Papers › Towards a Zero-One Law for Column Subset Selection
Towards a Zero-One Law for Column Subset Selection
Zhao Song, David P. Woodruff, Peilin Zhong
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_(rank-k B)‖A-B‖₁, or more generally finding a rank-k matrix B which minimizes the sum of p-th powers of absolute values of differences, min_(rank-k B)‖A-B‖ₚᵖ. Many of these algorithms are linear time columns subset selection algorithms, returning a subset of poly(k logn) 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:ℝ →ℝ_(≥0), find a rank-k matrix B which minimizes ‖A-B‖_g = ∑_(i,j)g(A_(i,j)-B_(i,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 every 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 ℓₚ-norms, e.g., one can show the lack of scale-invariance causes any column subset selection algorithm to provably require a √(logn) factor larger number of columns than ℓₚ-norms; nevertheless we design the first efficient column subset selection algorithms for such error measures.
In Syntology Open this paper in Syntology's Atlas, the map of the papers in Syntology's graph and their citations.
Code
Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.
Code Syntology ran Syntology
Not run by Syntology. Nothing on this page verifies that the listed code works.
Results from the paper archive 2025-07-28
No leaderboard rows for this paper in the archive.
Methods
Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections