TY - JOUR

T1 - Rectangular maximum-volume submatrices and their applications

AU - Mikhalev, Aleksandr

AU - Oseledets, I.V.

N1 - KAUST Repository Item: Exported on 2020-10-01
Acknowledgements: 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.

PY - 2017/10/18

Y1 - 2017/10/18

N2 - 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.

AB - 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.

UR - http://hdl.handle.net/10754/625919

UR - http://www.sciencedirect.com/science/article/pii/S0024379517305931

UR - http://www.scopus.com/inward/record.url?scp=85032201215&partnerID=8YFLogxK

U2 - 10.1016/j.laa.2017.10.014

DO - 10.1016/j.laa.2017.10.014

M3 - Article

SN - 0024-3795

VL - 538

SP - 187

EP - 211

JO - Linear Algebra and Its Applications

JF - Linear Algebra and Its Applications

ER -