Randomized Nystr\"om approximation of non-negative self-adjoint operators
<|reference_start|>Randomized Nystr\"om approximation of non-negative self-adjoint operators: 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\'e 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{\"o}m approximation is usually preferred over the randomized SVD. This paper explores an infinite-dimensional analog of the Nystr{\"o}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{\"o}m approximation error in the operator, trace, and Hilbert-Schmidt norms. Numerical experiments for simple integral operators validate the proposed framework.<|reference_end|>
@article{persson2024randomized,
    title={Randomized Nystr\"om approximation of non-negative self-adjoint
  operators},
    author={David Persson, Nicolas Boull'e, Daniel Kressner},
    journal={arXiv preprint arXiv:2404.00960},
    year={2024},
    archivePrefix={arXiv},
    eprint={2404.00960},
    primaryClass={math.NA cs.NA}
}