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 February 16, 2017 | Submitted
Report Open

Randomized Single-View Algorithms for Low-Rank Matrix Approximation

Abstract

This paper develops a suite of algorithms for constructing low-rank approximations of an input matrix from a random linear image of the matrix, called a sketch. 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 computer experiments.

Additional Information

JAT and MU were supported in part by ONR Award N00014-11-1002 and the Gordon & Betty Moore Foundation. AY and VC were supported in part by the European Commission under Grant ERC Future Proof, SNF 200021-146750, and SNF CRSII2-147633. The authors would like to thank Gunnar Martinsson and Mark Tygert for helpful conversations.

Attached Files

Submitted - ACM_TR_2017_01.pdf

Files

ACM_TR_2017_01.pdf
Files (4.6 MB)
Name Size Download all
md5:3510c27c5f4f9794b647c74b1fa30423
4.6 MB Preview Download

Additional details

Created:
August 22, 2023
Modified:
January 13, 2024