Sam Powerhttps://arxiv.org/abs/2306.03955
'Kernel Quadrature with Randomly Pivoted Cholesky'
- Ethan N. Epperly, Elvira Moreno
Kernel quadrature methods can become bottlenecked by the task of selecting quadrature nodes, which is often approached through the (approximate) solution of a difficult non-convex optimisation problem. This work proposes instead using a simple randomised strategy for node selection, motivated by recent developments in randomised numerical linear algebra, and which shows promising empirical performance.
Kernel quadrature with randomly pivoted Cholesky
This paper presents new quadrature rules for functions in a reproducing kernel Hilbert space using nodes drawn by a sampling algorithm known as randomly pivoted Cholesky. The resulting computational procedure compares favorably to previous kernel quadrature methods, which either achieve low accuracy or require solving a computationally challenging sampling problem. Theoretical and numerical results show that randomly pivoted Cholesky is fast and achieves comparable quadrature error rates to more computationally expensive quadrature schemes based on continuous volume sampling, thinning, and recombination. Randomly pivoted Cholesky is easily adapted to complicated geometries with arbitrary kernels, unlocking new potential for kernel quadrature.