5.5 Matrix function low-rank approximation

The previous sections describe algorithms for obtaining a low-rank approximation to a matrix $\vec{A}$. In some settings (e.g. trace estimation), we instead want a low-rank approximation to a matrix function $f(\vec{A})$ of a symmetric matrix $\vec{A}$, which we can access only through matrix-vector products. Products with $f(\vec{A})$ can be approximated using black-box methods like the Lanczos method for matrix functions, but each such product requires a number of products with $\vec{A}$. In this section, we describe two approaches for making more efficient use of the products with $\vec{A}$: Krylov-aware methods, which reuse the information generated by the underlying Krylov subspace methods, and, for operator monotone functions, approximations obtained by sketching $\vec{A}$ directly.

Krylov-aware methods¶

Krylov-aware methods make use of the 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 is 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 $br$ additional matrix-vector products with $\vec{A}$ (to extend $\mathcal{K}_s(\vec{A},\vec{\Omega})$ to $\mathcal{K}_{s+r}(\vec{A},\vec{\Omega})$), rather than the roughly $sbr$ products required to build $\mathcal{K}_{r+1}(\vec{A},\vec{Q}_s)$ by treating the $sb$ columns of $\vec{Q}_s$ as a fresh starting block.

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 $s$ to be quite large to obtain a good approximation to $f(\vec{A}) \vec{\Omega}$, but even the basis obtained with $s=1$ (which is basically like sketching $\vec{A}$) works well.

Operator monotone functions¶

The methods above still approximate products with $f(\vec{A})$ using Krylov subspace methods. For an important class of functions, we can avoid approximating products with $f(\vec{A})$ altogether: it suffices to compute a good low-rank approximation to $\vec{A}$ itself Persson & Kressner, 2023Persson et al., 2025.

Common examples of operator monotone functions include $f(x) = x^{\alpha}$ for $\alpha\in[0,1]$, $f(x) = \log(1+x)$, and $f(x) = x/(x+\lambda)$ for $\lambda \geq 0$.

Suppose $\vec{A}$ is positive semi-definite, and let $\widehat{\vec{A}}$ be a rank-$k$ approximation to $\vec{A}$ satisfying $\vec{0} \preceq \widehat{\vec{A}} \preceq \vec{A}$; e.g. the Nyström approximation, which always satisfies this condition. If $f(0) = 0$, then $f(\widehat{\vec{A}})$ also has rank at most $k$, and can be computed directly from the eigendecomposition of $\widehat{\vec{A}}$ — no products with $f(\vec{A})$ are required. Remarkably, if $\widehat{\vec{A}}$ is a near-optimal low-rank approximation to $\vec{A}$, then $f(\widehat{\vec{A}})$ is a near-optimal low-rank approximation to $f(\vec{A})$. The following version of this result is from Persson et al., 2025, which generalizes the analysis of the funNyström method of Persson & Kressner, 2023.

Note that since $\vec{A} - \widehat{\vec{A}} \succeq \vec{0}$ (and, by operator monotonicity, $f(\vec{A}) - f(\widehat{\vec{A}}) \succeq \vec{0}$), the traces above are exactly the nuclear norm errors; analogous guarantees hold in the Frobenius and operator norms Persson et al., 2025.