Memory Limited, Streaming PCA
We consider streaming, one-pass principal component analysis (PCA), in the highdimensional 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 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) samplecomplexity -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.
Summary: proposes an approach to one-pass SVD 
      based on a blocked variant of the power method, which variance is reduced 
      within each block of streaming data, and compares to exact batch SVD. 
      Figure 1d is offered as an example where the proposed Algo 1 can scale 
      to data for which the authors claim to be so large that "traditional batch 
      methods" could not be run and reported. Yet there are many existing 
      well-known SVD methods which are routinely used for even larger data sets 
      than the largest here (sparse 8.2M vectors for 120k dimensions). These 
      include the EMPCA (Roweiss 1998) and fast randomized SVD (Haiko et at 
      2011), both of which the author's cite. Why were these methods (both very 
      simple to implement efficiently even in Matlab, etc.) not reported for 
      this data? Especially necessary to compare against is the randomized SVD, 
      since it too can be done in one-pass (see Haiko et al); although that 
      cited paper discusses the tradeoffs in doing multiple passes -- something 
      this paper does not even discuss. The authors say it took "a few hours" 
      for Algo 1 to extract the top 7 components. Methods like the randomized 
      SVD family of Haiko et al scale linearly in those parameters (n=8.2M and 
      d=120k and k=7 and the number of non-zeros of the sparse data) and 
      typically run in less than 1 hour for even larger data sets. So, 
      demonstrating both the speed and accuracy of the proposed Algo 1 compared 
      to the randomized algorithms seems necessary at this point, to establish 
      the practical significance of this proposed approach. Even though 
      the paper argues that previous approaches do not have "finite sample 
      guarantees", this does not excuse them from having to demonstrate that 
      their approach is actually better in practice than existing methods. As 
      written, this paper basically presents yet another way to do SVD, for 
      which there are already many existing methods, including streaming 
      one-pass methods (such as the above mentioned randomized SVD). 
      Also, the focus on spiked covariance models in the theory parts of 
      this paper is confusing. What is the point of proving finite sample 
      complexity results for that case, but then failing to compare to existing 
      state of the art methods (like EMPCA and randomized SVD) for data (like 
      PubMed) which does not fall into the spiked covariance type of data?