# Analysis of stochastic Lanczos quadrature for spectrum approximation

Tyler Chen, Thomas Trogdon, Shashanka Ubaru
Proceedings of the 38th International Conference on Machine Learning, PMLR 139:1728-1739, 2021.

#### 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., $\Phi[\mathbf{A}](x) := \sum_{i=1}^{n} \frac{1}{n} {\large\unicode{x1D7D9}}[ \lambda_i[\mathbf{A}]\leq x]$. Spectral sums $\operatorname{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 12 t^{-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.
{"ft_lang_label":"__label__en","ft_lang_prob":0.6901756,"math_prob":0.99900526,"size":5482,"snap":"2022-40-2023-06","text_gpt3_token_len":1610,"char_repetition_ratio":0.10806864,"word_repetition_ratio":0.7542614,"special_character_ratio":0.28639182,"punctuation_ratio":0.109014675,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.9996376,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2022-09-30T09:51:57Z\",\"WARC-Record-ID\":\"<urn:uuid:9e2e2459-7d9b-49ef-ae54-15b274354220>\",\"Content-Length\":\"16440\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:d43fbfce-0e76-4aed-8ce7-fccd40c9927e>\",\"WARC-Concurrent-To\":\"<urn:uuid:7949b7cd-7cc9-4378-9373-7623284e9efd>\",\"WARC-IP-Address\":\"185.199.108.153\",\"WARC-Target-URI\":\"http://proceedings.mlr.press/v139/chen21s.html\",\"WARC-Payload-Digest\":\"sha1:N6NXRI2DBJXQX3O7TC4JOQXEURB3CEBO\",\"WARC-Block-Digest\":\"sha1:6RE6NVX2LKNL6SH5MTZEU65QGZHYZJOR\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2022/CC-MAIN-2022-40/CC-MAIN-2022-40_segments_1664030335448.34_warc_CC-MAIN-20220930082656-20220930112656-00346.warc.gz\"}"}