Faster eigenvector computation via shift-and-invert preconditioning

Abstract

We give faster algorithms and improved sample complexities for the fundamental problem of estimating the top eigenvector. Given an explicit matrix A € Rn×d, we show how to compute an e approximate top eigenvector of ATA in time O (jnnz(A) + • log l/ϵ). Here nnz(A) is the number of nonzeros in A, sr(A) is the stable rank, and gap is the relative eigengap. We also consider an online setting in which, given a stream of i.i.d. samples from a distribution V with covariance matrix E and a vector xq which is an O(gap) approximate top eigenvector for E, we show how to refine xo to an € approximation using O j samples from V. Here v(P) is a natural notion of variance. Combining our algorithm with previous work to initialize xo, we obtain improved sample complexities and runtimes under a variety of assumptions on V. We achieve our results via a robust analysis of the classic shift-and-invert preconditioning method. This technique lets us reduce eigenvector computation to approximately solving a scries of linear systems with fast stochastic gradient methods.