Radial basis function (RBF) interpolation is an advanced method in
approximation theory
In mathematics, approximation theory is concerned with how functions can best be approximated with simpler functions, and with quantitatively characterizing the errors introduced thereby. Note that what is meant by ''best'' and ''simpler'' wil ...
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 function A radial basis function (RBF) is a real-valued function \varphi whose value depends only on the distance between the input and some fixed point, either the origin, so that \varphi(\mathbf) = \hat\varphi(\left\, \mathbf\right\, ), or some other fixed ...
s, like for example Gaussian distributions. 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
A mesh is a barrier made of connected strands of metal, fiber, or other flexible or ductile materials. A mesh is similar to a web or a net in that it has many attached or woven strands.
Types
* A plastic mesh may be extruded, oriented, e ...
. It is often spectrally accurate 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 operator
In mathematics, and more specifically in linear algebra, a linear map (also called a linear mapping, linear transformation, vector space homomorphism, or in some contexts linear function) is a Map (mathematics), mapping V \to W between two vect ...
s, and RBF interpolation is no exception. RBF interpolation has been used to approximate
differential operators, integral operators, and
surface differential operators.
Examples
Let
and let
be 15 equally spaced points on the interval
radial basis function A radial basis function (RBF) is a real-valued function \varphi whose value depends only on the distance between the input and some fixed point, either the origin, so that \varphi(\mathbf) = \hat\varphi(\left\, \mathbf\right\, ), or some other fixed ...
, and choose
w_k, k=0, 1, \dots, 14 such that
s(x_k)=f(x_k), k=0, 1, \dots, 14 (
s interpolates
f at the chosen points). In matrix notation this can be written as
:
\begin
\varphi(\, x_0 - x_0\, ) & \varphi(\, x_1 - x_0\, ) & \dots & \varphi(\, x_ - x_0\, ) \\
\varphi(\, x_0 - x_1\, ) & \varphi(\, x_1 - x_1\, ) & \dots & \varphi(\, x_ - x_\, ) \\
\vdots & \vdots & \ddots & \vdots \\
\varphi(\, x_0 - x_\, ) & \varphi(\, x_1 - x_\, ) & \dots & \varphi(\, x_ - x_\, ) \\
\end
\beginw_0 \\ w_1 \\ \vdots \\ w_\end
= \beginf(x_0) \\ f(x_1) \\ \vdots \\ f(x_)\end.
Choosing
\varphi(r) = \exp(-(\varepsilon r)^2), the
Gaussian, with a shape parameter of
\varepsilon = 3, 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
In the mathematical field of numerical analysis, Runge's phenomenon () is a problem of oscillation at the edges of an interval that occurs when using polynomial interpolation with polynomials of high degree over a set of equispaced interpolation ...
), where it is still a very close approximation. More precisely the maximum error is roughly
\, f - s\, _\infty \approx 0.0267414 at
x = 0.0220012.
Motivation
The Mairhuber–Curtis theorem says that for any open set
V in
\mathbb^n with
n \geq 2, and
f_1, f_2, \dots, f_n linearly independent functions on
V, there exists a set of
n points in the domain such that the interpolation matrix
:
\begin
f_1(x_1) & f_2(x_1) & \dots & f_n(x_1) \\
f_1(x_2) & f_2(x_2) & \dots & f_n(x_2) \\
\vdots & \vdots & \ddots & \vdots \\
f_1(x_n) & f_2(x_n) & \dots & f_n(x_n)
\end
is
singular
Singular may refer to:
* Singular, the grammatical number that denotes a unit quantity, as opposed to the plural and other forms
* Singular homology
* SINGULAR, an open source Computer Algebra System (CAS)
* Singular or sounder, a group of boar ...
.
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
s(\mathbf) = \sum\limits_^N \sqrt. This is interpolation using a basis of shifted multiquadric functions, now more commonly written as
\varphi(r) = \sqrt, and is the first instance of radial basis function interpolation. 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.
Shape-parameter tuning
Many radial basis functions have a parameter that controls their relative flatness or peakedness. This parameter is usually represented by the symbol
\varepsilon with the function becoming increasingly flat as
\varepsilon \to 0. For example, Rolland Hardy used the formula
\varphi(r) = \sqrt for the
multiquadric, however nowadays the formula
\varphi(r) = \sqrt is used instead. These formulas are equivalent up to a scale factor. This factor is inconsequential since the
basis vectors have the same
span
Span may refer to:
Science, technology and engineering
* Span (unit), the width of a human hand
* Span (engineering), a section between two intermediate supports
* Wingspan, the distance between the wingtips of a bird or aircraft
* Sorbitan es ...
and the interpolation weights will compensate. By convention, the basis function is scaled such that
\varphi(0) = 1 as seen in the plots of the
Gaussian function
In mathematics, a Gaussian function, often simply referred to as a Gaussian, is a function of the base form
f(x) = \exp (-x^2)
and with parametric extension
f(x) = a \exp\left( -\frac \right)
for arbitrary real constants , and non-zero . It i ...
s and the
bump function
In mathematics, a bump function (also called a test function) is a function f: \R^n \to \R on a Euclidean space \R^n which is both smooth (in the sense of having continuous derivatives of all orders) and compactly supported. The set of all ...
s.
File:Gaussian function shape parameter.png, A Gaussian function
In mathematics, a Gaussian function, often simply referred to as a Gaussian, is a function of the base form
f(x) = \exp (-x^2)
and with parametric extension
f(x) = a \exp\left( -\frac \right)
for arbitrary real constants , and non-zero . It i ...
for several choices of \varepsilon
File:Bump function shape.png, A plot of the scaled bump function
In mathematics, a bump function (also called a test function) is a function f: \R^n \to \R on a Euclidean space \R^n which is both smooth (in the sense of having continuous derivatives of all orders) and compactly supported. The set of all ...
with several choices of shape parameter

A consequence of this choice, is that the interpolation matrix approaches the identity matrix as
\varepsilon \to \infty 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
In numerical analysis, the condition number of a function measures how much the output value of the function can change for a small change in the input argument. This is used to measure how sensitive a function is to changes or errors in the inpu ...
of the interpolation matrix will diverge to infinity as
\varepsilon \to 0 leading to ill-conditioning of the system. In practice, one chooses a shape parameter so that the interpolation matrix is "on the edge of ill-conditioning" (eg. with a condition number of roughly
10^ for
double-precision floating point).
There are sometimes other factors to consider when choosing a shape-parameter. For example the
bump function
In mathematics, a bump function (also called a test function) is a function f: \R^n \to \R on a Euclidean space \R^n which is both smooth (in the sense of having continuous derivatives of all orders) and compactly supported. The set of all ...
\varphi(r) =
\begin
\exp\left( -\frac\right) & \mbox r<\frac \\
0 & \mbox
\end
has a
compact support
In mathematics, the support of a real-valued function f is the subset of the function domain containing the elements which are not mapped to zero. If the domain of f is a topological space, then the support of f is instead defined as the smal ...
(it is zero everywhere except when
r< \tfrac) leading to a
sparse
Sparse is a computer software tool designed to find possible coding faults in the Linux kernel. Unlike other such tools, this static analysis tool was initially designed to only flag constructs that were likely to be of interest to kernel de ...
interpolation matrix.
Some radial basis functions such as the
polyharmonic spline In applied mathematics, polyharmonic splines are used for function approximation and data interpolation. They are very useful for interpolating and fitting scattered data in many dimensions. Special cases include thin plate splines and natural cu ...
s have no shape-parameter.
See also
*
Kriging
In statistics, originally in geostatistics, kriging or Kriging, also known as Gaussian process regression, is a method of interpolation based on Gaussian process governed by prior covariances. Under suitable assumptions of the prior, kriging g ...
References
{{reflist
Numerical analysis
Approximation theory
Interpolation