Name
Abstract | ||
|---|---|---|
The cumulative empirical spectral measure (CESM) Phi [A] : R -> [0, 1] of a n x n symmetric matrix A is defined as the fraction of eigenvalues of A less than a given threshold, i.e., Phi [A](x) := Sigma(n)(i=1)1/n 1[lambda(i)[A] <= x]. Spectral sums tr(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 vertical bar lambda(max) [A]- lambda(min) [A]vertical bar with probability at least 1 - eta, by applying the Lanczos algorithm for inverted right perpendicular12t(-1) + 1/2inverted left prepedicular iterations to inverted right perpedicular4(n + 2)(-1) t(-2) ln(2n eta(-1))inverted left perpendicular 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. |
Year | Venue | DocType |
|---|---|---|
2021 | INTERNATIONAL CONFERENCE ON MACHINE LEARNING, VOL 139 | Conference |
Volume | ISSN | Citations |
139 | 2640-3498 | 0 |
PageRank | References | Authors |
0.34 | 0 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Tyler Chen | 1 | 0 | 0.34 |
| Thomas Trogdon | 2 | 6 | 3.29 |
| shashanka ubaru | 3 | 58 | 8.97 |