Faster Eigenvector Computation via Shift and Invert Preconditioning
We give faster algorithms and improved sample complexities for estimating the top eigenvector of a matrix \Sigma$ i.e. computing a unit vector $x$ such that $x^T \Sigma x \ge (1 \epsilon)\lambda_1(\Sigma) Offline Eigenvector Estimation: Given an explicit $A \in \mathbb{R}{n \times d} with \Sigma A^TA$ we show how to compute an \epsilon$ approximate top eigenvector in time \tilde O([nnz(A) \frac{d*sr(A){gap^2} \log 1/\epsilon and \tilde O(\frac{nnz(A){3/4} (d*sr(A){1/4}\sqrt{gap} \log 1/\epsilon Here $nnz(A) is the number of nonzeros in $A$ $sr(A) is the stable rank, $gap$ is the relative eigengap. By separating the $gap$ dependence from the $nnz(A) term, our first runtime improves upon the classical power and Lanczos methods. It also improves prior work using fast subspace embeddings [AC09, CW13] and stochastic optimization [Sha15c] giving significantly better dependencies on $sr(A) and \epsilon$ Our second running time improves these further when $nnz(A) \le \frac{d*sr(A){gap^2} Online Eigenvector Estimation: Given a distribution $D$ with covariance matrix \Sigma$ and a vector $x_0$ which is an $O(gap) approximate top eigenvector for \Sigma$ we show how to refine to an \epsilon$ approximation using O(\frac{var(D){gap*\epsilon} samples from $D$ Here $var(D) is a natural notion of variance. Combining our algorithm with previous work to initialize $x_0$ we obtain improved sample complexity and runtime results under a variety of assumptions on $D$ We achieve our results using a general framework that we believe is of independent interest. We give 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 stochastic variance reduced gradient (SVRG) based system solvers to achieve our claims.
ICML