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

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"om, which first constructs a Nystr"om 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 widehatA is a near-optimal low-rank Nystr"om approximation to A then f(widehatA) is a near-optimal low-rank approximation to f(A), independently of how widehatA is computed. Further, we show sufficient conditions for a basis Q to produce a near-optimal Nystr"om approximation widehatA = AQ(QT AQ)dagger QT A. We use these results to establish that many common low-rank approximation methods produce near-optimal Nystr"om approximations to A and therefore to f(A).