Publication
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.