  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}$.
