Analysis of stochastic Lanczos quadrature for spectrum approximation

Author name not available (Why is that?)

Publication date: 13 May 2021

Abstract: The cumulative empirical spectral measure (CESM)

P h i [m a t h b f A] : m a t h b b R o [0, 1]

of a

n i m e s n

symmetric matrix

m a t h b f A

is defined as the fraction of eigenvalues of

m a t h b f A

less than a given threshold, i.e.,

P h i [m a t h b f A] (x) := s u m_{i = 1}^{n} f r a c 1 n l a r g e u n i c o d e x 1 D 7 D 9 [l a m b d a_{i} [m a t h b f A] l e q x]

. Spectral sums

o p e r a t o r n a m e t r (f [m a t h b f A])

can be computed as the Riemann--Stieltjes integral of

f

against

P h i [m a t h b f 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 : | l a m b d a_{e x t m a x} [m a t h b f A] - l a m b d a_{e x t m i n} [m a t h b f A] |

with probability at least

1 - e t a

, by applying the Lanczos algorithm for

l c e i l 12 t^{- 1} + f r a c 12 c e i l

iterations to

l c e i l 4 (n + 2)^{- 1} t^{- 2} l n (2 n e t a^{- 1}) c e i l

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.

Has companion code repository: https://github.com/chentyl/SLQ_analysis

This page was built for publication: Analysis of stochastic Lanczos quadrature for spectrum approximation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6367623)