Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published December 6, 2017 | Submitted + Published + Supplemental Material
Journal Article Open

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.

Additional Information

© 2017, Society for Industrial and Applied Mathematics. Submitted: 17 January 2017. Accepted: 18 August 2017. Published online: 06 December 2017. The work of the first and third authors was supported in part by ONR award N00014-11-1002 and the Gordon & Betty Moore Foundation. The work of the third author was also supported in part by DARPA award FA8750-17-2-0101. The work of the second and fourth authors was supported in part by the European Commission under the ERC Future Proof grant and grants SNF 200021-146750, and SNF CRSII2-147633.

Attached Files

Submitted - 1609.00048.pdf

Published - 17m1111590.pdf

Supplemental Material - M111159_01.zip


Files (1.5 MB)
Name Size Download all
939.7 kB Preview Download
502.0 kB Preview Download
80.2 kB Preview Download

Additional details

September 15, 2023
September 15, 2023