# Analysis of stochastic Lanczos quadrature for spectrum approximation

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

## Key facts

- Cited by 17 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 May 2021.

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

- [A Defense of the Quadratic Model](https://mlsanity.com/paper/2607.21716/) (2026)
- [PCENet: High Dimensional Surrogate Modeling for Learning Uncertainty](https://mlsanity.com/paper/2202.05063/) (2022)
- [Sharper Bounds for Chebyshev Moment Matching, with Applications](https://mlsanity.com/paper/2408.12385/) (2024)
- [WinQ: Accelerating Quantization-Aware Training of Language Models Around Saddle Points](https://mlsanity.com/paper/2605.17471/) (2026)
- [Moments, Random Walks, and Limits for Spectrum Approximation](https://mlsanity.com/paper/2307.00474/) (2023)
- [Multivariate trace estimation using quantum state space linear algebra](https://mlsanity.com/paper/2405.01098/) (2024)
- [Faster Spectral Density Estimation and Sparsification in the Nuclear Norm](https://mlsanity.com/paper/2406.07521/) (2024)
- [Spectral Estimation with Free Decompression](https://mlsanity.com/paper/2506.11994/) (2025)
- [Correlating Cross-Iteration Noise for DP-SGD using Model Curvature](https://mlsanity.com/paper/2510.05416/) (2025)
- [Hessian Spectral Analysis at Foundation Model Scale](https://mlsanity.com/paper/2602.00816/) (2026)
- [Local Hessian Spectral Filtering for Robust Intrinsic Dimension Estimation](https://mlsanity.com/paper/2605.01221/) (2026)
- [WeSpeR: Computing non-linear shrinkage formulas for the weighted sample covariance](https://mlsanity.com/paper/2410.14413/) (2024)
- [Fast Spectrum Estimation of Some Kernel Matrices](https://mlsanity.com/paper/2411.00657/) (2024)
- [Query Efficient Structured Matrix Learning](https://mlsanity.com/paper/2507.19290/) (2025)
- [Multi-Head Spectral-Adaptive Graph Anomaly Detection](https://mlsanity.com/paper/2512.22291/) (2025)
- [Theoretically and Practically Efficient Resistance Distance Computation on Large Graphs](https://mlsanity.com/paper/2601.11159/) (2026)
- [Cost-free Spectral Estimation for Adaptive Newton--Schulz in Matrix Optimizers](https://mlsanity.com/paper/2609.33047/) (2026)

## Abstract (arXiv)

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.