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. 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 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. RBF interpolation has been used to approximate differential operators, integral operators, and surface differential operators. These algorithms have been used to find highly accurate solutions of many differential equations including Navier–Stokes equations, Cahn–Hilliard equation, and the shallow water equations.

Examples

Let $f(x)=\exp(x\cos(3\pi x))-1$ and let $x_{k}={\frac {k}{14}},k=0,1,\dots ,14$ be 15 equally spaced points on the interval $[0,1]$. We will form $s(x)=\sum \limits _{k=0}^{14}w_{k}\varphi (\|x-x_{k}\|)$ where $\varphi$ is a radial basis function, and choose $w_{k},k=1,2,\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{bmatrix}\varphi (\|x_{1}-x_{1}\|)&\varphi (\|x_{2}-x_{1}\|)&\dots &\varphi (\|x_{14}-x_{1}\|)\\\varphi (\|x_{1}-x_{2}\|)&\varphi (\|x_{2}-x_{2}\|)&\dots &\varphi (\|x_{2}-x_{14}\|)\\\vdots &\vdots &\ddots &\vdots \\\varphi (\|x_{1}-x_{14}\|)&\varphi (\|x_{2}-x_{14}\|)&\dots &\varphi (\|x_{n}-x_{14}\|)\\\end{bmatrix}}{\begin{bmatrix}w_{0}\\w_{1}\\\vdots \\w_{14}\end{bmatrix}}={\begin{bmatrix}f(x_{0})\\f(x_{1})\\\vdots \\f(x_{14})\end{bmatrix}}.$$

Choosing $\varphi (r)=\exp(-(\varepsilon r)^{2})$, the Gaussian, with a shape parameter of $\varepsilon \approx 3.05048$, 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 $\|f-s\|_{\infty }\approx 0.02476$.

The function $f(x)=\exp(x\cos(3\pi x))-1$ sampled at $n=15$ equally spaced nodes in the unit interval, and interpolated using the Gaussian RBF with a shape parameter of $\varepsilon \approx 3.05048$.

Motivation

The Mairhuber–Curtis theorem says that for any vector space $V$ with dimension higher than 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{bmatrix}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{bmatrix}}$$

is not singular.

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 {x} )=\sum \limits _{k=1}^{N}{\sqrt {\|\mathbf {x} -\mathbf {x} _{k}\|^{2}+C}}$. This is interpolation using a basis of shifted multiquadric functions, now more commonly written as $\varphi (r)={\sqrt {1+(\varepsilon r)^{2}}}$, 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 radial basis function. It has been shown that any function that is completely monotone will have this property, including the Gaussian, inverse quadratic, and inverse multiquadric functions.