Query Efficient Algorithms for Spectral Density Estimation

We will discuss efficient algorithms for estimating the eigenvalue spectrum of a matrix in two popular query models: the matrix-vector product (matvec) query model and the entrywise query model. In the matvec model, we will discuss how worst-case bounds for `moment-matching' based Krylov methods like the kernel polynomial method can be significantly improved for matrices with decaying eigenvalue spectra using a deflation-based approach. We will then discuss how the bounds obtained by this approach are essentially matched by the popular stochastic Lanczos quadrature method (SLQ), helping to explain the strong performance of this method as compared to explicit moment-matching-based methods in practice. Finally, we will briefly review eigenvalue approximation bounds in the entrywise query model -- discussing how poly(1/epsilon) entrywise samples from any matrix can be used to estimate all of its eigenvalues to small additive error. We will highlight several open questions in both query models.