EUVIMEDEUVIMED entdecken
Crossref

Randomized Low-Rank Approximation of Monotone Matrix Functions

David Persson, Daniel Kressner

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →