Revisiting column subset selection through the lens of submodularity
arXiv:2607.13823
The paper shows that the logarithm of the volume of a set of matrix columns is a submodular function, allowing classic QR with column pivoting to be viewed as a greedy algorithm with provable error bounds for column subset selection and related matrix volume problems.
Abstract
The problem is to select k columns with maximal volume from a real mxn matrix X. We show that the logarithm of the volume is a set submodular function on columns of X, and for full column-rank matrices X with sufficiently large singular values, it is a non-negative non-decreasing function. As a consequence, traditional Businger-Golub QR with column pivoting is a greedy algorithm, with a relative error of at most 37 percent. In contrast, Gu-Eisenstat strong rank-revealing QR is a 1-interchange algorithm, with a relative error of at most 50 percent. The higher accuracy, under this metric, of the simple QR with column pivoting confirms its well known effectiveness in practice. For general, possibly rank-deficient matrices, we derive probabilistic bounds for the absolute error based on a smoothed analysis. The above analyses are extended to finding kxk submatrices of maximal volume in symmetric positive-definite matrices.