# Fast and Simple PCA via Convex Optimization

arXiv: https://arxiv.org/abs/1509.05647 · HTML: https://mlsanity.com/paper/1509.05647/

## Key facts

- Cited by 16 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 Sep 2015.

## Built on by (most cited first, 16 of 16)

- [A Practical Method for Constructing Equivariant Multilayer Perceptrons for Arbitrary Matrix Groups](https://mlsanity.com/paper/2104.09459/) (2021)
- [Personalized PCA: Decoupling Shared and Unique Features](https://mlsanity.com/paper/2207.08041/) (2022)
- [Hessian Averaging in Stochastic Newton Methods Achieves Superlinear Convergence](https://mlsanity.com/paper/2204.09266/) (2022)
- [Sarah Frank-Wolfe: Methods for Constrained Optimization with Best Rates and Practical Features](https://mlsanity.com/paper/2304.11737/) (2023)
- [Federated Learning on Riemannian Manifolds with Differential Privacy](https://mlsanity.com/paper/2404.10029/) (2024)
- [FedPower: Privacy-Preserving Distributed Eigenspace Estimation](https://mlsanity.com/paper/2103.00704/) (2021)
- [Riemannian Federated Learning via Averaging Gradient Streams](https://mlsanity.com/paper/2409.07223/) (2024)
- [Frank-Wolfe-based Algorithms for Approximating Tyler's M-estimator](https://mlsanity.com/paper/2206.09370/) (2022)
- [Streamlining in the Riemannian Realm: Efficient Riemannian Optimization with Loopless Variance Reduction](https://mlsanity.com/paper/2403.06677/) (2024)
- [Enhancing E-Commerce Recommendation using Pre-Trained Language Model and Fine-Tuning](https://mlsanity.com/paper/2302.04443/) (2023)
- [Optimization Can Learn Johnson Lindenstrauss Embeddings](https://mlsanity.com/paper/2412.07242/) (2024)
- [Gap-Free Streaming PCA Beyond Rank-One Updates: Near-Optimal Rates and Applications to Differential Privacy](https://mlsanity.com/paper/2609.26508/) (2026)
- [From Oja's Algorithm to the Multiplicative Weights Update Method with Applications](https://mlsanity.com/paper/2310.15559/) (2023)
- [Accelerated Gradient Algorithms with Adaptive Subspace Search for Instance-Faster Optimization](https://mlsanity.com/paper/2312.03218/) (2023)
- [k-SVD with Gradient Descent](https://mlsanity.com/paper/2502.00320/) (2025)
- [What is a Sketch-and-Precondition Derivation for Low-Rank Approximation? Inverse Power Error or Inverse Power Estimation?](https://mlsanity.com/paper/2502.07993/) (2025)

## Abstract (arXiv)

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 textitsmall 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× d matrix X = frac1nsumi=1nxixitop with top eigenvector u and top eigenvalue λ1 it is possible to: beginitemize item compute a unit vector w such that (wtopu)2 ≥ 1-ε in tildeOleft(fracdδ2+Nright) time, where δ = λ1 - λ2 and N is the total number of non-zero entries in x1,...,xn, item compute a unit vector w such that wtopXw ≥ λ1-ε in tildeO(d/ε2) time. enditemize 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 δ (in the first case) and ε (in the second case) are smaller than √d/N.