Fast Fitting and Evaluation of Radial Basis Functions

Radial Basis functions are used to interpolate scattered data in two or more dimensions. Several applications in graphics, geophysics, and learning use interpolation methods based on RBFs. In particular there is a significant theory on RBF interpolation (see e.g., the book by Buhmann).

One issue with using the technique
for large data sets is that direct solution of the interpolation problem for *N * points scales as *O(N ^{3}) * while a
single evaluation of the radial basis function fit at a point itself requires

Af = [ 0 0
1
0 0]^{t}

If we stack cardinal functions for
each point, we obtain A^{-1}, albeit at great expense.

Beatson and Powell 1992, proposed to use the smoothness of the interpolant and required the cardinality properties be satisfied at a small number of points in the domain. This method was further developed by the groups of Powell and Beatson. The culmination of this work was an iterative Krylov subspace algorithm Faul et al. (2005)

· A.C. Faul, G. Goodsell, M. J. D. Powell, "A Krylov subspace algorithm for multiquadric interpolation in many dimensions," IMA Journal of Numerical Analysis (2005) 25, 1--24 link

Our Matlab implementation of this algorithm can be downloaded here. (Unzip the file, and see the comments in FGP05_iterator_web.m)

This algorithm
can be accelerated via use of the FMM for the matrix vector product required at
each step. However the algorithm involves a precomputation
stage for obtaining search directions. complexity of
these calculations is *O(N ^{2}).
*We modify this set-up stage and reduce its complexity to

·
Nail A. Gumerov and

The fast multipole for the biharmonic radial basis function is described here

·
Nail A. Gumerov and

Here is a picture of biharmonic RBF interpolation in 3D via the method

Here is a picture of multiquadric RBF interpolation in 2D via the method