Sublinear Time Eigenvector Approximation via Column Sampling

Rajarshi Bhattacharjee, Cameron Musco, Dominic Rutkowski

We study sublinear time sampling methods for approximating the outlying eigenvectors of large matrices. Our main result is an algorithm that uniformly samples just $\tilde{O}(\log…