2024/04/01 by Persson, David, Boullé, Nicolas, Kressner, Daniel
#65F30 #65R10 #68W20 #FOS: Mathematics #Numerical Analysis (math.NA)
paper · doi:10.48550/arxiv.2404.00960
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 (FoCM, 2023) presents an infinite-dimensional analog 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 analog 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.