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)

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


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)
Tropp, Joel A.0000-0003-1024-1791
Udell, Madeleine0000-0002-3985-915X
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
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
Series Name:ACM Technical Reports
Issue or Number:2017-01
Classification Code:AMS subject classifications. Primary, 65F30; Secondary, 68W20
Record Number:CaltechAUTHORS:20170215-154809329
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:74347
Deposited By: Sydney Garstang
Deposited On:16 Feb 2017 00:17
Last Modified:09 Mar 2020 13:19

Repository Staff Only: item control page