Improved Spectral Density Estimation via Explicit and Implicit Deflation

We study algorithms for approximating the spectral density (i.e., the eigenvalue distribution) of a symmetric matrix A ∈ Rⁿ×ⁿ that is accessed through matrix-vector product queries. Recent work has analyzed popular Krylov subspace methods for this problem, showing that they output an ϵ · ∥A∥2 error approximation to the spectral density in the Wasserstein-1 metric using O(1/ϵ) matrix-vector products. 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 improved error bound of ϵ · σ_ℓ(A) using O(ℓ log n + 1/ϵ) matrix-vector products, where σ_ℓ(A) is the ℓ^th largest singular value of A. In the common case when A exhibits fast singular value decay and so σ_ℓ(A) ≪ ∥A∥2, our bound can be much stronger than prior work. We also show that it is nearly tight: any algorithm giving error ϵ · σ_ℓ(A) must use Ω(ℓ + 1/ϵ) matrix-vector products. We further show that the popular Stochastic Lanczos Quadrature (SLQ) method essentially matches the above bound for any choice of parameter ℓ, even though SLQ itself is parameter-free and performs no explicit deflation. Our bound helps to explain the strong practical performance and observed ‘spectrum adaptive’ nature of SLQ, and motivates a simple variant of the method that achieves an even tighter error bound. Technically, our results require a careful analysis of how eigenvalues and eigenvectors are approximated by (block) Krylov subspace methods, which may be of independent interest. Our error bound for SLQ leverages an analysis of the method that views it as an implicit polynomial moment matching method, along with recent results on low-rank approximation with single-vector Krylov methods. We use these results to show that the method can perform ‘implicit deflation’ as part of moment matching.