2021/05/13 by Tyler Chen, Chen, Tyler, Thomas Trogdon +3 · 2 citations
Computer Science · Engineering · Mathematics · #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Matrix Theory and Algorithms #Numerical Analysis (math.NA) #Sparse and Compressive Sensing Techniques #Tensor decomposition and applications
paper · pdf · doi:10.48550/arxiv.2105.06595
openalex publication_date 2021/05/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The cumulative empirical spectral measure (CESM) Φ[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., Φ[A](x) := ∑i=1n (1)/(n) \large\unicodex1D7D9[ λi[A]≤ x]. Spectral sums tr(f[A]) can be computed as the Riemann--Stieltjes integral of f against Φ[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 + (1)/(2) \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.