The problem of principle component analysis (PCA) is traditionally solved by spectral or algebraic methods. We show how computing the leading principal component could be reduced to solving a \textit{ small} number of well-conditioned { \it convex} optimization problems. This gives rise to a new efficient method for PCA based on recent advances in stochastic methods for convex optimization. In particular we show that given a $d\times d$ matrix $\X = \frac{ 1}{ n}\sum_{ i=1}^n\x_i\x_i^{ \top}$ with top eigenvector $\u$ and top eigenvalue $\lambda_1$ it is possible to: \begin{ itemize} \item compute a unit vector $\w$ such that $(\w^{ \top}\u)^2 \geq 1-\epsilon$ in $\tilde{ O}\left({ \frac{ d}{ \delta^2}+N}\right)$ time, where $\delta = \lambda_1 - \lambda_2$ and $N$ is the total number of non-zero entries in $\x_1,...,\x_n$, \item compute a unit vector $\w$ such that $\w^{ \top}\X\w \geq \lambda_1-\epsilon$ in $\tilde{ O}(d/\epsilon^2)$ time. \end{ itemize} To the best of our knowledge, these bounds are the fastest to date for a wide regime of parameters. These results could be further accelerated when $\delta$ (in the first case) and $\epsilon$ (in the second case) are smaller than $\sqrt{ d/N}$.
Categories: math.OC cs.LG cs.NA math.NA