# Practical sketching algorithms for low-rank matrix approximation

arXiv: https://arxiv.org/abs/1609.00048 · HTML: https://mlsanity.com/paper/1609.00048/

## Key facts

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

## Built on by (most cited first, 30 of 38)

- [Sketching Curvature for Efficient Out-of-Distribution Detection for Deep Neural Networks](https://mlsanity.com/paper/2102.12567/) (2021)
- [Matrix Compression via Randomized Low Rank and Low Precision Factorization](https://mlsanity.com/paper/2310.11028/) (2023)
- [K-shot NAS: Learnable Weight-Sharing for NAS with K-shot Supernets](https://mlsanity.com/paper/2106.06442/) (2021)
- [SketchySGD: Reliable Stochastic Optimization via Randomized Curvature Estimates](https://mlsanity.com/paper/2211.08597/) (2022)
- [Operator learning without the adjoint](https://mlsanity.com/paper/2401.17739/) (2024)
- [Nonparametric Control Koopman Operators](https://mlsanity.com/paper/2405.07312/) (2024)
- [Probabilistic methods for approximate archetypal analysis](https://mlsanity.com/paper/2108.05767/) (2021)
- [Sparse PCA With Multiple Components](https://mlsanity.com/paper/2209.14790/) (2022)
- [Tractable Uncertainty-Aware Meta-Learning](https://mlsanity.com/paper/2210.01881/) (2022)
- [A randomized algorithm to solve reduced rank operator regression](https://mlsanity.com/paper/2312.17348/) (2023)
- [Randomized K-FACs: Speeding up K-FAC with Randomized Numerical Linear Algebra](https://mlsanity.com/paper/2206.15397/) (2022)
- [Alternating Direction Method of Multipliers for Nonlinear Matrix Decompositions](https://mlsanity.com/paper/2512.17473/) (2025)
- [Spectral Guarantees for Adversarial Streaming PCA](https://mlsanity.com/paper/2408.10332/) (2024)
- [Learning-Augmented Frequent Directions](https://mlsanity.com/paper/2503.00937/) (2025)
- [Manifold-based Algorithms for the Hadamard Decomposition](https://mlsanity.com/paper/2605.28980/) (2026)
- [An Improved Frequent Directions Algorithm for Low-Rank Approximation via Block Krylov Iteration](https://mlsanity.com/paper/2109.11703/) (2021)
- [Multivariate Analysis for Multiple Network Data via Semi-Symmetric Tensor PCA](https://mlsanity.com/paper/2202.04719/) (2022)
- [Matching Pursuit Based Scheduling for Over-the-Air Federated Learning](https://mlsanity.com/paper/2206.06679/) (2022)
- [A Note on Dimensionality Reduction in Deep Neural Networks using Empirical Interpolation Method](https://mlsanity.com/paper/2305.09842/) (2023)
- [SketchOGD: Memory-Efficient Continual Learning](https://mlsanity.com/paper/2305.16424/) (2023)
- [Regression for matrix-valued data via Kronecker products factorization](https://mlsanity.com/paper/2404.19220/) (2024)
- [Perturbation Bounds for Low-Rank Inverse Approximations under Noise](https://mlsanity.com/paper/2510.25571/) (2025)
- [WARP: Weight Teleportation for Attack-Resilient Unlearning Protocols](https://mlsanity.com/paper/2512.00272/) (2025)
- [Concatenated Matrix SVD: Compression Bounds, Incremental Approximation, and Error-Constrained Clustering](https://mlsanity.com/paper/2601.11626/) (2026)
- [SeFoRA: Sketch-Aggregated Federated Low-Rank Adaptation with Heterogeneous Client Ranks](https://mlsanity.com/paper/2608.10144/) (2026)
- [Compressive Independent Component Analysis: Theory and Algorithms](https://mlsanity.com/paper/2110.08045/) (2021)
- [Sample Efficient Learning of Factored Embeddings of Tensor Fields](https://mlsanity.com/paper/2209.00372/) (2022)
- [Towards Efficient and Accurate Approximation: Tensor Decomposition Based on Randomized Block Krylov Iteration](https://mlsanity.com/paper/2211.14828/) (2022)
- [Variable Clustering via Distributionally Robust Nodewise Regression](https://mlsanity.com/paper/2212.07944/) (2022)
- [On the Noise Sensitivity of the Randomized SVD](https://mlsanity.com/paper/2305.17435/) (2023)

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