# The Noisy Power Method: A Meta Algorithm with Applications

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

## Key facts

- Cited by 58 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 11 Nov 2013.

## Built on by (most cited first, 30 of 58)

- [DP-PCA: Statistically Optimal and Differentially Private PCA](https://mlsanity.com/paper/2205.13709/) (2022)
- [Streaming k-PCA: Efficient guarantees for Oja's algorithm, beyond rank-one updates](https://mlsanity.com/paper/2102.03646/) (2021)
- [DeEPCA: Decentralized Exact PCA with Linear Convergence Rate](https://mlsanity.com/paper/2102.03990/) (2021)
- [Privately Learning Subspaces](https://mlsanity.com/paper/2106.00001/) (2021)
- [Optimal Gradient-based Algorithms for Non-concave Bandit Optimization](https://mlsanity.com/paper/2107.04518/) (2021)
- [Share Your Representation Only: Guaranteed Improvement of the Privacy-Utility Tradeoff in Federated Learning](https://mlsanity.com/paper/2309.05505/) (2023)
- [On the Optimality of the Oja's Algorithm for Online PCA](https://mlsanity.com/paper/2104.00512/) (2021)
- [Bootstrapping the error of Oja's algorithm](https://mlsanity.com/paper/2106.14857/) (2021)
- [Private Alternating Least Squares: Practical Private Matrix Completion with Tighter Rates](https://mlsanity.com/paper/2107.09802/) (2021)
- [Efficient Low-Rank Matrix Estimation, Experimental Design, and Arm-Set-Dependent Low-Rank Bandits](https://mlsanity.com/paper/2402.11156/) (2024)
- [Faster Kernel Matrix Algebra via Density Estimation](https://mlsanity.com/paper/2102.08341/) (2021)
- [Statistical and Computational Trade-offs in Variational Inference: A Case Study in Inferential Model Selection](https://mlsanity.com/paper/2207.11208/) (2022)
- [Black-Box k-to-1-PCA Reductions: Theory and Applications](https://mlsanity.com/paper/2403.03905/) (2024)
- [PLAN: Variance-Aware Private Mean Estimation](https://mlsanity.com/paper/2306.08745/) (2023)
- [Differentially private and decentralized randomized power method](https://mlsanity.com/paper/2411.01931/) (2024)
- [On the Second-order Convergence Properties of Random Search Methods](https://mlsanity.com/paper/2110.13265/) (2021)
- [Fast algorithm for overcomplete order-3 tensor decomposition](https://mlsanity.com/paper/2202.06442/) (2022)
- [Streaming Kernel PCA Algorithm With Small Space](https://mlsanity.com/paper/2303.04555/) (2023)
- [Fair Streaming Principal Component Analysis: Statistical and Algorithmic Viewpoint](https://mlsanity.com/paper/2310.18593/) (2023)
- [FedPower: Privacy-Preserving Distributed Eigenspace Estimation](https://mlsanity.com/paper/2103.00704/) (2021)
- [Stochastic and Private Nonconvex Outlier-Robust PCA](https://mlsanity.com/paper/2203.09276/) (2022)
- [Differentially Private Low-dimensional Synthetic Data from High-dimensional Datasets](https://mlsanity.com/paper/2305.17148/) (2023)
- [An Iterative Algorithm for Differentially Private k-PCA with Adaptive Noise](https://mlsanity.com/paper/2508.10879/) (2025)
- [Low-Precision Streaming PCA](https://mlsanity.com/paper/2510.22440/) (2025)
- [Spectral Perturbation Bounds for Low-Rank Approximation with Applications to Privacy](https://mlsanity.com/paper/2510.25670/) (2025)
- [Federated singular value decomposition for high dimensional data](https://mlsanity.com/paper/2205.12109/) (2022)
- [Learning ground states of gapped quantum Hamiltonians with Kernel Methods](https://mlsanity.com/paper/2303.08902/) (2023)
- [Spectral Guarantees for Adversarial Streaming PCA](https://mlsanity.com/paper/2408.10332/) (2024)
- [In-depth Analysis of Low-rank Matrix Factorisation in a Federated Setting](https://mlsanity.com/paper/2409.08771/) (2024)
- [On the Price of Differential Privacy for Spectral Clustering over Stochastic Block Models](https://mlsanity.com/paper/2505.05816/) (2025)

## Abstract (arXiv)

We provide a new robust convergence analysis of the well-known power method for computing the dominant singular vectors of a matrix that we call the noisy power method. Our result characterizes the convergence behavior of the algorithm when a significant amount noise is introduced after each matrix-vector multiplication. The noisy power method can be seen as a meta-algorithm that has recently found a number of important applications in a broad range of machine learning problems including alternating minimization for matrix completion, streaming principal component analysis (PCA), and privacy-preserving spectral analysis. Our general analysis subsumes several existing ad-hoc convergence bounds and resolves a number of open problems in multiple applications including streaming PCA and privacy-preserving singular vector computation.