Sampling-based Nyström Approximation and Kernel Quadrature
This work addresses kernel approximation challenges in machine learning, offering incremental improvements with new theoretical insights for broader applicability.
The paper tackles the problem of approximating positive definite kernels via Nyström methods, proving improved error bounds for i.i.d. sampling and introducing a refined subspace selection for non-i.i.d. points, with applications to kernel quadrature showing theoretical guarantees and numerical results.
We analyze the Nyström approximation of a positive definite kernel associated with a probability measure. We first prove an improved error bound for the conventional Nyström approximation with i.i.d. sampling and singular-value decomposition in the continuous regime; the proof techniques are borrowed from statistical learning theory. We further introduce a refined selection of subspaces in Nyström approximation with theoretical guarantees that is applicable to non-i.i.d. landmark points. Finally, we discuss their application to convex kernel quadrature and give novel theoretical guarantees as well as numerical observations.