Algorithm-agnostic low-rank approximation of operator monotone matrix functions

Abstract

Low-rank approximation of a matrix function, $f(A)$, is an important task in computational mathematics. Most methods require direct access to $f(A)$, which is often considerably more expensive than accessing $A$. Persson and Kressner (SIMAX 2023) avoid this issue for symmetric positive semidefinite matrices by proposing funNyström, which first constructs a Nyström approximation to $A$ using subspace iteration, and then uses the approximation to directly obtain a low-rank approximation for $f(A)$. They prove that the method yields a near-optimal approximation whenever $f$ is a continuous operator monotone function with $f(0)=0$. We significantly generalize the results of Persson and Kressner beyond subspace iteration. We show that if $\hat{A}$ is a near-optimal low-rank Nyström approximation to $A$ then $f(\hat{A})$ is a near-optimal low-rank approximation to $f(A)$, independently of how $\hat{A}$ is computed. Further, we show sufficient conditions for a basis $Q$ to produce a near-optimal Nyström approximation $\hat{A}=AQ(Q^{T}AQ{)}^{†}{Q}^{T}A$. We use these results to establish that many common low-rank approximation methods produce near-optimal Nyström approximations to $A$ and therefore to $f(A)$.