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

The authors provide a unified analysis of a general class of randomized matrix-free quadrature algorithms for approximating the cumulative empirical spectral measure (CESM) corresponding to an eigendecomposition of a Hermitian matrix \(A\). The CESM is related to the spectral sum \(\operatorname{tr}(f(A))\) of a matrix function \(f(A)\). The algorithms studied include two widely used methods for these tasks -- the well-known kernel polynomial method (KPM) and stochastic Lanczos quadrature (SLQ), and can be broken into two main stages. In the first stage, the CESM is approximated with the weighted CESM. In the second stage, each weighted CESM is approximated using a polynomial quadrature rule.\N\NTheoretical bounds are derived for spectral sum approximation which guarantee that the algorithms are simultaneously accurate on all bounded analytic functions. The bounds are stated in terms of the best approximation on a given interval \([\lambda_{\min}, \lambda_{\max}]\). This approach is applied to analytic bounded functions on a Bernstein ellipse.\N\NIn addition to theory, comprehensive and complementary numerical experiments are provided that highlight a number of qualitative trade-offs between the algorithms. The 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. In particular, SLQ and KPM are compared in a range of settings and the impact of using KPM approximations corresponding to orthogonal polynomial families other than the Chebyshev polynomials is studied.