We study the problem of approximating the eigenvalues and eigenvectors of a symmetric matrix \(A \in R^{n \times n}\) with bounded entries using random sampling. We present a simple sublinear time algorithm that approximates all eigenvalues of \(A\) up to additive error \(\pm \epsilon n\) using those of a randomly sampled \(\tilde{O} (\frac{1}{\epsilon^2}) \times \tilde{O}(\frac{1}{\epsilon^2} )\) principal submatrix. Our result can be viewed as a concentration bound on the complete eigenspectrum of a random submatrix, significantly extending known bounds on just the singular values. Using similar techniques, we also show that for any eigenvalue \(\lambda\) of A, one can compute a vector v satisfying \(||Av-\lambda v||_2 <=\epsilon n \) by sampling \( \tilde{O}(1/\epsilon^4) \) columns of A. When rows of A can be sampled with probabilities proportional to their squared Euclidean norms, we obtain improved approximation guarantees for the eigenspectrum.

Rajarshi Bhattacharjee is a Ph.D student in theoretical computer science at UMass Amherst, working on randomized linear algebra and online learning. He is advised by Prof. Cameron Musco.

For more information, please visit our website: Math Frontier Seminar Website.