Randomized Sketching

Ask about this topic

Overview

Randomized sketching studies how to compress large vectors, matrices, or data streams while retaining the information needed for a particular computation. Common approaches include Gaussian and subspace embeddings, structured transforms such as randomized Hadamard matrices, hashing methods such as TensorSketch, and sketch-and-solve or iterative optimization algorithms. These techniques support faster regression, low-rank approximation, kernel methods, streaming summaries, quantization, and large-scale optimization. The field has strong guarantees for many settings, but a central challenge is balancing speed and memory savings against the preservation of task-relevant geometry, statistical accuracy, and robustness to data structure.

Latest papers

CardsList

45 papers8 papers in the last four weeks, level with the four weeks before. 0.0% of all new papers.

  1. Random Projections for Spectral Algorithms: Optimal Rates in Sobolev Norms

    Oct 22, 2026Caixing Wang, Yue WangGeneralization BoundsSpectral Methods

    School of Statistics and Data Science, Southeast University, Nanjing, 210000, Jiangsu, China · Faculty of Business for Science and Technology, School of Management, University of Science and Technology of China, Hefei, 230000, Anhui, China

  2. No Escape from the Quadratic Barrier: Adaptive Attacks on Linear ℓ2\ell_2 Sketches

    Oct 18, 2026Edith Cohen, Uri StemmerRandomized SketchingInformation-Theoretic Lower Bounds

    Google Research · Tel Aviv University

  3. Efficient Preconditioned Optimization Methods with Frequent Directions

    Oct 12, 2026Sifan Yang, Yuanyu Wan, Yibo Wang +1Adaptive Gradient MethodsOnline Convex Optimization

    State Key Laboratory of Novel Software Technology, Nanjing University, Nanjing, China · School of Artificial Intelligence, Nanjing University, Nanjing, China · School of Software Technology, Zhejiang University, Ningbo, China +1

  4. Fast Quantized Johnson−-Lindenstrauss Transforms

    Oct 12, 2026Angelos Korakitis, Vasileios NakosQuantizationRandomized Sketching

    National and Kapodistrian University of Athens

  5. Efficient quadratic entropy with distance sketches

    Oct 8, 2026Steve HuntsmanRandomized Sketching

  6. A Connectome Test of the Fly Hashing Algorithm

    Oct 6, 2026Sebastian SengeDimensionality ReductionRandomized Sketching

    Independent Researcher

  7. The Advantages of Fresh Sketching for Ridge Regression

    Sep 29, 2026Linkai Ma, Qilin Li, Petros DrineasImportance SamplingRandomized Sketching

    Purdue University · University of Wisconsin-Madison

  8. Single-Layer MeMo as a Randomized Hamming-Kernel Classifier

    Sep 28, 2026Alessandro StraziotaMemory-Augmented Language ModelsNext-Token Prediction

    Department of Enterprise Engineering University of Rome “Tor Vergata” Rome, Italy

  9. Extremely Fast and Compact Binary Graph Representations via Randomized Operator Sketching

    Sep 26, 2026Srajan Agarwal, Megha P, Bikas C Das +2Graph Representation LearningRandomized Sketching

    School of Data Science, IISER Thiruvananthapuram, India · Department of Physical Sciences, IISER Berhampur, India

  10. Efficient Linear Bandits via Cluster-Aware Sketching

    Sep 23, 2026Hantao Yang, Hong Xie, Defu LianMulti-Armed BanditsRandomized Sketching

    University of Science and Technology of China

  11. Randomized SVD Approximations for Spectral Co-Clustering of Word-Document Matrices

    Sep 16, 2026Fateme Mazdarani, Carlos ToxtliClusteringRandomized Sketching

    School of Computing Clemson University Clemson, SC, USA

  12. 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.

  13. Inference for Newton Methods with Accelerated Sketch-and-Project via Random Scaling

    Sep 11, 2026Xinchen Du, Elizaveta Rebrova, Michał Dereziński +1Stochastic ApproximationSecond-Order Optimization

    School of Industrial and Systems Engineering, Georgia Institute of Technology · Department of Operations Research and Financial Engineering, Princeton University

  14. Photonic reservoir computing with dimensionally compressed readout

    Sep 7, 2026Gerald Kobi, Mohab Abdalla, Miguel C. Soriano +1Reservoir ComputingRandomized 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

  15. Communication-Efficient Personalized Federated Learning via Layer-Wise Multi-Threshold Random Sketching

    Sep 4, 2026Xu Zhang, Xingyu Hou, Jiacheng Cheng +2Federated LearningLow-Bit Quantization

    School of Artificial Intelligence, Xidian University, Xi’an, 710126, China · School of Automation, Northwestern Polytechnical University, Xi’an, China · Key Laboratory of Collaborative Intelligence Systems, Ministry of Education, Xidian University, Xi’an, 710071, China +2

  16. 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

  17. Contact Geometry and Covariance Deficits in Volume-Sampled Least Squares

    Aug 27, 2026Kihun Rhee, Hanjoon Byun, Junpyo SeoRandomized SketchingLinear Regression

  18. Hadamard Flattening and Gaussian Pooling Sketch for Least Squares with Coordinate-wise Guarantee

    Aug 27, 2026Zhao Song, Lichen ZhangRandomized SketchingLinear Regression

    Independent Researcher. · Massachusetts Institute of Technology.

  19. Improving TensorSketch Using Complex Random Variables

    Aug 11, 2026Amit Sharma, Mohammad Azhar Khan, Rameshwar Pratap +1Randomized SketchingKernel Methods

    Department of Computer Science and Engineering, IIT Hyderabad, India · Department of Mathematics and Statistics, Bucknell University, USA

  20. MosaicJoin: Compact Semantic Sketches for Value-Level Join Discovery

    Jul 23, 2026Grace Fan, Eden Wu, Majid Daliri +1Randomized SketchingInformation Retrieval

    New York University

  21. Distributed Sketching on Data Partitions for OLS Regression

    Jul 8, 2026Luyuan Yang, Brayden Garner, Shayan Shafaei +1Randomized SketchingLinear Regression

    a School of Computer Science, University of Oklahoma, U.S.

  22. 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 OptimizationRandomized Sketching

    Leiden Institute of Advanced Computer Science (LIACS), Leiden University, The Netherlands · RWTH Aachen University, Germany

  23. Any-Dimensional Learning by Sampling

    Jul 8, 2026Eitan Levin, Venkat ChandrasekaranRandomized SketchingGeneralization 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

  24. 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 QuantizationRotation-Based Quantization

    National Institute of Telecommunications (Inatel), Santa Rita do Sapucaí, MG 37536-001, Brazil

  25. Stochastic trace estimation with tensor train random vectors

    Jun 14, 2026Zvonimir Bujanović, Daniel Kressner, Hrvoje OlićTensor NetworksRandomized Sketching

    University of Zagreb, Faculty of Science, Department of Mathematics, Croatia. · Institute of Mathematics, EPFL, Switzerland.

  26. Bidirectional Random Projections

    Jun 9, 2026Chao Lan, Luyuan YangRandomized SketchingLinear Regression

    a School of Computer Science, University of Oklahoma, U.S.

  27. Bernstein-Schur Kernels: Random Features by Sketched Modulation and Radial Randomization

    Jun 8, 2026Taha BouhsineFourier Feature EmbeddingsKernel Ridge Regression

    Azetta AI

  28. The Fast Mixing Mechanism for Differential Privacy

    May 28, 2026Omri Lev, Moshe Shenfeld, Vishwak Srinivasan +2Randomized SketchingDifferential Privacy

    Massachusetts Institute of Technology · The Hebrew University of Jerusalem

  29. Optimizing Computational-Statistical Runtime for Wasserstein Distance Estimation

    May 19, 2026Peter Matthew Jacobs, Jeff M. PhillipsRandomized SketchingApproximation Algorithms

    Department of Statistics University of Wisconsin-Madison Madison, WI 53706 · Kahlert School of Computing University of Utah Salt Lake City, UT 84101

  30. 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 LearningAutomated Algorithm Discovery

    Pratt School of Engineering, Duke University, Durham, NC, USA · Department of Computer Science, Dartmouth College, Hanover, NH, USA.