Algorithm-Agnostic Low-Rank Approximation of Operator Monotone Matrix Functions
David Persson, Raphael A. Meyer, Christopher Musco · SIAM Journal on Matrix Analysis and Applications · 2025
Abstract. Low-rank approximation of a matrix function, [Formula: see text], is an important task in computational mathematics. Most methods require direct access to [Formula: see text], which is often considerably more expensive than accessing [Formula: see text]. Persson and Kressner [ SIAM J. Matrix Anal., 44 (2023), pp. 415–944] avoid this issue for symmetric positive semidefinite matrices by proposing funNyström, which first constructs a Nyström approximation to [Formula: see text] using subspace iteration and then uses the approximation to directly obtain a low-rank approximation for [Formula: see text]. They prove that the method yields a near-optimal approximation whenever [Formula: see text] is a continuous operator monotone function with [Formula: see text]. We significantly generalize the results of Persson and Kressner beyond subspace iteration. We show that if [Formula: see text] is a near-optimal low-rank Nyström approximation to [Formula: see text], then [Formula: see text] is a near-optimal low-rank approximation to [Formula: see text] , independently of how [Formula: see text] is computed. Further, we show sufficient conditions for a basis [Formula: see text] to produce a near-optimal Nyström approximation [Formula: see text]. We use these results to establish that many common low-rank approximation methods produce near-optimal Nyström approximations to [Formula: see text] and therefore to [Formula: see text].