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 [SIAM J. Matrix Anal., 44 (2023), pp. 415-944] 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 A\widehat is a near-optimal low-rank Nystr"om approximation to A, then f(A\widehat ) is a near-optimal low-rank approximation to f(A), independently of how A\widehat is computed. Further, we show sufficient conditions for a basis Q to produce a near-optimal Nystr"om approximation A\widehat = AQ(QT AQ)\daggerQT 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).