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 Nystrom 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.

References in corpus (3)

• Sketchy Decisions: Convex Low-Rank Matrix Optimization with Optimal Storage
• Sketched SVD: Recovering Spectral Features from Compressive Measurements
• Dimensionality Reduction of Massive Sparse Datasets Using Coresets

Cited by in corpus (12)

• Scalable Kernel K-Means Clustering with Nystrom Approximation: Relative-Error Bounds
• Rapid Robust Principal Component Analysis: CUR Accelerated Inexact Low Rank Estimation
• Improved Fixed-Rank Nyström Approximation via QR Decomposition: Practical and Theoretical Aspects
• Fast and stable randomized low-rank matrix approximation
• MOSES: A Streaming Algorithm for Linear Dimensionality Reduction
• Perturbations of CUR Decompositions
• Range-Net: A High Precision Streaming SVD for Big Data Applications
• Simple and Almost Assumption-Free Out-of-Sample Bound for Random Feature Mapping
• CUR Decompositions, Approximations, and Perturbations
• Simpler is better: A comparative study of randomized algorithms for computing the CUR decomposition
• Provable Exactness for Asymmetric Low-Rank SDP Learning
• Approximate Cross-Validation with Low-Rank Data in High Dimensions