Randomized Nyström approximation of non-negative self-adjoint operators (Q6956547)

This interesting paper studies randomized Nyström approximations of non-negative self-adjoint operators. To set the stage, it is known for example that various randomized techniques are becoming increasingly popular for computing low-rank approximations to matrices. As a popular choice, the randomized singular value decomposition (SVD) is one of the primary choices, due to its performance, efficiency, strong theoretical guarantees, simplicity and reliability. Put simply, the randomized SVD for the matrix of interest say, \(C\), introduces the approximation \(BB*C\approx C\), where \(B\) is an orthonormal basis for the range of the matrix \(CD\) where \(D\) is a thin and tall random sketch matrix. Boull'e and Townsend have recently given an infinite-dimensional analogue of the randomized SVD to approximate Hilbert-Schmidt operators. The authors give a careful and detailed analysis of this method improving the existing infinite-dimensional bounds for the randomized SVD. Their analysis yields tail bounds and bounds on the expected value for the Nyström approximation error in the operator, trace, and Hilbert--Schmidt norms arising in this method. Numerical experiments support their findings when using integral operators arising from certain Gaussian process sampling and Bayesian inverse problems.\N\NThe paper is well written with a good set of references.