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(N3)  while a single evaluation of the radial basis function fit at a point itself requires O(N) operations. Much work by Powell, Beatson and co-workers focused on iterative methods for the solution of the RBF interpolation problem. Fast Multipole Methods for RBF evaluation, coupled with preconditioned iterative methods were developed. One approach created preconditioners via approximate cardinal functions. The ideal preconditioner must be close to the inverse of the matrix. The cardinal functions and the inverse are related. The cardinal function has value unity at one of the interpolation points and zero at all other points. Thus a cardinal function f satisfies

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(N2). We modify this set-up stage and reduce its complexity to O(N log N). The modifications are described in the following article

·                  Nail A. Gumerov and Ramani Duraiswami, Fast radial basis function interpolation via preconditioned Krylov iteration, 2006. pdf

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

·                  Nail A. Gumerov and Ramani Duraiswami, Nail A. Gumerov and Ramani Duraiswami, "Fast multipole method for the biharmonic equation in three dimensions," Journal of Computational Physics, Volume 215, Issue 1, 10 June 2006, Pages 363-383. pdf

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