Loading...
research article
Practical Sketching Algorithms For Low-Rank Matrix Approximation
This paper describes a suite of algorithms for constructing low-rank approximations of an input matrix from a random linear image, or sketch, of the matrix. These methods can preserve structural properties of the input matrix, such as positive-semidefiniteness, and they can produce approximations with a user-specified rank. The algorithms are simple, accurate, numerically stable, and provably correct. Moreover, each method is accompanied by an informative error bound that allows users to select parameters a priori to achieve a given approximation quality. These claims are supported by numerical experiments with real and synthetic data.
Type
research article
Web of Science ID
WOS:000418665600017
Authors
Publication date
2017
Published in
Volume
38
Issue
4
Start page
1454
End page
1485
Peer reviewed
REVIEWED
EPFL units
Available on Infoscience
January 15, 2018
Use this identifier to reference this record