CaltechAUTHORS
  A Caltech Library Service

Fixed-Rank Approximation of a Positive-Semidefinite Matrix from Streaming Data

Tropp, Joel A. and Yurtsever, Alp and Udell, Madeleine and Cevher, Volkan (2017) Fixed-Rank Approximation of a Positive-Semidefinite Matrix from Streaming Data. In: 31st Conference on Neural Information Processing Systems (NIPS 2017), 4-9 December 2017, Long Beach, CA. https://resolver.caltech.edu/CaltechAUTHORS:20180829-073029156

[img] PDF - Published Version
See Usage Policy.

455kB
[img] PDF - Submitted Version
See Usage Policy.

1MB

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20180829-073029156

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:Conference or Workshop Item (Paper)
Related URLs:
URLURL TypeDescription
https://arxiv.org/abs/1706.05736arXivDiscussion Paper
http://resolver.caltech.edu/CaltechAUTHORS:20170620-081901312Related ItemTechnical Report
https://nips.cc/Conferences/2017OrganizationConference Website
ORCID:
AuthorORCID
Tropp, Joel A.0000-0003-1024-1791
Udell, Madeleine0000-0002-3985-915X
Additional Information:The authors wish to thank Mark Tygert and Alex Gittens for helpful feedback on preliminary versions of this work. JAT gratefully acknowledges partial support from ONR Award N00014-17-1-2146 and the Gordon & Betty Moore Foundation. VC and AY were supported in part by the European Commission under Grant ERC Future Proof, SNF 200021-146750, and SNF CRSII2-147633. MU was supported in part by DARPA Award FA8750-17-2-0101.
Funders:
Funding AgencyGrant Number
Office of Naval Research (ONR)N00014-17-1-2146
Gordon and Betty Moore FoundationUNSPECIFIED
European CommissionSNF 200021-146750
European CommissionSNF CRSII2-147633
Defense Advanced Research Projects Agency (DARPA)FA8750-17-2-0101
DOI:10.48550/arXiv.1706.05736
Record Number:CaltechAUTHORS:20180829-073029156
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:20180829-073029156
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:89267
Collection:CaltechAUTHORS
Deposited By: Tony Diaz
Deposited On:29 Aug 2018 16:45
Last Modified:02 Jun 2023 00:34

Repository Staff Only: item control page