Sublinear Time Eigenvector Approximation via Column Sampling

Abstract

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 eigenvalue $\lambda$ of $A$ with $|\lambda| \ge \epsilon n$, outputs an approximate eigenvector $v$ satisfying $\|Av - \lambda v\|_2 \le \epsilon n$. For approximating just the eigenvector of the largest magnitude eigenvalue, our algorithm samples only $\tilde{O}(\log n/\epsilon^2)$ columns. Given the ability to sample rows and columns of $A$ proportional to their squared norms, we give a similar result with an improved error bound of $\epsilon \|A\|_F$. For top eigenvector approximation, we show our bound is tight up to logarithmic terms. A key feature of our algorithms is that the output eigenvectors are spanned by a small number of $A$'s columns, and individual entries can be computed rapidly, in poly(log n, 1/epsilon) time per entry. This makes them applicable in the quantum-inspired algorithms framework of [Tang, STOC 2019], where we give the first sublinear time classical algorithms for eigenvector approximation with additive error $\epsilon \|A\|_F$. Finally, we present an alternative approach, based on a truncated Nystrom method, that, while not allowing poly(log n, 1/epsilon) time entrywise computation of the approximate eigenvectors, achieves near optimal sample complexity for general symmetric matrices, and improved bounds for positive semidefinite matrices. Technically, our bounds build on recent work on approximating the outlying eigenvalues of symmetric matrices via random sampling in [Bhattacharjee et al.'22] and [Swartworth and Woodruff'25]. We demonstrate for the first time that these approaches extend to the problem of eigenvector estimation.