Multilevel Sparse Kernel-Based Interpolation

Radial basis functions (RBFs) have been successfully applied for the last four decades for fitting scattered data in Rd, due to their simple implementation for any d. However, RBF interpolation faces the challenge of keeping a balance between convergence performance and numerical stability. Moreover, to ensure good convergence rates in high dimensions, one has to deal with the difficulty of exponential growth of the degrees of freedom with respect to the dimension d of the interpolation problem. This makes the application of RBFs limited to few thousands of data sites and/or low dimensions in practice. In this work, we propose a hierarchical multilevel scheme, termed sparse kernel-based interpolation (SKI) algorithm, for the solution of interpolation problem in high dimensions. The new scheme uses direction-wise multilevel decomposition of structured or mildly unstructured interpolation data sites in conjunction with the application of kernel-based interpolants with different scaling in each direction. The new SKI algorithm can be viewed as an extension of the idea of sparse grids/hyperbolic cross to kernel-based functions. To achieve accelerated convergence, we propose a multilevel version of the SKI algorithm. The SKI and multilevel SKI (MLSKI) algorithms admit good reproduction properties: they are numerically stable and efficient for the reconstruction of large data in Rd, for d = 2, 3, 4, with several thousand data. SKI is generally superior over classical RBF methods in terms of complexity, run time, and convergence at least for large data sets. The MLSKI algorithm accelerates the convergence of SKI and has also generally faster convergence than the classical multilevel RBF scheme.