  A multilevel kernel-based interpolation method, suitable for moderately
high-dimensional function interpolation problems, is proposed. The method,
termed multilevel sparse kernel-based interpolation (MLSKI, for short), uses
both level-wise and 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 multilevel interpolation algorithm is based on a hierarchical
decomposition of the data sites, whereby at each level the detail is added to
the interpolant by interpolating the resulting residual of the previous level.
On each level, anisotropic radial basis functions are used for solving a number
of small interpolation problems, which are subsequently linearly combined to
produce the interpolant. MLSKI can be viewed as an extension of $d$-boolean
interpolation (which is closely related to ideas in sparse grid and hyperbolic
crosses literature) to kernel-based functions, within the hierarchical
multilevel framework to achieve accelerated convergence. Numerical experiments
suggest that the new algorithm is numerically stable and efficient for the
reconstruction of large data in $\mathbb{R}^{d}\times \mathbb{R}$, for $d = 2,
3, 4$, with tens or even hundreds of thousands data points. Also, MLSKI appears
to be generally superior over classical radial basis function methods in terms
of complexity, run time and convergence at least for large data sets.
