Memory Limited, Streaming PCA

By Ioannis Mitliagkas, Constantine Caramanis, Prateek Jain. 2013

172 citations recorded by the source corpus.

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(p2) 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 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(p2). 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.

Subfields: Artificial Intelligence, Computational Mechanics, Statistics and Probability

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mechanics

In Statistics and Probability

Citations in the corpus

The Ideal Continual Learner: An Agent That Never Forgets (2023, methodology): “In this way, continual matrix factorization relates to streaming PCA (Mitliagkas et al., 2013; Peng & Risteski, 2022), incremental SVD (Bunch & Nielsen, 1978), and subspace tracking (Balzano et al.”
Fundamental Limits of Online and Distributed Algorithms for Statistical Learning and Estimation (2013, background): “[20, 7, 17, 13]), but these do not consider lower bounds or provable trade-offs.”
Privacy-Preserving Stochastic Gradual Learning (2018, background): “Second, in each iteration, it processes either a single point [12] or a tiny batch of points [13].”
Memory, Communication, and Statistical Queries (2016, background): “One more modest and practically relevant goal would be to provide an efficient memory-bounded algorithm for sparse regression without assumptions on the covariance structure.”
On the Convergence of a Family of Robust Losses for Stochastic Gradient Descent (2016, background): “Secondly, they only process a mini-batch of data points [1] or even one data point [2] in each iteration, which vastly reduces the memory storage.”
The Fast Convergence of Incremental PCA (2013, background): “There have been recent attempts to remedy this situation by relaxing the nonconvexity inherent in the problem [3] or making generative assumptions [8].”
Streaming PCA and Subspace Tracking: The Missing Data Case (2018, methodology): “One of the earlier works is [36], where the authors analyze a block variant of Oja’s method: within each iteration, multiple sample vectors are drawn, whose empirical covariance matrix is then used in place of xnxn in (37).”
Online Learning: A Comprehensive Survey (2018, background): “…have been focused on addressing online PCA for unsupervised learning on streaming data settings in literature (Warmuth and Kuzmin, 2008; Arora et al., 2013, 2012a; Mitliagkas et al., 2013; Feng et al., 2013), while there are also a few studies for online ICA (Li et al., 2016b; Wang and Lu, 2017).”
Streaming PCA: Matching Matrix Bernstein and Near-Optimal Finite Sample Guarantees for Oja's Algorithm (2016, methodology): “leviate this issue, a popular line of research over the past several decades has been to consider streaming algorithms for PCA under the assumption that the data has reasonable statistical properties [5, 6, 7, 8, 9]. There have been signiﬁcant breakthroughs in getting near-optimal streaming PCA algo”