A novel class of stabilized greedy kernel approximation algorithms: Convergence, stability & uniform point distribution

Abstract

Kernel based methods provide a way to reconstruct potentially high-dimensional functions from meshfree samples, i.e., sampling points and corresponding target values. A crucial ingredient for this to be successful is the distribution of the sampling points. Since the computation of an optimal selection of sampling points may be an infeasible task, one promising option is to use greedy methods. Although these methods may be very effective, depending on the specific greedy criterion the chosen points might quickly lead to instabilities in the computation. To circumvent this problem, we introduce and investigate a new class of \textit{stabilized} greedy kernel algorithms, which can be used to create a scale of new selection strategies. We analyze these algorithms, and in particular we prove convergence results and quantify in a precise way the distribution of the selected points. These results allow to prove, in the case of certain Sobolev kernels, that the algorithms have optimal stability and optimal convergence rates, including for functions outside the native space of the kernel. The results also apply to the case of the usual $P$-greedy algorithm, significantly improving state-of-the-art results available in the literature. Illustrative experiments are presented that support the theoretical findings.

References in corpus (2)

• Convergence analysis of the Generalized Empirical Interpolation Method
• Kernel Methods for Surrogate Modeling

Cited by in corpus (15)

• Deep Reinforcement Learning for Turbulence Modeling in Large Eddy Simulations
• Analysis of target data-dependent greedy kernel algorithms: Convergence rates for $f$-, $f\cdot P$- and $f/P$-greedy
• Kernel methods for center manifold approximation and a data-based version of the Center Manifold Theorem
• A hierarchical expected improvement method for Bayesian optimization
• Convergence Guarantees for Gaussian Process Means With Misspecified Likelihoods and Smoothness
• Sampling based approximation of linear functionals in Reproducing Kernel Hilbert Spaces
• On the optimality of target-data-dependent kernel greedy interpolation in Sobolev Reproducing Kernel Hilbert Spaces
• Stability of convergence rates: Kernel interpolation on non-Lipschitz domains
• Adaptive meshfree approximation for linear elliptic partial differential equations with PDE-greedy kernel methods
• Kernel-Based Models for Influence Maximization on Graphs based on Gaussian Process Variance Minimization
• Kriging prediction with isotropic Matérn correlations: Robustness and experimental design
• Comparing Scale Parameter Estimators for Gaussian Process Interpolation with the Brownian Motion Prior: Leave-One-Out Cross Validation and Maximum Likelihood
• A Framework for Verifiable and Auditable Federated Anomaly Detection
• Greedy algorithms for learning via exponential-polynomial splines
• Refined rates of convergence for target-data dependent greedy generalized interpolation with Sobolev kernels