Noisy Power Method with Grassmann Average

Abstract

The power method is a simple and efficient algorithm for finding the top k singular vectors of any input matrix. In practice, noise matrices could be added to the input matrix at each iteration of the power method, and the convergence behavior of the algorithm is hard to guarantee. The convergence behavior of the noisy power method is understood only for the cases when the noise level (the spectral norm of noise matrices) is bellow a threshold and the noisy power method cannot extract the exact top k singular vectors because of the noise matrices. We propose a Grassmann average function which can make the noisy power method converge to the exact top k singular vectors and an efficient algorithm that can approximate the Grassmann average with a much less computational cost.