Dominic Rutkowski

Sublinear Time Eigenvector Approximation via Column Sampling

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 n/\epsilon^4)$ columns of a symmetric matrix $A \in \mathbb{R}^{n \times n}$ with entries bounded in magnitude by $1$, and, for any eigenval...