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

Chi Jin, Sham M. Kakade, Cameron Musco +2

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 c…