Stochastic Approximation Algorithms for Principal Component Analysis
  Principal Component Analysis is a novel way of of dimensionality reduction.
This problem essentially boils down to finding the top k eigen vectors of the
data covariance matrix. A considerable amount of literature is found on
algorithms meant to do so such as an online method be Warmuth and Kuzmin,
Matrix Stochastic Gradient by Arora, Oja's method and many others. In this
paper we see some of these stochastic approaches to the PCA optimization
problem and comment on their convergence and runtime to obtain an epsilon
sub-optimal solution. We revisit convex relaxation based methods for stochastic
optimization of principal component analysis. While methods that directly solve
the non convex problem have been shown to be optimal in terms of statistical
and computational efficiency, the methods based on convex relaxation have been
shown to enjoy comparable, or even superior, empirical performance. This
motivates the need for a deeper formal understanding of the latter.
