# Improved Spectral Density Estimation via Explicit and Implicit Deflation

arXiv: https://arxiv.org/abs/2410.21690 · HTML: https://mlsanity.com/paper/2410.21690/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 29 Oct 2024.

## Built on by (most cited first, 3 of 3)

- [Spectral Estimation with Free Decompression](https://mlsanity.com/paper/2506.11994/) (2025)
- [Query Efficient Structured Matrix Learning](https://mlsanity.com/paper/2507.19290/) (2025)
- [Theoretically and Practically Efficient Resistance Distance Computation on Large Graphs](https://mlsanity.com/paper/2601.11159/) (2026)

## Abstract (arXiv)

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 ε·σℓ(A) error approximation to the spectral density in the Wasserstein-1 metric 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, our bound can be much stronger than prior work, which gives an error bound of ε · ||A||2 using O(1/ε) matrix-vector products. We also show that it is nearly tight: any algorithm giving error ε · σℓ(A) must use Omega(ℓ+1/ε) matrix-vector products. We further show that the popular Stochastic Lanczos Quadrature (SLQ) method matches the above bound, even though SLQ itself is parameter-free and performs no explicit deflation. This bound explains the strong practical performance of SLQ, and motivates a simple variant of SLQ that achieves an even tighter error bound. Our error bound for SLQ leverages an analysis 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.