We provide a new robust convergence analysis of the well-known subspace iteration algorithm for computing the dominant singular vectors of a matrix, also known as simultaneous iteration or power method. Our result characterizes the convergence behavior of the algorithm when a large amount noise is introduced after each matrix-vector multiplication. While interesting in its own right, our main motivation comes from the problem of privacy-preserving spectral analysis where noise is added in order to achieve the privacy guarantee known as differential privacy. Our contributions here are twofold: We give nearly tight worst-case bounds for the problem of computing a differentially private low-rank approximation in the spectral norm. Our results extend to privacy-preserving principal component analysis and apply to several variants of differential privacy that have been considered in the past. The running time of our algorithm is nearly linear in the input sparsity leading to strong improvements in running time over previous work while almost matching existing worst-case lower bounds on the amount of error that is required by any differentially private algorithm. Complementing our worst-case bounds, we show that the error dependence of our algorithm on the matrix dimension can be replaced by an essentially tight dependence on the coherence of the matrix. This result resolves the main problem left open by previous results in this line of work. The coherence is always bounded by the matrix dimension but often substantially smaller thus leading to significant average-case improvements over our worst-case bounds.

本文针对机器学习中常用的噪声干扰的幂方法进行研究，提出了新的稳健收敛性分析，解决了在多个应用领域中的一系列问题。

噪声幂法：具有应用的元算法