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) https://resolver.caltech.edu/CaltechAUTHORS:20220826-183609942
![]() |
PDF
- Accepted Version
See Usage Policy. 3MB |
Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20220826-183609942
Abstract
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) | ||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
ORCID: |
| ||||||||||||||||
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 | ||||||||||||||||
Funders: |
| ||||||||||||||||
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 | ||||||||||||||||
DOI: | 10.7907/bb7w-ve61 | ||||||||||||||||
Record Number: | CaltechAUTHORS:20220826-183609942 | ||||||||||||||||
Persistent URL: | https://resolver.caltech.edu/CaltechAUTHORS:20220826-183609942 | ||||||||||||||||
Usage Policy: | No commercial reproduction, distribution, display or performance rights in this work are provided. | ||||||||||||||||
ID Code: | 116589 | ||||||||||||||||
Collection: | CaltechACMTR | ||||||||||||||||
Deposited By: | George Porter | ||||||||||||||||
Deposited On: | 26 Aug 2022 19:42 | ||||||||||||||||
Last Modified: | 26 Aug 2022 20:51 |
Repository Staff Only: item control page