Id: arxiv/2607.13823 Url: https://arxiv.org/abs/2607.13823 Tags: math.NA Score: 0 Title: Revisiting column subset selection through the lens of submodularity Domain: math.NA Source: arxiv Authors: Ilse C. F. Ipsen, Arvind K. Saibaba Reviews: 0 Subject: math.NA Category: research Comments: 0 Disputed: false Division: math Mentions: 0 Discussed: 0 Published: 2026-07-15 Page: https://delphi.science/r/arxiv/2607.13823 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…