mlsanityData to 7 Oct 2026

Sketching as a Tool for Numerical Linear Algebra

arXiv 1411.4357 ↗First posted 17 Nov 2014cs.DScited by 285

Not on the map. Why?

Abstract (arXiv)

This survey highlights the recent advances in algorithms for numerical linear algebra that have come from the technique of linear sketching, whereby given a matrix, one first compresses it to a much smaller matrix by multiplying it by a (usually) random matrix with certain properties. Much of the expensive computation can then be performed on the smaller matrix, thereby accelerating the solution for the original problem. In this survey we consider least squares as well as robust regression problems, low rank approximation, and graph sparsification. We also discuss a number of variants of these problems. Finally, we discuss the limitations of sketching methods.

Key facts. Cited by 285 papers in the map (data through 7 Oct 2026). First posted on arXiv 17 Nov 2014.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 47; 2022: 54; 2023: 56; 2024: 49; 2025: 45; 2026: 34.

285 papers.

Sort:

By area:

  1. 2023Deja Vu: Contextual Sparsity for Efficient LLMs at Inference Timecited by 247
  2. 2022Training Data Influence Analysis and Estimation: A Surveycited by 134
  3. 2021Scaling Up Influence Functionscited by 130
  4. 2022Survey on Federated Learning Threats: concepts, taxonomy on attacks and defences, experimental study and challengescited by 81
  5. 2021Training Multi-Layer Over-Parametrized Neural Network in Subquadratic Timecited by 62
  6. 2024Scaling Laws in Linear Regression: Compute, Parameters, and Datacited by 54
  7. 2023Increasing the Scope as You Learn: Adaptive Bayesian Optimization in Nested Subspacescited by 50
  8. 2022A Framework and Benchmark for Deep Batch Active Learning for Regressioncited by 47
  9. 2022Submodularity In Machine Learning and Artificial Intelligencecited by 37
  10. 2021Fast Sketching of Polynomial Kernels of Polynomial Degreecited by 33
  11. 2023PolySketchFormer: Fast Transformers via Sketching Polynomial Kernelscited by 33
  12. 2021Scaling Neural Tangent Kernels via Sketching and Random Featurescited by 32
38 more
  1. 2023Bounce: Reliable High-Dimensional Bayesian Optimization for Combinatorial and Mixed Spacescited by 27
  2. 2022Sketching for First Order Method: Efficient Algorithm for Low-Bandwidth Channel and Vulnerabilitycited by 25
  3. 2021Newton-LESS: Sparsification without Trade-offs for the Sketched Newton Updatecited by 23
  4. 2021I Don't Need u: Identifiable Non-Linear ICA Without Side Informationcited by 21
  5. 2022Triangle and Four Cycle Counting with Predictions in Graph Streamscited by 20
  6. 2023Solving Attention Kernel Regression Problem via Pre-conditionercited by 20
  7. 2021Oblivious sketching for logistic regressioncited by 18
  8. 2022Sharp Analysis of Sketch-and-Project Methods via a Connection to Randomized Singular Value Decompositioncited by 17
  9. 2024Grass: Compute Efficient Low-Memory LLM Training with Structured Sparse Gradientscited by 17
  10. 2023Uncertainty-biased molecular dynamics for learning uniformly accurate interatomic potentialscited by 16
  11. 2025Towards Fast, Specialized Machine Learning Force Fields: Distilling Foundation Models via Energy Hessianscited by 15
  12. 2021Adaptive Newton Sketch: Linear-time Optimization with Quadratic Convergence and Effective Hessian Dimensionalitycited by 14
  13. 2021L1 Regression with Lewis Weights Subsamplingcited by 14
  14. 2023A Nearly-Optimal Bound for Fast Regression with ℓ_∞ Guaranteecited by 14
  15. 2024Provable Differentially Private Computation of the Cross-Attention Mechanismcited by 14
  16. 2021Mode-wise Tensor Decompositions: Multi-dimensional Generalizations of CUR Decompositionscited by 13
  17. 2021Learning Augmentation Distributions using Transformed Risk Minimizationcited by 13
  18. 2023Examining Modularity in Multilingual LMs via Language-Specialized Subnetworkscited by 13
  19. 2022Active Learning for Single Neuron Models with Lipschitz Non-Linearitiescited by 12
  20. 2023Query lower bounds for log-concave samplingcited by 12
  21. 2023Solving Dense Linear Systems Faster Than via Preconditioningcited by 12
  22. 2021Fast and Accurate Randomized Algorithms for Low-rank Tensor Decompositionscited by 11
  23. 2021Learning a Latent Simplex in Input-Sparsity Timecited by 11
  24. 2022Improved Random Features for Dot Product Kernelscited by 11
  25. 2022p-Generalized Probit Regression and Scalable Maximum Likelihood Estimation via Sketching and Coresetscited by 11
  26. 2022Over-the-Air Federated Learning via Second-Order Optimizationcited by 11
  27. 2022Communication-Efficient Robust Federated Learning with Noisy Labelscited by 11
  28. 2023CS4ML: A general framework for active learning with arbitrary data based on Christoffel functionscited by 11
  29. 2023Asymptotically free sketched ridge ensembles: Risks, cross-validation, and tuningcited by 11
  30. 2023Optimal Embedding Dimension for Sparse Subspace Embeddingscited by 11
  31. 2023Efficient High-Quality Clustering for Large Bipartite Graphscited by 11
  32. 2024Agnostic Active Learning of Single Index Models with Linear Sample Complexitycited by 11
  33. 2024Recent and Upcoming Developments in Randomized Numerical Linear Algebra for Machine Learningcited by 11
  34. 2021An Introduction to Johnson-Lindenstrauss Transformscited by 10
  35. 2021Accumulation of Sub-Sampling Matrices with Applications to Statistical Computationcited by 10
  36. 2022Tensor-reduced atomic density representationscited by 10
  37. 2022Conformal Frequency Estimation using Discrete Sketched Data with Coverage for Distinct Queriescited by 10
  38. 2023Generalization Bound and Learning Methods for Data-Driven Projections in Linear Programmingcited by 10

50 most cited of 285 All 285 (JSON)