Improved Spectral Density Estimation via Explicit and Implicit Deflation

Understand

We study algorithms for approximating the spectral density of a symmetric matrix $A$ that is accessed through matrix-vector product queries.

• By combining a previously studied Chebyshev polynomial moment matching method with a deflation step that approximately projects off the largest magnitude eigendirections of $A$ before estimating the spectral density, we give an $\epsilon\cdot\sigma_\ell(A)$ error approximation to the spectral density in the Wasserstein-$1$ metric using $O(\ell\log n+ 1/\epsilon)$ matrix-vector products, where $\sigma_\ell(A)$ is the $\ell^{th}$ largest singular value of $A$.
• In the common case when $A$ exhibits fast singular value decay, our bound can be much stronger than prior work, which gives an error bound of $\epsilon \cdot ||A||_2$ using $O(1/\epsilon)$ matrix-vector products.
• We also show that it is nearly tight: any algorithm giving error $\epsilon \cdot \sigma_\ell(A)$ must use $\Omega(\ell+1/\epsilon)$ matrix-vector products.