Name
Title | ||
|---|---|---|
Robust Shift-and-Invert Preconditioning: Faster and More Sample Efficient Algorithms for Eigenvector Computation |
Abstract | ||
|---|---|---|
We provide faster algorithms and improved sample complexities for approximating the top eigenvector of a matrix. Offline Setting: Given an $n \times d$ matrix $A$, we show how to compute an $\epsilon$ approximate top eigenvector in time $\tilde O ( [nnz(A) + \frac{d \cdot sr(A)}{gap^2}]\cdot \log 1/\epsilon )$ and $\tilde O([\frac{nnz(A)^{3/4} (d \cdot sr(A))^{1/4}}{\sqrt{gap}}]\cdot \log1/\epsilon )$. 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 $\epsilon$. Our second running time improves this further when $nnz(A) \le \frac{d\cdot sr(A)}{gap^2}$. Online Setting: 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 $\tilde O(\frac{v(D)}{gap^2} + \frac{v(D)}{gap \cdot \epsilon})$ samples from $D$. Here $v(D)$ is a natural variance measure. Combining our algorithm with previous work to initialize $x_0$, 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. |
Year | Venue | Field |
|---|---|---|
2015 | CoRR | Discrete mathematics,Combinatorics,Lanczos resampling,Multiplicative function,Linear system,Subspace topology,Matrix (mathematics),Algorithm,Covariance matrix,Asymptotically optimal algorithm,Mathematics,Eigenvalues and eigenvectors |
DocType | Volume | Citations |
Journal | abs/1510.08896 | 11 |
PageRank | References | Authors |
0.64 | 15 | 5 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| chi jin | 1 | 16 | 1.72 |
| Sham Kakade | 2 | 4365 | 282.77 |
| Cameron Musco | 3 | 258 | 25.06 |
| Praneeth Netrapalli | 4 | 674 | 34.41 |
| Aaron Sidford | 5 | 484 | 44.21 |