The Noisy Power Method: A Meta Algorithm with Applications
This work provides a foundational analysis that benefits machine learning practitioners dealing with noisy data in applications such as privacy and streaming.
The paper introduces a robust convergence analysis for the noisy power method, a meta-algorithm applied to problems like matrix completion and streaming PCA, resolving open issues and unifying existing bounds.
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.