Faster Spectral Density Estimation and Sparsification in the Nuclear Norm

Understand

We consider the problem of estimating the spectral density of the normalized adjacency matrix of an $n$-node undirected graph.

• We provide a randomized algorithm that, with $O(n\epsilon^{-2})$ queries to a degree and neighbor oracle and in $O(n\epsilon^{-3})$ time, estimates the spectrum up to $\epsilon$ accuracy in the Wasserstein-1 metric.
• This improves on previous state-of-the-art methods, including an $O(n\epsilon^{-7})$ time algorithm from [Braverman et al., STOC 2022] and, for sufficiently small $\epsilon$, a $2^{O(\epsilon^{-1})}$ time method from [Cohen-Steiner et al., KDD 2018].
• To achieve this result, we introduce a new notion of graph sparsification, which we call nuclear sparsification.