Revisiting column subset selection through the lens of submodularity
Provides theoretical justification for the practical effectiveness of a classic algorithm (QR with column pivoting) in column subset selection, benefiting researchers and practitioners in numerical linear algebra and machine learning.
The paper shows that the logarithm of the volume of a matrix is a submodular function, proving that Businger-Golub QR with column pivoting is a greedy algorithm with a relative error of at most 37%, outperforming Gu-Eisenstat strong rank-revealing QR which has a 50% error bound.
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 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 matrices, we show that Businger-Golub QR is a greedy algorithm, and Gu-Eisenstat QR a 1-interchange algorithm for maximizing the trace of the upper triangular matrix in a QR factorization of X, with Businger-Golub again having a better error bound. This is extended to finding kxk submatrices of maximal volume in symmetric positive-definite matrices.