Tropp, Joel A. and Yurtsever, Alp and Udell, Madeleine and Cevher, Volkan (2017) Randomized Single-View Algorithms for Low-Rank Matrix Approximation. ACM Technical Reports, 2017-01. California Institute of Technology , Pasadena, CA. (Unpublished) https://resolver.caltech.edu/CaltechAUTHORS:20170215-154809329
![]() |
PDF
- Submitted Version
See Usage Policy. 4MB |
Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20170215-154809329
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.
Item Type: | Report or Paper (Technical Report) | ||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|
ORCID: |
| ||||||||||||
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. | ||||||||||||
Group: | Applied & Computational Mathematics | ||||||||||||
Funders: |
| ||||||||||||
Subject Keywords: | Dimension reduction; matrix approximation; numerical linear algebra; randomized algorithm; single-pass algorithm; single-view algorithm; streaming algorithm; subspace embedding | ||||||||||||
Series Name: | ACM Technical Reports | ||||||||||||
Issue or Number: | 2017-01 | ||||||||||||
Classification Code: | AMS subject classifications. Primary, 65F30; Secondary, 68W20 | ||||||||||||
DOI: | 10.7907/Z9HT2M9C | ||||||||||||
Record Number: | CaltechAUTHORS:20170215-154809329 | ||||||||||||
Persistent URL: | https://resolver.caltech.edu/CaltechAUTHORS:20170215-154809329 | ||||||||||||
Usage Policy: | No commercial reproduction, distribution, display or performance rights in this work are provided. | ||||||||||||
ID Code: | 74347 | ||||||||||||
Collection: | CaltechACMTR | ||||||||||||
Deposited By: | Sydney Garstang | ||||||||||||
Deposited On: | 16 Feb 2017 00:17 | ||||||||||||
Last Modified: | 09 Mar 2020 13:19 |
Repository Staff Only: item control page