# Streaming and Distributed Algorithms for Robust Column Subset Selection

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Jul 2021.

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

- [Solving Attention Kernel Regression Problem via Pre-conditioner](https://mlsanity.com/paper/2308.14304/) (2023)
- [Ridge Leverage Score Sampling for ℓp Subspace Approximation](https://mlsanity.com/paper/2407.03262/) (2024)
- [On Socially Fair Low-Rank Approximation and Column Subset Selection](https://mlsanity.com/paper/2412.06063/) (2024)
- [Performance of ℓ1 Regularization for Sparse Convex Optimization](https://mlsanity.com/paper/2307.07405/) (2023)
- [Online Adaptive Mahalanobis Distance Estimation](https://mlsanity.com/paper/2309.01030/) (2023)
- [Fast Heavy Inner Product Identification Between Weights and Inputs in Neural Network Training](https://mlsanity.com/paper/2311.11429/) (2023)

## Abstract (arXiv)

We give the first single-pass streaming algorithm for Column Subset Selection with respect to the entrywise ℓp-norm with 1 ≤ p < 2. We study the ℓp norm loss since it is often considered more robust to noise than the standard Frobenius norm. Given an input matrix A ∈ ℝd × n (n gg d), our algorithm achieves a multiplicative k^frac1p - frac12poly(log nd)-approximation to the error with respect to the best possible column subset of size k. Furthermore, the space complexity of the streaming algorithm is optimal up to a logarithmic factor. Our streaming algorithm also extends naturally to a 1-round distributed protocol with nearly optimal communication cost. A key ingredient in our algorithms is a reduction to column subset selection in the ℓp,2-norm, which corresponds to the p-norm of the vector of Euclidean norms of each of the columns of A. This enables us to leverage strong coreset constructions for the Euclidean norm, which previously had not been applied in this context. We also give the first provable guarantees for greedy column subset selection in the ℓ1, 2 norm, which can be used as an alternative, practical subroutine in our algorithms. Finally, we show that our algorithms give significant practical advantages on real-world data analysis tasks.