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 [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).
Original language | English (US) |
---|---|
Pages (from-to) | 1-21 |
Number of pages | 21 |
Journal | SIAM Journal on Matrix Analysis and Applications |
Volume | 46 |
Issue number | 1 |
DOIs | |
State | Published - 2025 |
Keywords
- low-rank approximation
- matrix functions
- numerical analysis
ASJC Scopus subject areas
- Analysis