Speaker
Description
We study the problem of approximating the eigenvectors of an n x n symmetric matrix A with bounded entries using random column sampling. We show that for any eigenvalue $\lambda$ of A, one can compute a vector v satisfying $||Av-\lambda v||_2 \leq \epsilon n$ by sampling $\tilde{O}(\frac{1}{\epsilon^4})$ columns of A. For the eigenvector corresponding to the largest-magnitude eigenvalue, this sample complexity improves to $\tilde{O}(\frac{1}{\epsilon^2})$ columns.
We further establish a lower bound on the number of entries of A that must be sampled to approximate its top eigenvector up to error $\epsilon n$, showing that our algorithm is optimal up to polylogarithmic factors. When columns of A can be sampled with probabilities proportional to their squared $l_2$-norms, we obtain an improved error guarantee of $\epsilon ||A||_F$ for the approximate eigenvectors, where $||A||_F$ denotes the Frobenius norm.
Our analysis builds on recent results of Bhattacharjee et al. (2022) and Swartworth and Woodruff (2025), which demonstrate that all eigenvalues of A can be approximated up to additive error $\epsilon n$ (and $\epsilon ||A||_F$ under $l_2$ sampling) by sampling a sufficiently large principal submatrix.