Randomized Sketching

Follow this topic Ask about this topic

Momentum

7 papers in the last four weeks, up 133% on the four weeks before. 0.1% of all new papers.

Jul 13Week of Sep 28

Latest papers 33

All topics

A Connectome Test of the Fly Hashing Algorithm
Oct 6, 2026Sebastian SengeDimensionality Reduction Randomized Sketching
Independent Researcher
The Advantages of Fresh Sketching for Ridge Regression
Sep 29, 2026Linkai Ma, Qilin Li, Petros DrineasImportance Sampling Randomized Sketching
Purdue University · University of Wisconsin-Madison
Single-Layer MeMo as a Randomized Hamming-Kernel Classifier
Sep 28, 2026Alessandro StraziotaMemory-Augmented Language Models Next-Token Prediction
Department of Enterprise Engineering University of Rome “Tor Vergata” Rome, Italy
Efficient Linear Bandits via Cluster-Aware Sketching
Sep 23, 2026Hantao Yang, Hong Xie, Defu LianMulti-Armed Bandits Randomized Sketching
University of Science and Technology of China
Randomized SVD Approximations for Spectral Co-Clustering of Word-Document Matrices
Sep 16, 2026Fateme Mazdarani, Carlos ToxtliClustering Randomized Sketching
School of Computing Clemson University Clemson, SC, USA
Accurate Trace Estimation with Fewer Random Bits via Recursive TensorSketch
Sep 16, 2026Mohammad Azhar Khan, Rameshwar Pratap, Amit SharmaRandomized Sketching
Indian Institute of Technology Hyderabad, Kandi, Sangareddy, 502284, Telangana, India.
Inference for Newton Methods with Accelerated Sketch-and-Project via Random Scaling
Sep 14, 2026Xinchen Du, Elizaveta Rebrova, Micha\l Dereziński +1Stochastic Approximation Second-Order Optimization
School of Industrial and Systems Engineering, Georgia Institute of Technology · Department of Operations Research and Financial Engineering, Princeton University · Computer Science and Engineering, University of Michigan
Photonic reservoir computing with dimensionally compressed readout
Sep 7, 2026Gerald Kobi, Mohab Abdalla, Miguel C. Soriano +1Reservoir Computing Randomized Sketching
Université de Lorraine, CentraleSupélec, LMOPS, F-57000 Metz, France · Instituto de Física Interdisciplinar y Sistemas Complejos (IFISC), CSIC–UIB, Campus UIB, E-07122 Palma de Mallorca, Spain
Exact Limits of Random Projections for Preserving Geometry: Distance Recovery, Nearest-Neighbor Rankings, and Covariance Shape in Gaussian Models
Sep 2, 2026Piyush SaoRandomized Sketching
Computer Science and Mathematics Division, Oak Ridge National Laboratory, Oak Ridge, Tennessee 37830, USA
Contact Geometry and Covariance Deficits in Volume-Sampled Least Squares
Aug 27, 2026Kihun Rhee, Hanjoon Byun, Junpyo SeoRandomized Sketching Linear Regression
Improving TensorSketch Using Complex Random Variables
Aug 11, 2026Amit Sharma, Mohammad Azhar Khan, Rameshwar Pratap +1Randomized Sketching Kernel Methods
Department of Computer Science and Engineering, IIT Hyderabad, India · Department of Mathematics and Statistics, Bucknell University, USA
MosaicJoin: Compact Semantic Sketches for Value-Level Join Discovery
Jul 23, 2026Grace Fan, Eden Wu, Majid Daliri +1Randomized Sketching Information Retrieval
New York University
Distributed Sketching on Data Partitions for OLS Regression
Jul 8, 2026Luyuan Yang, Brayden Garner, Shayan Shafaei +1Randomized Sketching Linear Regression
a School of Computer Science, University of Oklahoma, U.S.
Sampling on Random Subspaces under Limited Data in the Context of Exploratory Landscape Analysis
Jul 8, 2026Iván Olarte Rodríguez, Anja Jankovic, Thomas Bäck +1Black-Box Optimization Randomized Sketching
Leiden Institute of Advanced Computer Science (LIACS), Leiden University, The Netherlands · RWTH Aachen University, Germany
Any-Dimensional Learning by Sampling
Jul 8, 2026Eitan Levin, Venkat ChandrasekaranRandomized Sketching Generalization Bounds
Department of Statistics University of Chicago Chicago, IL 60637 · Department of Computing and Mathematical Sciences Department of Electrical Engineering California Institute of Technology Pasadena, CA 91125
Fast-TurboQuant: A Multiplier-Free Online Vector Quantization Approach
Jun 19, 2026Pedro M. R. Pereira, Felipe A. P. de Figueiredo, Rausley A. A. de SouzaLLM Quantization Rotation-Based Quantization
National Institute of Telecommunications (Inatel), Santa Rita do Sapucaí, MG 37536-001, Brazil
Stochastic trace estimation with tensor train random vectors
Jun 14, 2026Zvonimir Bujanović, Daniel Kressner, Hrvoje OlićTensor Networks Randomized Sketching
University of Zagreb, Faculty of Science, Department of Mathematics, Croatia. · Institute of Mathematics, EPFL, Switzerland.
Bidirectional Random Projections
Jun 9, 2026Chao Lan, Luyuan YangRandomized Sketching Linear Regression
a School of Computer Science, University of Oklahoma, U.S.
Bernstein-Schur Kernels: Random Features by Sketched Modulation and Radial Randomization
Jun 8, 2026Taha BouhsineFourier Feature Embeddings Kernel Ridge Regression
Azetta AI
The Fast Mixing Mechanism for Differential Privacy
May 28, 2026Omri Lev, Moshe Shenfeld, Vishwak Srinivasan +2Randomized Sketching Differential Privacy
Massachusetts Institute of Technology · The Hebrew University of Jerusalem
Optimizing Computational-Statistical Runtime for Wasserstein Distance Estimation
May 19, 2026Peter Matthew Jacobs, Jeff M. PhillipsRandomized Sketching Approximation Algorithms
Department of Statistics University of Wisconsin-Madison Madison, WI 53706 · Kahlert School of Computing University of Utah Salt Lake City, UT 84101
RL4RLA: Teaching ML to Discover Randomized Linear Algebra Algorithms Through Curriculum Design and Graph-Based Search
May 18, 2026Jinglong Xiong, Xiaotian Liu, Ruoxin Wang +4Reinforcement Learning Automated Algorithm Discovery
Pratt School of Engineering, Duke University, Durham, NC, USA · Department of Computer Science, Dartmouth College, Hanover, NH, USA.
MaxSketch: Robust Distinct Counting in Streams via Random Projections
May 15, 2026Nikos Tsikouras, Constantine Caramanis, Christos TzamosRandomized Sketching Streaming Algorithms
National and Kapodistrian University of Athens, Greece · Archimedes, Athena Research Center, Greece · The University of Texas at Austin, USA
Provable Quantization with Randomized Hadamard Transform
May 13, 2026Ying Feng, Piotr Indyk, Michael Kapralov +2Vector Quantization Randomized Sketching
Accelerating Power Method with Fast Sketching for Stronger Low-Rank Approximation
May 10, 2026Shabarish Chenakkod, Michał DerezińskiLow-Rank Matrix Decomposition Randomized Sketching
University of Michigan, Ann Arbor, MI 48105.
Quantizing With Randomized Hadamard Transforms: Efficient Heuristic Now Proven
May 7, 2026Ran Ben-Basat, William Kuszmaul, Michael Mitzenmacher +2Rotation-Based Quantization Gradient Compression
UCL and Broadcom · Carnegie Mellon University · Harvard University +2
Randomized Subspace Nesterov Accelerated Gradient
May 1, 2026Gaku Omiya, Pierre-Louis Poirion, Akiko TakedaGradient Descent Randomized Sketching
Department of Mathematical Informatics, The University of Tokyo, Tokyo, Japan · Center for Advanced Intelligence Project, RIKEN, Tokyo, Japan
Inference of Online Newton Methods with Nesterov's Accelerated Sketching
Apr 25, 2026Haoxuan Wang, Xinchen Du, Sen NaStochastic Approximation Second-Order Optimization
School of Industrial and Systems Engineering, Georgia Institute of Technology.
Analysis of Nystrom method with sequential ridge leverage scores
Apr 22, 2026Daniele Calandriello, Alessandro Lazaric, Michal ValkoKernel Ridge Regression Kernel Regression
SequeL team INRIA Lille - Nord Europe
Does Dimensionality Reduction via Random Projections Preserve Landscape Features?
Apr 14, 2026Iván Olarte Rodríguez, Anja Jankovic, Thomas Bäck +1Black-Box Optimization Randomized Sketching
Leiden Institute of Advanced Computer Science, Leiden University · Leiden, The Netherlands · RTWH Aachen University +1
On the (Generative) Linear Sketching Problem
Mar 15, 2026Xinyu Yuan, Yan Qiao, Zonghui Wang +1Unsupervised Learning Randomized Sketching
College of Computer Science and Technology, Zhejiang University, Hangzhou, China · School of Computer Science and Information Engineering, Hefei University of Technology, Hefei, China
Sublinear Sketches for Approximate Nearest Neighbor and Kernel Density Estimation
Oct 27, 2025Ved Danait, Srijan Das, Sujoy BhoreRandomized Sketching Kernel Density Estimation
Department of Computer Science & Engineering, Indian Institute of Technology Bombay, Mumbai, India. · Department of Computer Science & Engineering and Centre for Machine Intelligence & Data Science (CMINDS), Indian Institute of Technology Bombay, Mumbai, India.
Computationally-efficient Graph Modeling with Refined Graph Random Features
Oct 9, 2025Krzysztof Choromanski, Avinava Dubey, Arijit Sehanobish +1Graph Representation Learning Randomized Sketching
Google DeepMind, New York, NY, USA · Columbia University, New York, NY, USA · Google Research, Mountain View, CA, USA +2
Geometrically Principled Randomized Optimization for Efficient LLM Training
Oct 2, 2025Sahar Rajabi, Nayeema Nonta, Sirisha RambhatlaLanguage Model Pretraining Deep Learning Optimization
CriticalML Lab, University of Waterloo
When do cheap embeddings beat protein language models? A theoretically-grounded hashing sketch for biological sequence classification
Date pendingSarwan Ali, Taslim Murad, Imdadullah Khan +1Protein Language Models Randomized Sketching
Columbia University, NY, USA · Institute of Business Administration, Karachi, Pakistan · Lahore University of Management Sciences, Lahore, Pakistan +1

Oct 6, 2026, cs.NEJ/K move · Enter open · S save

A Connectome Test of the Fly Hashing Algorithm

Sebastian Senge

Independent Researcher

Dimensionality Reduction Randomized Sketching Brain Network Analysis

Open paper AskPDF arXiv

Dasgupta, Stevens and Navlakha (2017) showed that the Drosophila olfactory circuit, modelled as a random sparse projection followed by winner-take-all, is a locality-sensitive hash that beats classical LSH. The projection was random because the wiring was unknown. We test it against four electron-microscopy connectomes (MaleCNS, hemibrain, FlyWire, BANC; four animals, seven hemispheres). First, the 2017 pattern holds in a reimplementation of its protocol on SIFT, MNIST and odour mixtures (GloVe is near chance at short codes for every method): the fly hash beats k Gaussian projections at short hash lengths (3.1x in AP@200 on MNIST at k = 4). Second, against the tested real-valued Gaussian baseline that advantage is per active cell, not per operation: Gaussian projections given the same projection arithmetic retrieve better on every dataset and input dimension tested. Third, across four connectomes the measured pairing of glomeruli gives no consistent retrieval advantage over degree-preserving rewiring: retrieval is slightly lower (median -1.6%), and the small odour deficits depend on how missing odour responses are treated. Separately, equalising glomerular fan-out at fixed connection count improves retrieval in the model in every hemisphere, while equalising inputs per cell lowers it on average. Yet the fan-out profile is similar across the four sampled animals (median between-animal Spearman rho = 0.86), structural synapse counts do not offset it, and its relation to odour tuning is weak. In the model that uneven allocation costs retrieval. For practice: measured wiring gives no consistent retrieval advantage over degree-preserving random wiring, so a fly hash needs no connectome data, and its advantage is per active unit, which may suit hardware where active units rather than arithmetic are the binding cost, a hypothesis we do not test.

Momentum

Related topics

Latest papers 33