mlsanityData to 14 Oct 2026

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

arXiv 1511.07263 ↗First posted 23 Nov 2015cs.DS cs.LGcited by 46

Not on the map. Why?

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

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 11; 2022: 6; 2023: 11; 2024: 9; 2025: 5; 2026: 4.

46 papers.

Sort:

By area:

  1. 2023DataComp: In search of the next generation of multimodal datasetscited by 644
  2. 2024Challenges in Training PINNs: A Loss Landscape Perspectivecited by 113
  3. 2022Efficient Dataset Distillation Using Random Feature Approximationcited by 111
  4. 2023Graph Condensation for Inductive Node Representation Learningcited by 31
  5. 2024Provably Accurate Shapley Value Estimation via Leverage Score Samplingcited by 23
  6. 2023Unlocking the Potential of Federated Learning: The Symphony of Dataset Distillation via Deep Generative Latentscited by 16
  7. 2022Coresets for Vertical Federated Learning: Regularized Linear Regression and K-Means Clusteringcited by 14
  8. 2023Provable Data Subset Selection For Efficient Neural Network Trainingcited by 14
  9. 2021EigenGame Unloaded: When playing games is better than optimizingcited by 13
  10. 2021Adversarial Robustness of Streaming Algorithms through Importance Samplingcited by 13
  11. 2022Active Learning for Single Neuron Models with Lipschitz Non-Linearitiescited by 12
  12. 2023Solving Dense Linear Systems Faster Than via Preconditioningcited by 12
34 more
  1. 2021An Introduction to Johnson-Lindenstrauss Transformscited by 11
  2. 2021Learning a Latent Simplex in Input-Sparsity Timecited by 11
  3. 2023Optimal Embedding Dimension for Sparse Subspace Embeddingscited by 11
  4. 2024Fine-grained Analysis and Faster Algorithms for Iteratively Solving Linear Systemscited by 7
  5. 2022Random Gegenbauer Features for Scalable Kernel Methodscited by 6
  6. 2022Subquadratic Kronecker Regression with Applications to Tensor Decompositioncited by 6
  7. 2025DataS^3: Dataset Subset Selection for Specializationcited by 6
  8. 2021Fast Low-Rank Tensor Decomposition by Ridge Leverage Score Samplingcited by 5
  9. 2024Sketchy Moment Matching: Toward Fast and Provable Data Selection for Finetuningcited by 5
  10. 2021Near-Optimal Algorithms for Linear Algebra in the Current Matrix Multiplication Timecited by 4
  11. 2021Probabilistic methods for approximate archetypal analysiscited by 4
  12. 2024Faster Linear Systems and Matrix Norm Approximation via Multi-level Sketched Preconditioningcited by 4
  13. 2025MetaTT: A Global Tensor-Train Adapter for Parameter-Efficient Fine-Tuningcited by 4
  14. 2021Fast Convex Quadratic Optimization Solvers with Adaptive Sketching-based Preconditionerscited by 3
  15. 2024Distributed Least Squares in Small Space via Sketching and Bias Reductioncited by 3
  16. 2021Estimating leverage scores via rank revealing methods and randomizationcited by 2
  17. 2023A Batch-to-Online Transformation under Random-Order Modelcited by 2
  18. 2024Ridge Leverage Score Sampling for ℓp Subspace Approximationcited by 2
  19. 2024On Socially Fair Low-Rank Approximation and Column Subset Selectioncited by 2
  20. 2025Fundamental Bias in Inverting Random Sampling Matrices with Application to Sub-sampled Newtoncited by 2
  21. 2026Improved large-scale graph learning through ridge spectral sparsificationcited by 2
  22. 2021ALLWAS: Active Learning on Language models in WASserstein spacecited by 1
  23. 2022One-pass additive-error subset selection for ℓp subspace approximationcited by 1
  24. 2023SALSA: Sequential Approximate Leverage-Score Algorithm with Application in Analyzing Big Time Series Datacited by 1
  25. 2021Non-PSD Matrix Sketching with Applications to Regression and Optimizationcited by 0
  26. 2023Learning the Positions in CountSketchcited by 0
  27. 2023Ordering for Non-Replacement SGDcited by 0
  28. 2023Performance of ℓ1 Regularization for Sparse Convex Optimizationcited by 0
  29. 2024HERTA: A High-Efficiency and Rigorous Training Algorithm for Unfolded Graph Neural Networkscited by 0
  30. 2025Importance Sampling for Nonlinear Modelscited by 0
  31. 2025Distribution-Aware Feature Selection for SAEscited by 0
  32. 2026From Average Sensitivity to Small-Loss Regret Bounds under Random-Order Modelcited by 0
  33. 2026Beyond Averaging in John Ellipsoid Approximation: High-Accuracy Algorithms in the Leverage-Score Modelcited by 0
  34. 2026The Advantages of Fresh Sketching for Ridge Regressioncited by 0