Dominic Rutkowski

Sublinear Time Eigenvector Approximation via Column Sampling

This work gives the first sublinear time classical algorithms for eigenvector approximation with additive error $\epsilon \|A\|_F$ and presents an alternative approach, based on a truncated Nystrom method, that achieves near optimal sample complexity for general symmetric matrices, and improved bounds for positive semi...