# An Improved Gap-Dependency Analysis of the Noisy Power Method

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

## Key facts

- Cited by 24 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Feb 2016.

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

- [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)
- [Optimal Gradient-based Algorithms for Non-concave Bandit Optimization](https://mlsanity.com/paper/2107.04518/) (2021)
- [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)
- [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)
- [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)
- [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)
- [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)
- [Federated singular value decomposition for high dimensional data](https://mlsanity.com/paper/2205.12109/) (2022)
- [Spectral Guarantees for Adversarial Streaming PCA](https://mlsanity.com/paper/2408.10332/) (2024)
- [Distributed Differentially Private Data Analytics via Secure Sketching](https://mlsanity.com/paper/2412.00497/) (2024)
- [Decentralized Differentially Private Power Method](https://mlsanity.com/paper/2507.22849/) (2025)
- [Adaptive Power Iteration Method for Differentially Private PCA](https://mlsanity.com/paper/2602.11454/) (2026)
- [Gap-Free Streaming PCA Beyond Rank-One Updates: Near-Optimal Rates and Applications to Differential Privacy](https://mlsanity.com/paper/2609.26508/) (2026)
- [Stochastic Parallelizable Eigengap Dilation for Large Graph Clustering](https://mlsanity.com/paper/2207.14589/) (2022)
- [Differentially Private and Scalable Estimation of the Network Principal Component](https://mlsanity.com/paper/2505.03858/) (2025)
- [Improved Analysis of the Accelerated Noisy Power Method with Applications to Decentralized PCA](https://mlsanity.com/paper/2602.03682/) (2026)
- [Gap-free Differentially Private PCA for Gaussian Data](https://mlsanity.com/paper/2609.31614/) (2026)

## Abstract (arXiv)

We consider the noisy power method algorithm, which has wide applications in machine learning and statistics, especially those related to principal component analysis (PCA) under resource (communication, memory or privacy) constraints. Existing analysis of the noisy power method shows an unsatisfactory dependency over the "consecutive" spectral gap (σk-σk+1) of an input data matrix, which could be very small and hence limits the algorithm's applicability. In this paper, we present a new analysis of the noisy power method that achieves improved gap dependency for both sample complexity and noise tolerance bounds. More specifically, we improve the dependency over (σk-σk+1) to dependency over (σk-σq+1), where q is an intermediate algorithm parameter and could be much larger than the target rank k. Our proofs are built upon a novel characterization of proximity between two subspaces that differ from canonical angle characterizations analyzed in previous works. Finally, we apply our improved bounds to distributed private PCA and memory-efficient streaming PCA and obtain bounds that are superior to existing results in the literature.