# One-pass additive-error subset selection for ℓp subspace approximation

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 36 references that are in the map.
- First posted on arXiv 26 Apr 2022.

## Builds on (most cited first, 11 of 11)

- [Input Sparsity Time Low-Rank Approximation via Ridge Leverage Score Sampling](https://mlsanity.com/paper/1511.07263/) (2015)
- [Introduction to Core-sets: an Updated Survey](https://mlsanity.com/paper/2011.09384/) (2020)
- [Frequent Directions : Simple and Deterministic Matrix Sketching](https://mlsanity.com/paper/1501.01711/) (2015)
- [Monte Carlo Markov Chain Algorithms for Sampling Strongly Rayleigh Distributions and Determinantal Point Processes](https://mlsanity.com/paper/1602.05242/) (2016)
- [Improving CUR Matrix Decomposition and the Nystr"om Approximation via Adaptive Sampling](https://mlsanity.com/paper/1303.4207/) (2013)
- [Near Optimal Linear Algebra in the Online and Sliding Window Models](https://mlsanity.com/paper/1805.03765/) (2018)
- [Unbiased estimates for linear regression via volume sampling](https://mlsanity.com/paper/1705.06908/) (2017)
- [Non-Adaptive Adaptive Sampling on Turnstile Streams](https://mlsanity.com/paper/2004.10969/) (2020)
- [Relative Errors for Deterministic Low-Rank Matrix Approximations](https://mlsanity.com/paper/1307.7454/) (2013)
- [Leveraging Well-Conditioned Bases: Streaming & Distributed Summaries in Minkowski p-Norms](https://mlsanity.com/paper/1807.02571/) (2018)
- [Optimal Analysis of Subset-Selection Based L_p Low Rank Approximation](https://mlsanity.com/paper/1910.13618/) (2019)

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

- [Ridge Leverage Score Sampling for ℓp Subspace Approximation](https://mlsanity.com/paper/2407.03262/) (2024)

## Abstract (arXiv)

We consider the problem of subset selection for ℓp subspace approximation, that is, to efficiently find a small subset of data points such that solving the problem optimally for this subset gives a good approximation to solving the problem optimally for the original input. Previously known subset selection algorithms based on volume sampling and adaptive sampling citeDeshpandeV07, for the general case of p ∈ [1, ∞), require multiple passes over the data. In this paper, we give a one-pass subset selection with an additive approximation guarantee for ℓp subspace approximation, for any p ∈ [1, ∞). Earlier subset selection algorithms that give a one-pass multiplicative (1+ε) approximation work under the special cases. Cohen textitet al. citeCohenMM17 gives a one-pass subset section that offers multiplicative (1+ε) approximation guarantee for the special case of ℓ2 subspace approximation. Mahabadi textitet al. citeMahabadiRWZ20 gives a one-pass noisy subset selection with (1+ε) approximation guarantee for ℓp subspace approximation when p ∈ 1, 2. Our subset selection algorithm gives a weaker, additive approximation guarantee, but it works for any p ∈ [1, ∞).