Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published June 21, 2017 | Submitted
Report Open

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

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.

Attached Files

Submitted - ACM_TR_2017_03.pdf

Files

ACM_TR_2017_03.pdf
Files (727.3 kB)
Name Size Download all
md5:13737acc92877ca5598931862bbec568
727.3 kB Preview Download

Additional details

Created:
August 19, 2023
Modified:
January 13, 2024