# Ridge Leverage Score Sampling for ℓp Subspace Approximation

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 38 of its 96 references that are in the map.
- First posted on arXiv 3 Jul 2024.

## Builds on (most cited first, 30 of 38)

- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [Sketching as a Tool for Numerical Linear Algebra](https://mlsanity.com/paper/1411.4357/) (2014)
- [Turning Big data into tiny data: Constant-size coresets for k-means, PCA and projective clustering](https://mlsanity.com/paper/1807.04518/) (2018)
- [Input Sparsity Time Low-Rank Approximation via Ridge Leverage Score Sampling](https://mlsanity.com/paper/1511.07263/) (2015)
- [New Frameworks for Offline and Streaming Coreset Constructions](https://mlsanity.com/paper/1612.00889/) (2016)
- [A New Coreset Framework for Clustering](https://mlsanity.com/paper/2104.06133/) (2021)
- [Uniform Sampling for Matrix Approximation](https://mlsanity.com/paper/1408.5099/) (2014)
- [Coresets for Clustering in Euclidean Spaces: Importance Sampling is Nearly Optimal](https://mlsanity.com/paper/2004.06263/) (2020)
- [Strong Coresets for k-Median and Subspace Approximation: Goodbye Dimension](https://mlsanity.com/paper/1809.02961/) (2018)
- [Query Complexity of Least Absolute Deviation Regression via Robust Uniform Convergence](https://mlsanity.com/paper/2102.02322/) (2021)
- [Towards Optimal Lower Bounds for k-median and k-means Coresets](https://mlsanity.com/paper/2202.12793/) (2022)
- [Near Optimal Linear Algebra in the Online and Sliding Window Models](https://mlsanity.com/paper/1805.03765/) (2018)
- [Sublinear Time Low-Rank Approximation of Positive Semidefinite Matrices](https://mlsanity.com/paper/1704.03371/) (2017)
- [Online Row Sampling](https://mlsanity.com/paper/1604.05448/) (2016)
- [Online Lewis Weight Sampling](https://mlsanity.com/paper/2207.08268/) (2022)
- [Coresets for Clustering in Excluded-minor Graphs and Beyond](https://mlsanity.com/paper/2004.07718/) (2020)
- [Input Sparsity and Hardness for Robust Subspace Approximation](https://mlsanity.com/paper/1510.06073/) (2015)
- [p-Generalized Probit Regression and Scalable Maximum Likelihood Estimation via Sketching and Coresets](https://mlsanity.com/paper/2203.13568/) (2022)
- [New Subset Selection Algorithms for Low Rank Approximation: Offline and Online](https://mlsanity.com/paper/2304.09217/) (2023)
- [Non-Adaptive Adaptive Sampling on Turnstile Streams](https://mlsanity.com/paper/2004.10969/) (2020)
- [On Optimal Coreset Construction for Euclidean (k,z)-Clustering](https://mlsanity.com/paper/2211.11923/) (2022)
- [Dimensionality Reduction for Sum-of-Distances Metric](https://mlsanity.com/paper/1912.12003/) (2019)
- [High-Dimensional Geometric Streaming in Polynomial Space](https://mlsanity.com/paper/2204.03790/) (2022)
- [Streaming Euclidean k-median and k-means with o(log n) Space](https://mlsanity.com/paper/2310.02882/) (2023)
- [Tight Bounds for the Subspace Sketch Problem with Applications](https://mlsanity.com/paper/1904.05543/) (2019)
- [Projection-Cost-Preserving Sketches: Proof Strategies and Constructions](https://mlsanity.com/paper/2004.08434/) (2020)
- [Streaming and Distributed Algorithms for Robust Column Subset Selection](https://mlsanity.com/paper/2107.07657/) (2021)
- [Sublinear Time Numerical Linear Algebra for Structured Matrices](https://mlsanity.com/paper/1912.06060/) (2019)
- [Spectral Hypergraph Sparsifiers of Nearly Linear Size](https://mlsanity.com/paper/2106.02353/) (2021)
- [Optimal Analysis of Subset-Selection Based L_p Low Rank Approximation](https://mlsanity.com/paper/1910.13618/) (2019)

## Built on by (most cited first, 2 of 2)

- [Stellar Colosseum: A Many-Agent Harness for Long-Horizon Research in Mathematics and Theoretical Computer Science](https://mlsanity.com/paper/2609.15983/) (2026)
- [Guessing Efficiently for Constrained Subspace Approximation](https://mlsanity.com/paper/2504.20883/) (2025)

## Abstract (arXiv)

The ℓp subspace approximation problem is an NP-hard low rank approximation problem that generalizes the median hyperplane (p = 1), principal component analysis (p = 2), and center hyperplane problems (p = ∞). A popular approach to cope with the NP-hardness is to compute a strong coreset, which is a weighted subset of input points that simultaneously approximates the cost of every k-dimensional subspace, typically to (1+ε) relative error for a small constant ε. We obtain an algorithm for constructing a strong coreset for ℓp subspace approximation of size tilde O(kε-4/p) for p<2 and tilde O(kp/2ε-p) for p>2. This offers the following improvements over prior work: - We construct the first strong coresets with nearly optimal dependence on k for all pneq 2. In prior work, [SW18] constructed coresets of modified points with a similar dependence on k, while [HV20] constructed true coresets with polynomially worse dependence on k. - We recover or improve the best known ε dependence for all p. In particular, for p > 2, the [SW18] coreset of modified points had a dependence of ε-p2/2 and the [HV20] coreset had a dependence of ε-3p. Our algorithm is based on sampling by root ridge leverage scores, which admits fast algorithms, especially for sparse or structured matrices. Our analysis avoids the use of the representative subspace theorem [SW18], which is a critical component of all prior dimension-independent coresets for ℓp subspace approximation. Our techniques also lead to the first nearly optimal online strong coresets for ℓp subspace approximation with similar bounds as the offline setting, resolving a problem of [WY23]. All prior approaches lose poly(k) factors in this setting, even when allowed to modify the original points.