Tropp, Joel A. and Yurtsever, Alp and Udell, Madeleine and Cevher, Volkan (2017) Fixed-Rank Approximation of a Positive-Semidefinite Matrix from Streaming Data. ACM Technical Reports, 2017-03. California Institute of Technology , Pasadena, CA. (Unpublished) https://resolver.caltech.edu/CaltechAUTHORS:20170620-081901312
![]() |
PDF
- Submitted Version
See Usage Policy. 727kB |
Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20170620-081901312
Abstract
Several important applications, such as streaming PCA and semidefinite programming, involve a large-scale positive-semidefinite (psd) matrix that is presented as a sequence of linear updates. Because of storage limitations, it may only be possible to retain a sketch of the psd matrix. This paper develops a new algorithm for fixed-rank psd approximation from a sketch. The approach combines the Nyström approximation with a novel mechanism for rank truncation. Theoretical analysis establishes that the proposed method can achieve any prescribed relative error in the Schatten 1-norm and that it exploits the spectral decay of the input matrix. Computer experiments show that the proposed method dominates alternative techniques for fixed-rank psd matrix approximation across a wide range of examples.
Item Type: | Report or Paper (Technical Report) | |||||||||
---|---|---|---|---|---|---|---|---|---|---|
Related URLs: |
| |||||||||
ORCID: |
| |||||||||
Group: | Applied & Computational Mathematics | |||||||||
Series Name: | ACM Technical Reports | |||||||||
Issue or Number: | 2017-03 | |||||||||
DOI: | 10.7907/QJE2-RP11 | |||||||||
Record Number: | CaltechAUTHORS:20170620-081901312 | |||||||||
Persistent URL: | https://resolver.caltech.edu/CaltechAUTHORS:20170620-081901312 | |||||||||
Usage Policy: | No commercial reproduction, distribution, display or performance rights in this work are provided. | |||||||||
ID Code: | 78360 | |||||||||
Collection: | CaltechACMTR | |||||||||
Deposited By: | Sydney Garstang | |||||||||
Deposited On: | 21 Jun 2017 20:58 | |||||||||
Last Modified: | 09 Mar 2020 13:19 |
Repository Staff Only: item control page