A Caltech Library Service

More practical sketching algorithms for low-rank matrix approximation

Tropp, Joel A. and Yurtsever, Alp and Udell, Madeleine and Cevher, Volkan (2018) More practical sketching algorithms for low-rank matrix approximation. ACM Technical Reports, 2018-01. California Institute of Technology , Pasadena, CA. (Unpublished)

[img] PDF - Accepted Version
See Usage Policy.


Use this Persistent URL to link to this item:


This paper describes new algorithms for constructing a low-rank approximation of an input matrix from a sketch, a random low-dimensional linear image of the matrix. These algorithms come with rigorous performance guarantees. Empirically, the proposed methods achieve significantly smaller relative errors than other approaches that have appeared in the literature. For a concrete application, the paper outlines how the algorithms support on-the-fly compression of data from a direct Navier-Stokes (DNS) simulation.

Item Type:Report or Paper (Technical Report)
Tropp, Joel A.0000-0003-1024-1791
Udell, Madeleine0000-0002-3985-915X
Additional Information:First draft: 22 March 2017. First release: 16 July 2018. JAT was supported in part by ONR Awards N00014-11-1002, N00014-17-1-214, N00014-17-1-2146, and the Gordon & Betty Moore Foundation. MU was supported in part by DARPA Award FA8750-17-2-0101. VC has received funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme under the grant agreement number 725594 (time-data) and the Swiss National Science Foundation (SNSF) under the grant number 200021_178865. The authors wish to thank Beverley McKeon and Sean Symon for providing DNS simulation data and visualization software. William North contributed the weather data.
Group:Applied & Computational Mathematics
Funding AgencyGrant Number
Office of Naval Research (ONR)N00014-11-1002
Office of Naval Research (ONR)N00014-17-1-214
Office of Naval Research (ONR)N00014-17-1-2146
Gordon and Betty Moore FoundationUNSPECIFIED
Defense Advanced Research Projects Agency (DARPA)FA8750-17-2-0101
European Research Council (ERC)725594
Swiss National Science Foundation (SNSF)200021_178865
Subject Keywords:Dimension reduction; matrix approximation; numerical linear algebra; randomized algorithm; single-pass algorithm; sketching; streaming algorithm; subspace embedding
Series Name:ACM Technical Reports
Issue or Number:2018-01
Classification Code:AMS subject classifications. Primary, 65F30; Secondary, 68W20
Record Number:CaltechAUTHORS:20220826-183609942
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:116589
Deposited By: George Porter
Deposited On:26 Aug 2022 19:42
Last Modified:26 Aug 2022 20:51

Repository Staff Only: item control page