Analysis of stochastic Lanczos quadrature for spectrum approximation

Abstract

The cumulative empirical spectral measure (CESM) $\Phi [\mathbf{A}]:\mathbb{R}\to [0,1]$ of a $n\times n$ symmetric matrix $\mathbf{A}$ is defined as the fraction of eigenvalues of $\mathbf{A}$ less than a given threshold, i.e., $Φ[\mathbf{A}](x) := \sum_{i=1}^{n} \frac{1}{n} {\large\unicode{x1D7D9}}[ λ_i[\mathbf{A}]\leq x]$. Spectral sums $\mathrm{tr}(f[\mathbf{A}])$ can be computed as the Riemann--Stieltjes integral of $f$ against $\Phi [\mathbf{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|{\lambda }_{\text{max}}[\mathbf{A}]-{\lambda }_{\text{min}}[\mathbf{A}]|$ with probability at least $1-\eta$, by applying the Lanczos algorithm for $\lceil 12t^{-1}+\frac{1}{2}\rceil$ iterations to $\lceil 4(n+2{)}^{-1}{t}^{-2}\ln (2n{\eta }^{-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.

References in corpus (10)

• The Kernel Polynomial Method
• A Density Matrix-based Algorithm for Solving Eigenvalue Problems
• Chebyshev-BdG: an efficient numerical approach to inhomogeneous superconductivity
• An Investigation into Neural Net Optimization via Hessian Eigenvalue Density
• The Full Spectrum of Deepnet Hessians at Scale: Dynamics with SGD Training and Sample Size
• Disordered double Weyl node: Comparison of transport and density-of-states calculations
• Disordered double Weyl node
• Fast estimation of approximate matrix ranks using spectral densities
• Estimating the Spectral Density of Large Implicit Matrices
• The Lanczos Algorithm Under Few Iterations: Concentration and Location of the Output

Cited by in corpus (4)

• Error bounds for Lanczos-based matrix function approximation
• Sublinear Time Spectral Density Estimation
• Numerical computation of the equilibrium-reduced density matrix for strongly coupled open quantum systems
• A spectrum adaptive kernel polynomial method