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. ACM Technical Reports, 2017-03. California Institute of Technology , Pasadena, CA. (Unpublished) https://resolver.caltech.edu/CaltechAUTHORS:20170620-081901312

[img] 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:
URLURL TypeDescription
http://users.cms.caltech.edu/~jtropp/reports/TYUC17-Fixed-Rank-Approximation-TR.pdfAuthorReport
http://resolver.caltech.edu/CaltechAUTHORS:20180829-073029156Related ItemDiscussion Paper
ORCID:
AuthorORCID
Tropp, Joel A.0000-0003-1024-1791
Udell, Madeleine0000-0002-3985-915X
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