MULTILEVEL SPARSE KERNEL-BASED INTERPOLATION

Emmanuil H. Georgoulis

doi:10.1137/110859610

Return

MULTILEVEL SPARSE KERNEL-BASED INTERPOLATION

2013-01-01

Emmanuil H. Georgoulis *

Jeremy Levesley

Fazli Subhan

DOI：10.1137/110859610

Original

Original request for help

Save

Abstract

En 中文

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 levelwise and directionwise 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 R-d x 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 overall performance for large data sets.

Keywords:

kernel-based interpolation

radial basis functions

multilevel

d-boolean interpolation

sparse grids

hyperbolic crosses