# Randomized matrix-free quadrature: unified and uniform bounds for stochastic Lanczos quadrature and the kernel polynomial method

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 Apr 2022.

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

- [Fast Spectrum Estimation of Some Kernel Matrices](https://mlsanity.com/paper/2411.00657/) (2024)

## Abstract (arXiv)

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 complimentary 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.