Memory Limited, Streaming PCA

Abstract

We consider streaming, one-pass principal component analysis (PCA), in the high-dimensional regime, with limited memory. Here, $p$-dimensional samples are presented sequentially, and the goal is to produce the $k$-dimensional subspace that best approximates these points. Standard algorithms require $O(p^2)$ memory; meanwhile no algorithm can do better than $O(kp)$ memory, since this is what the output itself requires. Memory (or storage) complexity is most meaningful when understood in the context of computational and sample complexity. Sample complexity for high-dimensional PCA is typically studied in the setting of the {\em spiked covariance model}, where $p$-dimensional points are generated from a population covariance equal to the identity (white noise) plus a low-dimensional perturbation (the spike) which is the signal to be recovered. It is now well-understood that the spike can be recovered when the number of samples, $n$, scales proportionally with the dimension, $p$. Yet, all algorithms that provably achieve this, have memory complexity $O(p^2)$. Meanwhile, algorithms with memory-complexity $O(kp)$ do not have provable bounds on sample complexity comparable to $p$. We present an algorithm that achieves both: it uses $O(kp)$ memory (meaning storage of any kind) and is able to compute the $k$-dimensional spike with $O(p\log p)$ sample-complexity -- the first algorithm of its kind. While our theoretical analysis focuses on the spiked covariance model, our simulations show that our algorithm is successful on much more general models for the data.

Cited by in corpus (25)

• The Noisy Power Method: A Meta Algorithm with Applications
• On-Device Machine Learning: An Algorithms and Learning Theory Perspective
• Finding Linear Structure in Large Datasets with Scalable Canonical Correlation Analysis
• Federated Principal Component Analysis
• Fixed-Rank Approximation of a Positive-Semidefinite Matrix from Streaming Data
• Indefinite Kernel Logistic Regression with Concave-inexact-convex Procedure
• Subspace Estimation from Incomplete Observations: A High-Dimensional Analysis
• Streaming Batch Eigenupdates for Hardware Neuromorphic Networks
• Federated Over-Air Subspace Tracking from Incomplete and Corrupted Data
• MOSES: A Streaming Algorithm for Linear Dimensionality Reduction
• Streaming, Memory Limited Algorithms for Community Detection
• Affine Invariant Covariance Estimation for Heavy-Tailed Distributions
• Streaming, Memory Limited Matrix Completion with Noise
• Momentum-based variance-reduced proximal stochastic gradient method for composite nonconvex stochastic optimization
• On the Regret Minimization of Nonconvex Online Gradient Ascent for Online PCA
• Memory-efficient training with streaming dimensionality reduction
• Blind calibration for compressed sensing: State evolution and an online algorithm
• Embedding Principal Component Analysis for Data Reductionin Structural Health Monitoring on Low-Cost IoT Gateways
• Convergence Rate of Krasulina Estimator
• Bootstrapping the error of Oja's algorithm
• AgFlow: Fast Model Selection of Penalized PCA via Implicit Regularization Effects of Gradient Flow
• Stochastic Approximation Algorithms for Principal Component Analysis
• Practical and Fast Momentum-Based Power Methods
• Pronto: Federated Task Scheduling
• Kernel Discrepancy-Based Rerandomization for Controlled Experiments