Sublinear Time Eigenvalue Approximation via Random Sampling

Rajarshi Bhattacharjee, Gregory Dexter, Petros Drineas +2

We study the problem of approximating the eigenspectrum of a symmetric matrix $\mathbf{A}\in {\mathbb{R}}^{n\times n}$ with bounded entries (i.e., $\Vert \mathbf{A}{\Vert }_{\infty }\le 1$).…