Fast and Simple PCA via Convex Optimization

Abstract

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-ε$ 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 λ_1-ε$ 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}$.

References in corpus (6)

• A Stochastic Gradient Method with an Exponential Convergence Rate for Finite Training Sets
• A Universal Catalyst for First-Order Optimization
• SDCA without Duality
• Fast Stochastic Algorithms for SVD and PCA: Convergence Properties and Convexity
• PCA with Gaussian perturbations
• Spectral Smoothing via Random Matrix Perturbations

Cited by in corpus (32)

• Variance Reduction for Faster Non-Convex Optimization
• Riemannian stochastic variance reduced gradient algorithm with retraction and vector transport
• Near-Optimal Stochastic Approximation for Online Principal Component Estimation
• Second-Order Stochastic Optimization for Machine Learning in Linear Time
• SGD: General Analysis and Improved Rates
• Faster Eigenvector Computation via Shift-and-Invert Preconditioning
• A Practical Method for Constructing Equivariant Multilayer Perceptrons for Arbitrary Matrix Groups
• Communication-efficient Algorithms for Distributed Stochastic Principal Component Analysis
• Stochastic Variance-Reduced Cubic Regularized Newton Method
• Doubly Accelerated Methods for Faster CCA and Generalized Eigendecomposition
• Stochastic Canonical Correlation Analysis
• Stochastic Recursive Variance-Reduced Cubic Regularization Methods
• Streaming PCA: Matching Matrix Bernstein and Near-Optimal Finite Sample Guarantees for Oja's Algorithm
• Riemannian stochastic variance reduced gradient on Grassmann manifold
• Distributed Stochastic Algorithms for High-rate Streaming Principal Component Analysis
• First Efficient Convergence for Streaming k-PCA: a Global, Gap-Free, and Near-Optimal Rate
• On Biased Stochastic Gradient Estimation
• Efficient Algorithms for Large-scale Generalized Eigenvector Computation and Canonical Correlation Analysis
• Convergence of Stochastic Gradient Descent for PCA
• A Universal Variance Reduction-Based Catalyst for Nonconvex Low-Rank Matrix Recovery
• Communication-Efficient Distributed SVD via Local Power Iterations
• The gradient complexity of linear regression
• Distributed Asynchronous Dual Free Stochastic Dual Coordinate Ascent
• Distributed Estimation for Principal Component Analysis: an Enlarged Eigenspace Analysis
• Stochastic Variance-reduced Gradient Descent for Low-rank Matrix Recovery from Linear Measurements
• On the Regret Minimization of Nonconvex Online Gradient Ascent for Online PCA
• Stochastic Variance-Reduced Heavy Ball Power Iteration
• Spectral M-estimation with Applications to Hidden Markov Models
• Efficient Globally Convergent Stochastic Optimization for Canonical Correlation Analysis
• Stochastic Gradient Descent for Stochastic Doubly-Nonconvex Composite Optimization
• Non-Sparse PCA in High Dimensions via Cone Projected Power Iteration
• FedPower: Privacy-Preserving Distributed Eigenspace Estimation