Analysis of stochastic Lanczos quadrature for spectrum approximation

The cumulative empirical spectral measure (CESM) Phi[A] : ℝ → [0,1] of a n× n symmetric matrix A is defined as the fraction of eigenvalues of A less than a given threshold, i.e., Phi[A](x) := sumi=1n frac1n largeunicodex1D7D9[ λi[A]≤ x]. Spectral sums operatornametr(f[A]) can be computed as the Riemann--Stieltjes integral of f against Phi[A], so the task of estimating CESM arises frequently in a number of applications, including machine learning. We present an error analysis for stochastic Lanczos quadrature (SLQ). We show that SLQ obtains an approximation to the CESM within a Wasserstein distance of t : | λmax[A] - λmin[A] | with probability at least 1-η, by applying the Lanczos algorithm for lceil 12 t-1 + frac12 rceil iterations to lceil 4 ( n+2 )-1t-2 ln(2nη-1) rceil vectors sampled independently and uniformly from the unit sphere. We additionally provide (matrix-dependent) a posteriori error bounds for the Wasserstein and Kolmogorov--Smirnov distances between the output of this algorithm and the true CESM. The quality of our bounds is demonstrated using numerical experiments.