MOSES: A Streaming Algorithm for Linear Dimensionality Reduction

Abstract

This paper introduces Memory-limited Online Subspace Estimation Scheme (MOSES) for both estimating the principal components of streaming data and reducing its dimension. More specifically, in various applications such as sensor networks, the data vectors are presented sequentially to a user who has limited storage and processing time available. Applied to such problems, MOSES can provide a running estimate of leading principal components of the data that has arrived so far and also reduce its dimension. MOSES generalises the popular incremental Singular Vale Decomposition (iSVD) to handle thin blocks of data, rather than just vectors. This minor generalisation in part allows us to complement MOSES with a comprehensive statistical analysis, thus providing the first theoretically-sound variant of iSVD, which has been lacking despite the empirical success of this method. This generalisation also enables us to concretely interpret MOSES as an approximate solver for the underlying non-convex optimisation program. We find that MOSES consistently surpasses the state of the art in our numerical experiments with both synthetic and real-world datasets, while being computationally inexpensive.

References in corpus (15)

• An overview of low-rank matrix recovery from incomplete observations
• The Noisy Power Method: A Meta Algorithm with Applications
• Memory Limited, Streaming PCA
• Sketched SVD: Recovering Spectral Features from Compressive Measurements
• Global Convergence of Stochastic Gradient Descent for Some Non-convex Matrix Problems
• A Distributed and Incremental SVD Algorithm for Agglomerative Data Analysis on Large Networks
• Global Convergence of a Grassmannian Gradient Descent Algorithm for Subspace Estimation
• The Fast Convergence of Incremental PCA
• Fixed-Rank Approximation of a Positive-Semidefinite Matrix from Streaming Data
• Robust Frequent Directions with Application in Online Learning
• What to Expect When You Are Expecting on the Grassmannian
• PCA by Optimisation of Symmetric Functions has no Spurious Local Optima
• Streaming Principal Component Analysis From Incomplete Data
• PCA by Determinant Optimization has no Spurious Local Optima
• Quantifying the Estimation Error of Principal Components

Cited by in corpus (3)

• Federated Principal Component Analysis
• Dynamic mode decomposition of magnetohydrodynamic bubble chain flow in a rectangular vessel
• Training Linear Neural Networks: Non-Local Convergence and Complexity Results