Memory Limited, Streaming PCA
  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.
