Krylov Aware Methods

It’s natural to combine Krylov subspace methods with variance reduction techniques for trace estimation. This can lead to improvements over Stochastic Lanczos Quadrature, which is based on the Girard-Hutchinson estimator. Krylov aware methods take this one step further, by making use of interaction between Krylov subspace methods and randomized low-rank approximation techniques to more efficiently produce low-rank approximations to matrix functions Chen & Hallman, 2023Persson et al., 2025.

Let’s consider a Randomized-SVD type approach to obtaining a low-rank approximation to $f(\vec{A})$, where products with $f(\vec{A})$ are approximated via Krylov subspace methods.

The first key observation is that $\vec{Y}$ is contained in some block Krylov subspace

where $s$ is the number of steps taken by the KSM.

Let $\vec{Q}_{s}$ be an orthonormal basis for $\mathcal{K}_s(\vec{A},\vec{\Omega})$. We can compute $\vec{Q}_{s}$ using the same number of matrix-vector products with $\vec{A}$ as were used to compute $\vec{Y}$. However, $\range(\vec{Q})\subseteq \range(\vec{Q}_{s})$, so we may expect that $\vec{Q}_{s}\vec{Q}_{s}^\T f(\vec{A})$ is a better approximation to $f(\vec{A})$ than $\vec{Q}\vec{Q}^\T f(\vec{A})$.

However, since $\vec{Q}_{s}$ has many more columns than $\vec{Q}$, at first glance computing an approximation to $f(\vec{A})\vec{Q}_{s}$ seems to require many more products than computing an approximation to $f(\vec{A})\vec{Q}$.

The second key observation that because $\vec{Q}_{s}$ is a basis for a Krylov subspace, we can efficiently compute an approximation to $f(\vec{A}) \vec{Q}_{s}$. In particular, we have the following:

This means that quantities such as $\vec{Q}_s^\T f(\vec{A}) \vec{Q}_s$ can be approximated from $\mathcal{K}_{s+r}(\vec{A},\vec{\Omega})$. This requires just $nr$ additional matrix vector products with $\vec{A}$, rather than $n(q+1)$.

While this idea is simple, our algorithm can often perform much better than if matrix-vector products with $f(\vec{A})$ are treated as a black box. This is particularly true for functions like $f(x) = \sqrt{x}$, where we may require $q$ to be quite large to obtain a good approximation to $f(\vec{A}) \vec{\Omega}$, but even the basis obtained with $q=1$ (which is basically like sketching $\vec{A}$) works well.

Similar ideas are explored in Persson & Kressner, 2023Persson et al., 2025 where it is shown that sketching $\vec{A}$ instead of $f(\vec{A})$ is a good idea for operator monotone functions.