Speaker
Ilse Ipsen
(North Carolina State University)
Description
It is well known that the problem of selecting k columns with maximal volume from a real matrix is NP-hard, and does not admit a polynomial time approximation scheme. However, one can show that the logarithm of the volume is a "submodular" function. Intuitively, this means: Adding a new column to a larger submatrix tends to be less beneficial than adding it to a smaller submatrix.
If subset selection for maximizing the logarithmic volume is implemented via QR with column pivoting, we show that: The Businger Golub algorithm is a greedy algorithm with relative error at most .37, while the Gu-Eisenstat algorithm is a 1-interchange algorithm with relative error at most .5
Author
Ilse Ipsen
(North Carolina State University)
Co-author
Arvind Saibaba
(North Carolina State University)