Sublinear Time Spectral Density Estimation

Christopher Musco (New York University)

I will discuss new work on the popular kernel polynomial method (KPM) for approximating the spectral density (eigenvalue distribution) of an nxn diagonalizable matrix A with real-valued eigenvalues. I will show that a practical variant of the KPM algorithm can approximate the spectral density to epsilon accuracy in the Wasserstein-1 distance with roughly O(1/epsilon) matrix-vector multiplications with A. Moreover, we will show that the method is robust to inaccuracy in these matrix-vector multiplications, which allows it to be combined with any approximation algorithm for computing them. As an application, we develop a randomized sublinear time algorithm for approximating the spectral density of any normalized graph adjacency or Laplacian matrix. The talk will cover the main tools used in our work, which include Jacksonâ€™s seminal work on approximation with positive kernels, and stability results for computing orthogonal polynomials via three-term recurrence relations.