# On Subspace Approximation and Subset Selection in Fewer Passes by MCMC Sampling

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 9 of its 30 references that are in the map.
- First posted on arXiv 20 Mar 2021.

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

- [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)
- [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)
- [Algorithms for ℓp Low Rank Approximation](https://mlsanity.com/paper/1705.06730/) (2017)
- [Low Rank Approximation in the Presence of Outliers](https://mlsanity.com/paper/1804.10696/) (2018)
- [Subspace approximation with outliers](https://mlsanity.com/paper/2006.16573/) (2020)

## Abstract (arXiv)

We consider the problem of subset selection for ℓp subspace approximation, i.e., given n points in d dimensions, we need to pick a small, representative subset of the given points such that its span gives (1+ε) approximation to the best k-dimensional subspace that minimizes the sum of p-th powers of distances of all the points to this subspace. Sampling-based subset selection techniques require adaptive sampling iterations with multiple passes over the data. Matrix sketching techniques give a single-pass (1+ε) approximation for ℓp subspace approximation but require additional passes for subset selection. In this work, we propose an MCMC algorithm to reduce the number of passes required by previous subset selection algorithms based on adaptive sampling. For p=2, our algorithm gives subset selection of nearly optimal size in only 2 passes, whereas the number of passes required in previous work depend on k. Our algorithm picks a subset of size poly(k/ε) that gives (1+ε) approximation to the optimal subspace. The running time of the algorithm is nd + d~poly(k/ε). We extend our results to the case when outliers are present in the datasets, and suggest a two pass algorithm for the same. Our ideas also extend to give a reduction in the number of passes required by adaptive sampling algorithms for ℓp subspace approximation and subset selection, for p ≥ 2.