# New Subset Selection Algorithms for Low Rank Approximation: Offline and Online

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 Apr 2023.

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

- [Data-Efficient Learning via Clustering-Based Sensitivity Sampling: Foundation Models and Beyond](https://mlsanity.com/paper/2402.17327/) (2024)
- [BUZZ: Beehive-structured Sparse KV Cache with Segmented Heavy Hitters for Efficient LLM Inference](https://mlsanity.com/paper/2410.23079/) (2024)
- [Tight Bounds for Volumetric Spanners and Applications](https://mlsanity.com/paper/2310.00175/) (2023)
- [Optimal bounds for ℓp sensitivity sampling via ℓ2 augmentation](https://mlsanity.com/paper/2406.00328/) (2024)
- [Turnstile ℓp leverage score sampling with applications](https://mlsanity.com/paper/2406.00339/) (2024)
- [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)
- [Data subsampling for Poisson regression with pth-root-link](https://mlsanity.com/paper/2410.22872/) (2024)
- [Performance of ℓ1 Regularization for Sparse Convex Optimization](https://mlsanity.com/paper/2307.07405/) (2023)
- [Sketching Algorithms for Sparse Dictionary Learning: PTAS and Turnstile Streaming](https://mlsanity.com/paper/2310.19068/) (2023)
- [Active Learning with Low-Rank Structure for Data Selection](https://mlsanity.com/paper/2606.16045/) (2026)

## Abstract (arXiv)

Subset selection for the rank k approximation of an n× d matrix A offers improvements in the interpretability of matrices, as well as a variety of computational savings. This problem is well-understood when the error measure is the Frobenius norm, with various tight algorithms known even in challenging models such as the online model, where an algorithm must select the column subset irrevocably when the columns arrive one by one. In contrast, for other matrix losses, optimal trade-offs between the subset size and approximation quality have not been settled, even in the offline setting. We give a number of results towards closing these gaps. In the offline setting, we achieve nearly optimal bicriteria algorithms in two settings. First, we remove a √ k factor from a result of [SWZ19] when the loss function is any entrywise loss with an approximate triangle inequality and at least linear growth. Our result is tight for the ℓ1 loss. We give a similar improvement for entrywise ℓp losses for p>2, improving a previous distortion of k1-1/p to k1/2-1/p. Our results come from a technique which replaces the use of a well-conditioned basis with a slightly larger spanning set for which any vector can be expressed as a linear combination with small Euclidean norm. We show that this technique also gives the first oblivious ℓp subspace embeddings for 1<p<2 with tilde O(d1/p) distortion, which is nearly optimal and closes a long line of work. In the online setting, we give the first online subset selection algorithm for ℓp subspace approximation and entrywise ℓp low rank approximation by implementing sensitivity sampling online, which is challenging due to the sequential nature of sensitivity sampling. Our main technique is an online algorithm for detecting when an approximately optimal subspace changes substantially.