mlsanityData to 7 Oct 2026

Practical sketching algorithms for low-rank matrix approximation

arXiv 1609.00048 ↗First posted 31 Aug 2016math.NA cs.DS cs.NAcited by 38

Not on the map. Why?

Abstract (arXiv)

This paper describes a suite of algorithms for constructing low-rank approximations of an input matrix from a random linear image of the matrix, called a sketch. These methods can preserve structural properties of the input matrix, such as positive-semidefiniteness, and they can produce approximations with a user-specified rank. The algorithms are simple, accurate, numerically stable, and provably correct. Moreover, each method is accompanied by an informative error bound that allows users to select parameters a priori to achieve a given approximation quality. These claims are supported by numerical experiments with real and synthetic data.

Key facts. Cited by 38 papers in the map (data through 7 Oct 2026). First posted on arXiv 31 Aug 2016.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 5; 2022: 9; 2023: 7; 2024: 5; 2025: 7; 2026: 5.

38 papers.

Sort:

By area:

  1. 2021Sketching Curvature for Efficient Out-of-Distribution Detection for Deep Neural Networkscited by 32
  2. 2023Matrix Compression via Randomized Low Rank and Low Precision Factorizationcited by 25
  3. 2021K-shot NAS: Learnable Weight-Sharing for NAS with K-shot Supernetscited by 22
  4. 2022SketchySGD: Reliable Stochastic Optimization via Randomized Curvature Estimatescited by 8
  5. 2024Operator learning without the adjointcited by 8
  6. 2024Nonparametric Control Koopman Operatorscited by 7
  7. 2021Probabilistic methods for approximate archetypal analysiscited by 4
  8. 2022Sparse PCA With Multiple Componentscited by 4
  9. 2022Tractable Uncertainty-Aware Meta-Learningcited by 4
  10. 2023A randomized algorithm to solve reduced rank operator regressioncited by 4
  11. 2022Randomized K-FACs: Speeding up K-FAC with Randomized Numerical Linear Algebracited by 3
  12. 2025Alternating Direction Method of Multipliers for Nonlinear Matrix Decompositionscited by 3
26 more
  1. 2024Spectral Guarantees for Adversarial Streaming PCAcited by 2
  2. 2025Learning-Augmented Frequent Directionscited by 2
  3. 2026Manifold-based Algorithms for the Hadamard Decompositioncited by 2
  4. 2021An Improved Frequent Directions Algorithm for Low-Rank Approximation via Block Krylov Iterationcited by 1
  5. 2022Multivariate Analysis for Multiple Network Data via Semi-Symmetric Tensor PCAcited by 1
  6. 2022Matching Pursuit Based Scheduling for Over-the-Air Federated Learningcited by 1
  7. 2023A Note on Dimensionality Reduction in Deep Neural Networks using Empirical Interpolation Methodcited by 1
  8. 2023SketchOGD: Memory-Efficient Continual Learningcited by 1
  9. 2024Regression for matrix-valued data via Kronecker products factorizationcited by 1
  10. 2025Perturbation Bounds for Low-Rank Inverse Approximations under Noisecited by 1
  11. 2025WARP: Weight Teleportation for Attack-Resilient Unlearning Protocolscited by 1
  12. 2026Concatenated Matrix SVD: Compression Bounds, Incremental Approximation, and Error-Constrained Clusteringcited by 1
  13. 2026SeFoRA: Sketch-Aggregated Federated Low-Rank Adaptation with Heterogeneous Client Rankscited by 1
  14. 2021Compressive Independent Component Analysis: Theory and Algorithmscited by 0
  15. 2022Sample Efficient Learning of Factored Embeddings of Tensor Fieldscited by 0
  16. 2022Towards Efficient and Accurate Approximation: Tensor Decomposition Based on Randomized Block Krylov Iterationcited by 0
  17. 2022Variable Clustering via Distributionally Robust Nodewise Regressioncited by 0
  18. 2023On the Noise Sensitivity of the Randomized SVDcited by 0
  19. 2023Making the Nystr"om method highly accurate for low-rank approximationscited by 0
  20. 2023Sketching for Convex and Nonconvex Regularized Least Squares with Sharp Guaranteescited by 0
  21. 2024Learning nonnegative matrix factorizations from compressed datacited by 0
  22. 2025Accelerating Large-Scale Regularized High-Order Tensor Recoverycited by 0
  23. 2025Sketching Low-Rank Plus Diagonal Matricescited by 0
  24. 2025Randomized Matrix Sketching for Neural Network Training and Gradient Monitoringcited by 0
  25. 2026Direction-Magnitude Decomposition for Low-Rank Matrix Optimization: Faster Convergence and Saddle-to-saddle Dynamicscited by 0
  26. 2026Subzero matrix completion for sparse data analysis: large-scale learning of latent low-rank structurecited by 0