Fast and Simple PCA via Convex Optimization

By Dan Garber, Elad Hazan. 2015

92 citations recorded by the source corpus.

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

Subfields: Artificial Intelligence, Computational Mechanics, Signal Processing

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mechanics

In Signal Processing

Citations in the corpus

SGD: General Analysis and Improved Rates (2019, neutral): “In the last experiment (Section 6.3) we focus on the problem of principal component analysis (PCA) which by construction can be seen as a problem with a strongly convex objective f but with non-convex functions f i (Allen-Zhu & Yuan, 2016; Garber & Hazan, 2015; Shalev-Shwartz, 2016).”
Katyusha: the first direct acceleration of stochastic gradient methods (2016, methodology): “1) also lead to fast algorithms for neural nets [2, 20] as well as SVD, PCA, and CCA [4, 5, 17].”
Streaming PCA: Matching Matrix Bernstein and Near-Optimal Finite Sample Guarantees for Oja's Algorithm (2016, methodology): “Finally, (Shamir, 2015a; Garber and Hazan, 2015; Jin et al., 2015) also provide methods for eigenvector computation, but they require multiple passes over the data and hence do not apply to the streaming setting.”
Second Order Stochastic Optimization in Linear Time (2016, methodology): “We note that the idea of applying SVRG as a sub-routine to achieve better guarantees have also recently been used in developing faster algorithms for PCA [GH15, Sha15].”
Improved SVRG for Non-Strongly-Convex or Sum-of-Non-Convex Objectives (2015, methodology): “Our improvement on SVRG immediately leads to faster stochastic algorithms for PCA [6, 24].”
Follow the Compressed Leader: Faster Online Learning of Eigenvectors and Faster MMWU (2017, methodology): “Most notably, Garber, Hazan and Ma (Garber et al., 2015) proposed to compute an (approximate) leading eigenvector of the matrix Σk−1 + rr> at iteration k, where r is a random vector whose norm is around √ dT .”
Stochastic Chebyshev Gradient Descent for Spectral Optimization (2018, methodology): “For notational simplicity, we denote The remaining part mimics the analysis of [10].”
Communication-efficient Algorithms for Distributed Stochastic Principal Component Analysis (2017, unknown): “Indeed, we show that already for the PCA problem with k = 1, simply averaging the local ERM solutions (and normalizing to obtain a unit vector as required), cannot improve significantly over the estimation error of any single machine.”
Variance Reduction for Faster Non-Convex Optimization (2016, background): “Even in the case when f ( ) is convex but each f i ( ) is non-convex, the problem (1.1) can be solved easily [10, 23].”