Fast and Simple PCA via Convex Optimization

Dan Garber, Elad Hazan

Published 2015-09-18Version 1

The problem of principle component analysis (PCA) is traditionally solved by spectral or algebraic methods. We show how PCA could be formulated as a sequence of {\it convex} optimization problems. This gives rise to a new efficient method for computing the PCA based on recent advances in stochastic methods for convex optimization. In particular, we present running times that improve over the current state-of-the-art.