# Towards a Zero-One Law for Column Subset Selection

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

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 4 Nov 2018.

## 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)
- [Solving Attention Kernel Regression Problem via Pre-conditioner](https://mlsanity.com/paper/2308.14304/) (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)
- [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)
- [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)

There are a number of approximation algorithms for NP-hard versions of low rank approximation, such as finding a rank-k matrix B minimizing the sum of absolute values of differences to a given n-by-n matrix A, min_textrmrank-k~B|A-B|1, or more generally finding a rank-k matrix B which minimizes the sum of p-th powers of absolute values of differences, min_textrmrank-k~B|A-B|pp. Many of these algorithms are linear time columns subset selection algorithms, returning a subset of poly(k log n) columns whose cost is no more than a poly(k) factor larger than the cost of the best rank-k matrix. The above error measures are special cases of the following general entrywise low rank approximation problem: given an arbitrary function g:ℝ rightarrow ℝ≥ 0, find a rank-k matrix B which minimizes |A-B|g = sumi,jg(Ai,j-Bi,j). A natural question is which functions g admit efficient approximation algorithms? Indeed, this is a central question of recent work studying generalized low rank models. In this work we give approximation algorithms for textitevery function g which is approximately monotone and satisfies an approximate triangle inequality, and we show both of these conditions are necessary. Further, our algorithm is efficient if the function g admits an efficient approximate regression algorithm. Our approximation algorithms handle functions which are not even scale-invariant, such as the Huber loss function, which we show have very different structural properties than ℓp-norms, e.g., one can show the lack of scale-invariance causes any column subset selection algorithm to provably require a √log n factor larger number of columns than ℓp-norms; nevertheless we design the first efficient column subset selection algorithms for such error measures.