Rectangular maximum-volume submatrices and their applications

Aleksandr Mikhalev, I.V. Oseledets

Research output: Contribution to journalArticlepeer-review

32 Scopus citations

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 languageEnglish (US)
Pages (from-to)187-211
Number of pages25
JournalLinear Algebra and Its Applications
Volume538
DOIs
StatePublished - Oct 18 2017

Bibliographical note

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.

Fingerprint

Dive into the research topics of 'Rectangular maximum-volume submatrices and their applications'. Together they form a unique fingerprint.

Cite this