Stochastic Lanczos Quadrature - Randomized Numerical Linear Algebra with Examples

Recall that using $k-1$ matrix-vector products with $\vec{A}$ , the Lanczos method for quadratic forms produces an approximation $\Call{Lan-QF}_k(f;\vec{A},\vec{x})$ that is an approximation to $\vec{x}^\T f(\vec{A})\vec{x}$ . Stochastic Lanczos Quadrature (SLQ) simply combines this method with the Girard-Hutchinson trace estimator.

A simple application of the triangle inequality gives a bound on expected squared error of the SLQ estimator.

Proof

By the triangle inequality and since $(x+y)^2\leq 2(x^2+y^2)$ , we have

\begin{aligned} \hspace{1em}&\hspace{-1em}| \tr(f(\vec{A})) - \Call{SLQ}_{k,m}(f;\vec{A}) |^2 \\&\leq 2\left| \tr(f(\vec{A})) - \frac{1}{m}\sum_{i=1}^{m} \vec{x}_i^\T f(\vec{A})\vec{x}_i \right|^2 + 2\left| \frac{1}{m}\sum_{i=1}^{m} \vec{x}_i^\T f(\vec{A})\vec{x}_i - \Call{Lan-QF}_k(f;\vec{A},\vec{x}_i) \right|^2. \end{aligned}

Note that

\EE\left[ \left| \tr(f(\vec{A})) - \frac{1}{m}\sum_{i=1}^{m} \vec{x}_i^\T f(\vec{A})\vec{x}_i \right|^2 \right] = \VV\left[ \widehat{\tr}_m(f(\vec{A})) \right] = \frac{2 \| f(\vec{A}) \|_\F^2}{m},

where $\widehat{\tr}_m(\cdot)$ is the Girard--Hutchinson estimator.

Next, by the triangle inequality and Theorem 6.3,

\begin{aligned} \hspace{2em}&\hspace{-2em} \left| \frac{1}{m}\sum_{i=1}^{m} \vec{x}_i^\T f(\vec{A})\vec{x}_i - \Call{Lan-QF}_k(f;\vec{A},\vec{x}_i) \right| \\&\leq \frac{1}{m}\sum_{i=1}^{m} \left| \vec{x}_i^\T f(\vec{A})\vec{x}_i - \Call{Lan-QF}_k(f;\vec{A},\vec{x}_i) \right| \\&\leq \frac{1}{m} \sum_{i=1}^{m} \|\vec{x}_i\|^2 \min_{\deg(p)<2k-1} \max_{x\in[\lambda_n,\lambda_1]} | f(x) - p(x) |. \end{aligned}

Hence,

\begin{aligned} \hspace{2em}&\hspace{-2em} \EE\left[ \left| \frac{1}{m}\sum_{i=1}^{m} \vec{x}_i^\T f(\vec{A})\vec{x}_i - \Call{Lan-QF}_k(f;\vec{A},\vec{x}_i) \right|^2 \right] \\&\leq \frac{1}{m^2}\EE\left[ \left(\sum_{i=1}^{m} \|\vec{x}_i\|^2 \right)^2 \right] \min_{\deg(p)<2k-1} \max_{x\in[\lambda_n,\lambda_1]} | f(x) - p(x) | \end{aligned}

Now, note that $\sum_{i=1}^{m} \|\vec{x}_i\|^2$ is a Chi-squared random variable with $mn$ degrees of freedom. By looking on Wikipedia, we see that

\EE\left[ \left(\sum_{i=1}^{m} \|\vec{x}_i\|^2 \right)^2 \right] = 2mn + (mn)^2 \leq 3(mn)^2.

Combining all of the above gives the result.

Note that for “nice” functions $f(x)$ , the error of the best polynomial approximation decreases exponentially with $k$ Trefethen, 2019.

References¶

Chen, T. (2024). The Lanczos algorithm for matrix functions: a handbook for scientists. https://arxiv.org/abs/2410.11090
Chen, T., Trogdon, T., & Ubaru, S. (2025). Randomized Matrix-Free Quadrature: Unified and Uniform Bounds for Stochastic Lanczos Quadrature and the Kernel Polynomial Method. SIAM Journal on Scientific Computing, 47(3), A1733–A1757. 10.1137/23m1600414
Trefethen, L. N. (2019). Approximation Theory and Approximation Practice, Extended Edition. Society for Industrial. 10.1137/1.9781611975949

Randomized Numerical Linear Algebra with Examples

Matrix function trace approximation

Randomized Numerical Linear Algebra with Examples

Krylov Aware Methods