Randomized Low-Rank Approximation of Monotone Matrix Functions
SIAM Journal on Matrix Analysis and Applications · 30.06.2023 · 44 (2) · 894-918
DOI: 10.1137/22m1523923 ↗Kurz gefasst
Fachartikel in der Zeitschrift SIAM Journal on Matrix Analysis and Applications, online erschienen am 08.06.2023. Verfasst von David Persson und 1 weiteren Autor:innen. Die Arbeit wurde bisher 11-mal zitiert (Crossref) und nennt 50 Literaturangaben. Gefördert von: SNSF.
Abstract (Originalsprache)
This work is concerned with computing low-rank approximations of a matrix function [Formula: see text] for a large symmetric positive semidefinite matrix [Formula: see text], a task that arises in, e.g., statistical learning and inverse problems. The application of popular randomized methods, such as the randomized singular value decomposition or the Nyström approximation, to [Formula: see text] requires multiplying [Formula: see text] with a few random vectors. A significant disadvantage of such an approach, matrix-vector products with [Formula: see text] are considerably more expensive than matrix-vector products with [Formula: see text], even when carried out only approximately via, e.g., the Lanczos method. In this work, we present and analyze funNyström, a simple and inexpensive method that constructs a low-rank approximation of [Formula: see text] directly from a Nyström approximation of [Formula: see text], completely bypassing the need for matrix-vector products with [Formula: see text]. It is sensible to use funNyström whenever [Formula: see text] is monotone and satisfies [Formula: see text]. Under the stronger assumption that [Formula: see text] is operator monotone, which includes the matrix square root [Formula: see text] and the matrix logarithm [Formula: see text], we derive probabilistic bounds for the error in the Frobenius, nuclear, and operator norms. These bounds confirm the numerical observation that funNyström tends to return an approximation that compares well with the best low-rank approximation of [Formula: see text]. Furthermore, compared to existing methods, funNyström requires significantly fewer matrix-vector products with [Formula: see text] to obtain a low-rank approximation of [Formula: see text], without sacrificing accuracy or reliability. Our method is also of interest when estimating quantities associated with [Formula: see text], such as the trace or the diagonal entries of [Formula: see text]. In particular, we propose and analyze funNyström++, a combination of funNyström with the recently developed Hutch++ method for trace estimation.
Förderung
- SNSF
Zitieren
APA
Persson, D., & Kressner, D. (2023). Randomized Low-Rank Approximation of Monotone Matrix Functions. SIAM Journal on Matrix Analysis and Applications, 44(2), 894-918. https://doi.org/10.1137/22m1523923
Vancouver
Persson D, Kressner D. Randomized Low-Rank Approximation of Monotone Matrix Functions. SIAM Journal on Matrix Analysis and Applications. 2023;44(2):894-918. doi:10.1137/22m1523923
BibTeX
@article{Persson2023,
author = {Persson, David and Kressner, Daniel},
title = {Randomized Low-Rank Approximation of Monotone Matrix Functions},
journal = {SIAM Journal on Matrix Analysis and Applications},
year = {2023},
volume = {44},
number = {2},
pages = {894--918},
doi = {10.1137/22m1523923}
}
EUVIMED