{"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","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-07-15","reactions":{}}