Revisiting column subset selection through the lens of submodularity

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.