# Input Sparsity Time Low-Rank Approximation via Ridge Leverage Score Sampling

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

## Key facts

- Cited by 46 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Nov 2015.

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

- [DataComp: In search of the next generation of multimodal datasets](https://mlsanity.com/paper/2304.14108/) (2023)
- [Challenges in Training PINNs: A Loss Landscape Perspective](https://mlsanity.com/paper/2402.01868/) (2024)
- [Efficient Dataset Distillation Using Random Feature Approximation](https://mlsanity.com/paper/2210.12067/) (2022)
- [Graph Condensation for Inductive Node Representation Learning](https://mlsanity.com/paper/2307.15967/) (2023)
- [Provably Accurate Shapley Value Estimation via Leverage Score Sampling](https://mlsanity.com/paper/2410.01917/) (2024)
- [Unlocking the Potential of Federated Learning: The Symphony of Dataset Distillation via Deep Generative Latents](https://mlsanity.com/paper/2312.01537/) (2023)
- [Coresets for Vertical Federated Learning: Regularized Linear Regression and K-Means Clustering](https://mlsanity.com/paper/2210.14664/) (2022)
- [Provable Data Subset Selection For Efficient Neural Network Training](https://mlsanity.com/paper/2303.05151/) (2023)
- [EigenGame Unloaded: When playing games is better than optimizing](https://mlsanity.com/paper/2102.04152/) (2021)
- [Adversarial Robustness of Streaming Algorithms through Importance Sampling](https://mlsanity.com/paper/2106.14952/) (2021)
- [Active Learning for Single Neuron Models with Lipschitz Non-Linearities](https://mlsanity.com/paper/2210.13601/) (2022)
- [Solving Dense Linear Systems Faster Than via Preconditioning](https://mlsanity.com/paper/2312.08893/) (2023)
- [An Introduction to Johnson-Lindenstrauss Transforms](https://mlsanity.com/paper/2103.00564/) (2021)
- [Learning a Latent Simplex in Input-Sparsity Time](https://mlsanity.com/paper/2105.08005/) (2021)
- [Optimal Embedding Dimension for Sparse Subspace Embeddings](https://mlsanity.com/paper/2311.10680/) (2023)
- [Fine-grained Analysis and Faster Algorithms for Iteratively Solving Linear Systems](https://mlsanity.com/paper/2405.05818/) (2024)
- [Random Gegenbauer Features for Scalable Kernel Methods](https://mlsanity.com/paper/2202.03474/) (2022)
- [Subquadratic Kronecker Regression with Applications to Tensor Decomposition](https://mlsanity.com/paper/2209.04876/) (2022)
- [DataS^3: Dataset Subset Selection for Specialization](https://mlsanity.com/paper/2504.16277/) (2025)
- [Fast Low-Rank Tensor Decomposition by Ridge Leverage Score Sampling](https://mlsanity.com/paper/2107.10654/) (2021)
- [Sketchy Moment Matching: Toward Fast and Provable Data Selection for Finetuning](https://mlsanity.com/paper/2407.06120/) (2024)
- [Near-Optimal Algorithms for Linear Algebra in the Current Matrix Multiplication Time](https://mlsanity.com/paper/2107.08090/) (2021)
- [Probabilistic methods for approximate archetypal analysis](https://mlsanity.com/paper/2108.05767/) (2021)
- [Faster Linear Systems and Matrix Norm Approximation via Multi-level Sketched Preconditioning](https://mlsanity.com/paper/2405.05865/) (2024)
- [MetaTT: A Global Tensor-Train Adapter for Parameter-Efficient Fine-Tuning](https://mlsanity.com/paper/2506.09105/) (2025)
- [Fast Convex Quadratic Optimization Solvers with Adaptive Sketching-based Preconditioners](https://mlsanity.com/paper/2104.14101/) (2021)
- [Distributed Least Squares in Small Space via Sketching and Bias Reduction](https://mlsanity.com/paper/2405.05343/) (2024)
- [Estimating leverage scores via rank revealing methods and randomization](https://mlsanity.com/paper/2105.11004/) (2021)
- [A Batch-to-Online Transformation under Random-Order Model](https://mlsanity.com/paper/2306.07163/) (2023)
- [Ridge Leverage Score Sampling for ℓp Subspace Approximation](https://mlsanity.com/paper/2407.03262/) (2024)

## Abstract (arXiv)

We present a new algorithm for finding a near optimal low-rank approximation of a matrix A in O(nnz(A)) time. Our method is based on a recursive sampling scheme for computing a representative subset of A's columns, which is then used to find a low-rank approximation. This approach differs substantially from prior O(nnz(A)) time algorithms, which are all based on fast Johnson-Lindenstrauss random projections. It matches the guarantees of these methods while offering a number of advantages. Not only are sampling algorithms faster for sparse and structured data, but they can also be applied in settings where random projections cannot. For example, we give new single-pass streaming algorithms for the column subset selection and projection-cost preserving sample problems. Our method has also been used to give the fastest algorithms for provably approximating kernel matrices [MM16].