Faster Eigenvector Computation via Shift-and-Invert Preconditioning This paper combines work first appearing in [GH15] and [JKM+15]
Dan Garber Affiliation: Toyota Technological Institute at Chicago Email: Elad Hazan Affiliation: Princeton University Email: Chi Jin Affiliation: UC Berkeley Email: Sham M. Kakade Affiliation: University of Washington Email: Cameron Musco Affiliation: MIT Email: Praneeth Netrapalli Affiliation: Microsoft Research, New England Email: Aaron Sidford Affiliation: Microsoft Research, New England Email:
Abstract
We give faster algorithms and improved sample complexities for estimating the top eigenvector of a matrix $\mathbf{\Sigma}$ – i.e. computing a unit vector $x$ such that $x^{\top}\mathbf{\Sigma}x\geq(1-\epsilon)\lambda_{1}(\mathbf{\Sigma})$ :
原文 arXiv:1605.08754;中英对照 + 大白话阅读 https://aha.fim.ai/paper/1605.08754v1