Abstract
We introduce a definition of the volume of a general rectangular matrix, which is equivalent to an absolute value of the determinant for square matrices. We generalize results of square maximum-volume submatrices to the rectangular case, show a connection of the rectangular volume with an optimal experimental design and provide estimates for a growth of coefficients and an approximation error in spectral and Chebyshev norms. Three promising applications of such submatrices are presented: recommender systems, finding maximal elements in low-rank matrices and preconditioning of overdetermined linear systems. The code is available online.
Original language | English (US) |
---|---|
Pages (from-to) | 187-211 |
Number of pages | 25 |
Journal | Linear Algebra and Its Applications |
Volume | 538 |
DOIs | |
State | Published - Oct 18 2017 |
Bibliographical note
KAUST Repository Item: Exported on 2020-10-01Acknowledgements: Work on the problem setting and numerical examples was supported by Russian Foundation for Basic Research grant 16-31-60095 mol_a_dk. Work on theoretical estimations of approximation error and the practical algorithm was supported by Russian Foundation for Basic Research grant 16-31-00351 mol_a.