Memory Limited, Streaming PCA
Talkat Workshop on Succinct Data Representations and Applications (Simons Institute Big Data 2013) · 2013-09-16..09-19·
summary
Algorithm recovers the top principal component in the Gaussian spiked identity model using a streaming power method that never forms the p×p covariance and stores two vectors only. It breaks data into ~log p blocks, multiplicatively updates with block empirical covariances, and needs about O(p log p) samples (with extra 1/q^2 factor under coordinate erasures). Analysis gives rates after the initial phase caused by a random start; simulations show it works.
AI-written summary · about
chapters (9)
- 0:00Introduction and motivation
- 1:30Spiked covariance model
- 5:33Memory complexity constraints
- 9:29Distributed PCA challenges
- 11:47Review of existing techniques
- 16:57Stochastic gradient approach
- 24:05Streaming power method
- 28:21Extensions and conclusions
- 34:05Q&A session
related talks
28mRandomized Constrained Matrix Decompositions
01h 31mUnsupervised Learning
52mIndependent Component Analysis: From Theory to Practice and Back
01h 02mLarge-Scale Private Learning, Part I
47mA Statistical Model for Tensor Principal Component Analysis
34mFree Energy Wells and Overlap Gap Property in Sparse PCA
49mRobust PCA via Non-convex Methods: Provable Bounds
36mBootstrapping The Error Of Oja’S Algorithm