Randomized Nyström Approximation of Non-negative Self-Adjoint Operators
SIAM Journal on Mathematics of Data Science · 30.06.2025 · 7 (2) · 670-698
DOI: 10.1137/24m165082x ↗Kurz gefasst
Fachartikel in der Zeitschrift SIAM Journal on Mathematics of Data Science, online erschienen am 13.05.2025. Verfasst von David Persson und 2 weiteren Autor:innen. Die Arbeit wurde bisher 3-mal zitiert (Crossref) und nennt 47 Literaturangaben. Gefördert von: Isaac Newton Institute for Mathematical Sciences, Office of Naval Research, Schweizerischer Nationalfonds zur Förderung der Wissenschaftlichen Forschung.
Abstract (Originalsprache)
The randomized singular value decomposition (SVD) has become a popular approach to computing cheap, yet accurate, low-rank approximations to matrices due to its efficiency and strong theoretical guarantees. Recent work by Boullé and Townsend [ Found. Comput. Math., 23 (2023), pp. 709–739] presents an infinite-dimensional analogue of the randomized SVD to approximate Hilbert–Schmidt operators. However, many applications involve computing low-rank approximations to symmetric positive semi-definite matrices. In this setting, it is well established that the randomized Nyström approximation is usually preferred over the randomized SVD. This paper explores an infinite-dimensional analogue of the Nyström approximation to compute low-rank approximations to non-negative self-adjoint trace-class operators. We present an analysis of the method and, along the way, improve the existing infinite-dimensional bounds for the randomized SVD. Our analysis yields bounds on the expected value and tail bounds for the Nyström approximation error in the operator, trace, and Hilbert–Schmidt norms. Numerical experiments on integral operators arising from Gaussian process sampling and Bayesian inverse problems are used to validate the proposed infinite-dimensional Nyström algorithm.
Förderung
- Isaac Newton Institute for Mathematical Sciences
- Office of Naval Research
- Schweizerischer Nationalfonds zur Förderung der Wissenschaftlichen Forschung
Zitieren
APA
Persson, D., Boullé, N., & Kressner, D. (2025). Randomized Nyström Approximation of Non-negative Self-Adjoint Operators. SIAM Journal on Mathematics of Data Science, 7(2), 670-698. https://doi.org/10.1137/24m165082x
Vancouver
Persson D, Boullé N, Kressner D. Randomized Nyström Approximation of Non-negative Self-Adjoint Operators. SIAM Journal on Mathematics of Data Science. 2025;7(2):670-698. doi:10.1137/24m165082x
BibTeX
@article{Persson2025,
author = {Persson, David and Boullé, Nicolas and Kressner, Daniel},
title = {Randomized Nyström Approximation of Non-negative Self-Adjoint Operators},
journal = {SIAM Journal on Mathematics of Data Science},
year = {2025},
volume = {7},
number = {2},
pages = {670--698},
doi = {10.1137/24m165082x}
}
EUVIMED