Randomized Matrix-Free Quadrature: Unified and Uniform Bounds for Stochastic Lanczos Quadrature and the Kernel Polynomial Method

We analyze randomized matrix-free quadrature algorithms for spectrum and spectral sum approximation. The algorithms studied include the kernel polynomial method and stochastic Lanczos quadrature, two widely used methods for these tasks. Our analysis of spectrum approximation unifies and simplifies several one-off analyses for these algorithms which have appeared over the past decade. In addition, we derive bounds for spectral sum approximation which guarantee that, with high probability, the algorithms are simultaneously accurate on all bounded analytic functions. Finally, we provide comprehensive and complementary numerical examples. These examples illustrate some of the qualitative similarities and differences between the algorithms, as well as relative drawbacks and benefits to their use on different types of problems.