# Average Case Column Subset Selection for Entrywise ℓ1-Norm Loss

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

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Apr 2020.

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

- [Solving Regularized Exp, Cosh and Sinh Regression Problems](https://mlsanity.com/paper/2303.15725/) (2023)
- [Low Rank Matrix Completion via Robust Alternating Minimization in Nearly Linear Time](https://mlsanity.com/paper/2302.11068/) (2023)
- [GradientCoin: A Peer-to-Peer Decentralized Large Language Models](https://mlsanity.com/paper/2308.10502/) (2023)
- [Dynamic Tensor Product Regression](https://mlsanity.com/paper/2210.03961/) (2022)
- [Efficient SGD Neural Network Training via Sublinear Activated Neuron Identification](https://mlsanity.com/paper/2307.06565/) (2023)
- [Efficient Alternating Minimization with Applications to Weighted Low Rank Approximation](https://mlsanity.com/paper/2306.04169/) (2023)
- [Solving Tensor Low Cycle Rank Approximation](https://mlsanity.com/paper/2304.06594/) (2023)
- [Is Solving Graph Neural Tangent Kernel Equivalent to Training Graph Neural Network?](https://mlsanity.com/paper/2309.07452/) (2023)
- [Low-Rank Approximation with 1/ε1/3 Matrix-Vector Products](https://mlsanity.com/paper/2202.05120/) (2022)
- [Only Large Weights (And Not Skip Connections) Can Prevent the Perils of Rank Collapse](https://mlsanity.com/paper/2505.16284/) (2025)
- [Performance of ℓ1 Regularization for Sparse Convex Optimization](https://mlsanity.com/paper/2307.07405/) (2023)
- [Fast Heavy Inner Product Identification Between Weights and Inputs in Neural Network Training](https://mlsanity.com/paper/2311.11429/) (2023)

## Abstract (arXiv)

We study the column subset selection problem with respect to the entrywise ℓ1-norm loss. It is known that in the worst case, to obtain a good rank-k approximation to a matrix, one needs an arbitrarily large nOmega(1) number of columns to obtain a (1+ε)-approximation to the best entrywise ℓ1-norm low rank approximation of an n × n matrix. Nevertheless, we show that under certain minimal and realistic distributional settings, it is possible to obtain a (1+ε)-approximation with a nearly linear running time and poly(k/ε)+O(klog n) columns. Namely, we show that if the input matrix A has the form A = B + E, where B is an arbitrary rank-k matrix, and E is a matrix with i.i.d. entries drawn from any distribution μ for which the (1+γ)-th moment exists, for an arbitrarily small constant γ > 0, then it is possible to obtain a (1+ε)-approximate column subset selection to the entrywise ℓ1-norm in nearly linear time. Conversely we show that if the first moment does not exist, then it is not possible to obtain a (1+ε)-approximate subset selection algorithm even if one chooses any no(1) columns. This is the first algorithm of any kind for achieving a (1+ε)-approximation for entrywise ℓ1-norm loss low rank approximation.