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 -