CaltechAUTHORS
  A Caltech Library Service

Randomized Single-View Algorithms for Low-Rank Matrix Approximation

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) http://resolver.caltech.edu/CaltechAUTHORS:20170215-154809329

[img] PDF - Submitted Version
See Usage Policy.

4Mb

Use this Persistent URL to link to this item: http://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:
AuthorORCID
Tropp, Joel A.0000-0003-1024-1791
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:
Funding AgencyGrant Number
Office of Naval Research (ONR)N00014-11-1002
Gordon and Betty Moore FoundationUNSPECIFIED
European Research Council (ERC)Future Proof
Swiss National Fund (SNF)200021-146750
Swiss National Fund (SNF)CRSII2-147633
Subject Keywords:Dimension reduction; matrix approximation; numerical linear algebra; randomized algorithm; single-pass algorithm; single-view algorithm; streaming algorithm; subspace embedding
Classification Code:AMS subject classifications. Primary, 65F30; Secondary, 68W20
DOI:10.7907/Z9HT2M9C
Record Number:CaltechAUTHORS:20170215-154809329
Persistent URL:http://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:16 Feb 2017 15:38

Repository Staff Only: item control page