Greedy regularized kernel interpolation
It addresses the need for efficient surrogate models in expensive function approximation, offering a sparse solution with theoretical guarantees.
The paper proposes a greedy algorithm for sparse kernel regularized interpolation, achieving asymptotically quasi-optimal error rates while reducing evaluation cost for surrogate models.
Kernel based regularized interpolation is a well known technique to approximate a continuous multivariate function using a set of scattered data points and the corresponding function evaluations, or data values. This method has some advantage over exact interpolation: one can obtain the same approximation order while solving a better conditioned linear system. This method is well suited also for noisy data values, where exact interpolation is not meaningful. Moreover, it allows more flexibility in the kernel choice, since approximation problems can be solved also for non strictly positive definite kernels. We discuss in this paper a greedy algorithm to compute a sparse approximation of the kernel regularized interpolant. This sparsity is a desirable property when the approximant is used as a surrogate of an expensive function, since the resulting model is fast to evaluate. Moreover, we derive convergence results for the approximation scheme, and we prove that a certain greedy selection rule produces asymptotically quasi-optimal error rates.