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.
