Stochastic Optimization of PCA with Capped MSG
We study PCA as a stochastic optimization problem and propose a novel stochastic approximation algorithm which we refer to as "Matrix Stochastic Gradient" (MSG), as well as a practical variant, Capped MSG. We study the method both theoretically and empirically.
This paper explores online stochastic approximation 
      algorithms for PCA. The authors provide a few apparently novel 
      suggestions and heuristics that extend existing methods. However, the 
      main contribution here is really about unifying and elucidating the 
      disparate perspectives taken in the literature, and analyzing common 
      approaches to online PCA. The paper is careful, well-written and clear, 
      however it is as if the authors had four or five smaller, somewhat 
      unrelated results they decided to tie together under the rather broad 
      banner of 'Matrix stochastic gradient for PCA' and related concepts. As 
      such, the discussion could benefit from further effort devoted to 
      connecting the various pieces into a coherent whole. Having said 
      this, the points made in this paper, even if disjoint at times, are 
      important ones, and moreover can be hard to piece together from the 
      literature without significant effort. The authors have absorbed some (but 
      by no means all -- see comments below) of the relevant work, and have 
      pointed out commonalities, differences, subtleties, and a few low-hanging 
      improvements. This, in my opinion, is valuable enough to make up for the 
      paper's shortcomings. As noted above, the authors are careful, and provide 
      a bit of theory in a language and setting that is probably much easier to 
      digest compared to what may be found in the references (which may be 
      comprehensive, but require a greater time investment to get the "gist" of 
      the proofs and the behavior of the algorithms). Other comments: 
      - In the introduction it is implied that taking a population approach 
      is something of fundamental innovation offered by the paper. That is a 
      stretch. In the end, we're still talking about online PCA, and calling 
      it by another name doesn't appear to offer any concrete, substantive 
      additions to the conversation. - The abstract claims that Eq (3.3) is 
      "novel", however working with the projection matrix rather than the 
      matrix of eigenvectors is common, and may even be viewed as an 
      alternative representation of the Grassmann manifold. This equation, and 
      others, probably overlap quite substantially with the approaches taken 
      in e.g. + "Optimization Algorithms on Matrix Manifolds" by Absil, P., 
      Mahony, R., Sepulchre, R. ( this reference also addresses more general 
      gradient flows, stepsize, retraction ("projection"), and convergence 
      issues). + S. Bonnabel, "Stochastic gradient descent on Riemannian 
      manifolds" (arXiv) + A. Edelman et al. "THE GEOMETRY OF ALGORITHMS 
      WITH ORTHOGONALITY CONSTRAINTS" - The perspective of gradient descent 
      on matrix manifolds is, to this reviewer, a major omission. The paper 
      could greatly benefit from a discussion as to how this slice of the 
      literature fits in to the picture, in terms of both practical algorithms 
      and theory. I understand that space is a constraint. But if the authors 
      decide to ultimately write a journal version of the submission, careful, 
      considered inclusion of the above would make for a fantastic, 
      authoritative paper bridging all of the major points of view on the topic. 
      - In light of the above references, a "theoretical understanding" of 
      the power method may not be so elusive after all! (statement at line 100) 
      - Can the projection step also be derived using standard tools from 
      proximal methods? - The experiments are well chosen to reveal the 
      behavior of the algorithms in question. - If the principal components 
      are needed after all is said and done, do you include anywhere the cost of 
      computing the factorization M=UU'?