Radial basis function interpolation
Radial basis function (RBF) interpolation is an advanced method in approximation theory for constructing high-order accurate interpolants of unstructured data, possibly in high-dimensional spaces.
The interpolant takes the form of a weighted sum of radial basis functions.
[1][2] RBF interpolation is a mesh-free method, meaning the nodes (points in the domain) need not lie on a structured grid, and does not require the formation of a mesh.
It is often spectrally accurate[3] and stable for large numbers of nodes even in high dimensions.
Many interpolation methods can be used as the theoretical foundation of algorithms for approximating linear operators, and RBF interpolation is no exception.
be 15 equally spaced points on the interval
is a radial basis function, and choose
In matrix notation this can be written as Choosing
, we can then solve the matrix equation for the weights and plot the interpolant.
Plotting the interpolating function below, we see that it is visually the same everywhere except near the left boundary (an example of Runge's phenomenon), where it is still a very close approximation.
More precisely the maximum error is roughly
points in the domain such that the interpolation matrix is singular.
[4] This means that if one wishes to have a general interpolation algorithm, one must choose the basis functions to depend on the interpolation points.
In 1971, Rolland Hardy developed a method of interpolating scattered data using interpolants of the form
This is interpolation using a basis of shifted multiquadric functions, now more commonly written as
, and is the first instance of radial basis function interpolation.
[5] It has been shown that the resulting interpolation matrix will always be non-singular.
This does not violate the Mairhuber–Curtis theorem since the basis functions depend on the points of interpolation.
Choosing a radial kernel such that the interpolation matrix is non-singular is exactly the definition of a strictly positive definite function.
Such functions, including the Gaussian, inverse quadratic, and inverse multiquadric are often used as radial basis functions for this reason.
[6] Many radial basis functions have a parameter that controls their relative flatness or peakedness.
These formulas are equivalent up to a scale factor.
This factor is inconsequential since the basis vectors have the same span and the interpolation weights will compensate.
By convention, the basis function is scaled such that
leading to stability when solving the matrix system.
The resulting interpolant will in general be a poor approximation to the function since it will be near zero everywhere, except near the interpolation points where it will sharply peak – the so-called "bed-of-nails interpolant" (as seen in the plot to the right).
On the opposite side of the spectrum, the condition number of the interpolation matrix will diverge to infinity as
In practice, one chooses a shape parameter so that the interpolation matrix is "on the edge of ill-conditioning" (eg.
) leading to a sparse interpolation matrix.
Some radial basis functions such as the polyharmonic splines have no shape-parameter.
