ALGORITHM-AGNOSTIC LOW-RANK APPROXIMATION OF OPERATOR MONOTONE MATRIX FUNCTIONS

David Persson, Raphael A. Meyer, Christopher Musco

    Research output: Contribution to journalArticlepeer-review

    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 languageEnglish (US)
    Pages (from-to)1-21
    Number of pages21
    JournalSIAM Journal on Matrix Analysis and Applications
    Volume46
    Issue number1
    DOIs
    StatePublished - 2025

    Keywords

    • low-rank approximation
    • matrix functions
    • numerical analysis

    ASJC Scopus subject areas

    • Analysis

    Fingerprint

    Dive into the research topics of 'ALGORITHM-AGNOSTIC LOW-RANK APPROXIMATION OF OPERATOR MONOTONE MATRIX FUNCTIONS'. Together they form a unique fingerprint.

    Cite this