The Noisy Power Method: A Meta Algorithm with Applications

Moritz Hardt, Eric Price

Abstract: 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.

Introduction

Computing the dominant singular vectors of a matrix, commonly known as Principal Component Analysis (PCA), is a fundamental task in machine learning. While the classical power method is well-understood for clean matrices, modern applications often involve significant noise. This noise can arise from sampling errors in streaming settings, intentional perturbations for differential privacy, or structural missingness in matrix completion.

Previously, these scenarios were addressed with specialized, ad-hoc analyses. This work introduces a unified, robust theory for the Noisy Power Method (NPM), explaining its convergence even under persistent, iteration-wise noise.

The Noisy Power Method

The NPM is a simple yet powerful meta-algorithm. It generalizes the standard power iteration by allowing for a perturbation matrix $G_\ell$ at each step.

The general Noisy Power Method algorithm, which serves as a meta-algorithm for various ML tasks.

The algorithm proceeds by starting with a random initial subspace $X_0$. In each iteration $\ell$, it computes a noisy matrix-vector product $Y_\ell = AX_{\ell-1} + G_\ell$ and then orthonormalizes the result using a QR-factorization. The core of this paper's contribution is a convergence analysis based on principal angles. The authors prove that the algorithm converges globally as long as the noise $G_\ell$ is bounded relative to the "eigengap"—the difference between the $k$-th and $(k+1)$-th singular values.

Key Insights: Over-sampling and Global Convergence

A critical finding of this research is the benefit of over-sampling. By choosing a subspace dimension $p$ that is slightly larger than the target number of singular vectors $k$ (e.g., $p = k + \text{constant}$), the algorithm becomes significantly more resilient to noise.

Furthermore, unlike many iterative methods that require a "warm start" (an initial guess close to the solution), this analysis guarantees global convergence from a random initialization. This is particularly important for practical applications where a good initial guess is unavailable.

Applications

The NPM framework allows for a unified treatment of several disparate problems.

Differentially Private PCA

In privacy-sensitive applications, noise is intentionally added to protect individual data points. The authors instantiate the NPM for this setting by defining the noise $G_\ell$ based on privacy parameters $\epsilon$ and $\delta$.

The Differentially Private Power Method, a specific instantiation of the NPM framework.

This approach yields the first nearly-linear time algorithm for differentially private PCA with nearly tight worst-case error bounds. Notably, for "incoherent" matrices, the error dependence on the ambient dimension $d$ is greatly reduced.

Streaming PCA

In the streaming setting, the matrix $A$ is not available directly; instead, we observe samples. The sampling error acts as the perturbation $G_\ell$. The NPM analysis provides a simpler proof for streaming PCA convergence with linear sample complexity in $d$, confirming empirical observations for non-Gaussian data.

Conclusion and Future Work

The Noisy Power Method provides a robust theoretical foundation for many modern PCA variants. While the current analysis depends on the eigengap $(\sigma_k - \sigma_{k+1})$, future research may explore gap-independent convergence through more aggressive over-sampling or focus on spectral approximation where the exact singular vectors are less critical than capturing the matrix's variance.

Summary updated

Abstract

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.
BibTeX
@inproceedings{hardt2014noisy,
  author = {Moritz Hardt and Eric Price},
  title = {{The Noisy Power Method: A Meta Algorithm with Applications}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2014},
  url = {https://openreview.net/forum?id=HJZqPv-d-S},
}
Figure