Robust Shift-and-Invert Preconditioning: Faster and More Sample Efficient Algorithms for Eigenvector Computation

We provide faster algorithms and improved sample complexities for approximating the top eigenvector of a matrix. Offline Setting: Given an n × d matrix A, we show how to compute an ε approximate top eigenvector in time tilde O ( [nnz(A) + fracd · sr(A)gap2]· log 1/ε ) and tilde O([fracnnz(A)3/4 (d · sr(A))1/4√gap]· log1/ε ). Here sr(A) is the stable rank and gap is the multiplicative eigenvalue gap. By separating the gap dependence from nnz(A) we improve on the classic power and Lanczos methods. We also improve prior work using fast subspace embeddings and stochastic optimization, giving significantly improved dependencies on sr(A) and ε. Our second running time improves this further when nnz(A) ≤ fracd· sr(A)gap2. Online Setting: Given a distribution D with covariance matrix Sigma and a vector x0 which is an O(gap) approximate top eigenvector for Sigma, we show how to refine to an ε approximation using tilde O(fracv(D)gap2 + fracv(D)gap · ε) samples from D. Here v(D) is a natural variance measure. Combining our algorithm with previous work to initialize x0, we obtain a number of improved sample complexity and runtime results. For general distributions, we achieve asymptotically optimal accuracy as a function of sample size as the number of samples grows large. Our results center around a robust analysis of the classic method of shift-and-invert preconditioning to reduce eigenvector computation to approximately solving a sequence of linear systems. We then apply fast SVRG based approximate system solvers to achieve our claims. We believe our results suggest the general effectiveness of shift-and-invert based approaches and imply that further computational gains may be reaped in practice.