Radial basis function interpolation

Let $f(x)\; =\; \backslash exp(x\; \backslash cos(3\; \backslash pi\; x))$ and let $x\_k\; =\; \backslash frac\{k\}\{14\},\; k=0,\; 1,\; \backslash dots,\; 14$ be 15 equally spaced points on the interval $[0,\; 1]$. We will form $s(x)\; =\; \backslash sum\backslash limits\_\{k=0\}^\{14\}\; w\_k\; \backslash varphi(\backslash |x-x\_k\backslash |)$ where $\backslash varphi$ is a radial basis function, and choose $w\_k,\; k=0,\; 1,\; \backslash dots,\; 14$ such that $s(x\_k)=f(x\_k),\; k=0,\; 1,\; \backslash dots,\; 14$ ($s$ interpolates $f$ at the chosen points). In matrix notation this can be written as

: $$$$

\begin{bmatrix}

\varphi(\|x_0 - x_0\|) & \varphi(\|x_1 - x_0\|) & \dots & \varphi(\|x_{14} - x_0\|) \\

\varphi(\|x_0 - x_1\|) & \varphi(\|x_1 - x_1\|) & \dots & \varphi(\|x_{14} - x_{1}\|) \\

\vdots & \vdots & \ddots & \vdots \\

\varphi(\|x_0 - x_{14}\|) & \varphi(\|x_1 - x_{14}\|) & \dots & \varphi(\|x_{14} - 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 $\backslash varphi(r)\; =\; \backslash exp(-(\backslash varepsilon\; r)^2)$, the Gaussian, with a shape parameter of $\backslash 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), where it is still a very close approximation. More precisely the maximum error is roughly $\backslash |f\; -\; s\backslash |\_\backslash infty\; \backslash approx\; 0.0267414$ at $x\; =\; 0.0220012$.

{{multiple image

| align = center

| width = 500

| image1 = Radial Basis Function Interpolation.svg|

| caption1 = The function $f(x)\; =\; \backslash exp(x\; \backslash cos(3\; \backslash pi\; x))$ sampled at 15 uniform nodes between 0 and 1, interpolated using the Gaussian RBF with a shape parameter of $\backslash varepsilon\; =\; 3$.

| image2 = Radial Basis Function Interpolation Error.svg|

| caption2 = The interpolation error, $s(x)\; -\; f(x)$, for the plot to the left.

| direction =

| total_width =

| alt1 =

}}

The Mairhuber–Curtis theorem says that for any open set $V$ in $\backslash mathbb\{R\}^n$ with $n\; \backslash geq\; 2$, and $f\_1,\; f\_2,\; \backslash 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 singular.{{cite journal |last1=Mairhuber |first1=John C. |title=On Haar's Theorem Concerning Chebychev Approximation Problems Having Unique Solutions |journal=Proceedings of the American Mathematical Society |date=1956 |volume=7 |issue=4 |pages=609–615 |doi=10.2307/2033359 |jstor=2033359 }}

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(\backslash mathbf\{x\})\; =\; \backslash sum\backslash limits\_\{k=1\}^N\; \backslash sqrt\{\backslash |\backslash mathbf\{x\}\; -\; \backslash mathbf\{x\}\_k\backslash |^2\; +\; C\}$. This is interpolation using a basis of shifted multiquadric functions, now more commonly written as $\backslash varphi(r)\; =\; \backslash sqrt\{1+(\backslash varepsilon\; r)^2\}$, and is the first instance of radial basis function interpolation.{{

cite journal |

last1=Hardy |

first1=Rolland L. |

title=Multiquadric equations of topography and other irregular surfaces

|journal=Journal of Geophysical Research

|date=1971 |volume=7 |issue=8 |pages=1905–1915

|

doi=10.1029/JB076i008p01905 |

bibcode=1971JGR....76.1905H }} 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.{{

cite book |

last1=Fasshaur |

first1=Greg |

title=Meshfree Approximation Methods with MATLAB |

date=2007 |

publisher=World Scientific Publishing |

isbn=978-981-270-633-1

}}

{{Unreferenced section|date=May 2020}}Many radial basis functions have a parameter that controls their relative flatness or peakedness. This parameter is usually represented by the symbol $\backslash varepsilon$ with the function becoming increasingly flat as $\backslash varepsilon\; \backslash to\; 0$. For example, Rolland Hardy used the formula $\backslash varphi(r)\; =\; \backslash sqrt\{r^2\; +\; C\}$ for the multiquadric, however nowadays the formula $\backslash varphi(r)\; =\; \backslash sqrt\{1\; +\; (\backslash varepsilon\; r)^2\}$ is used instead. 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 $\backslash varphi(0)\; =\; 1$ as seen in the plots of the Gaussian functions and the bump functions.

File:Gaussian function shape parameter.png|A Gaussian function for several choices of $\backslash varepsilon$

File:Bump function shape.png|A plot of the scaled bump function with several choices of shape parameter

File:Bed of nails.png interpolant."]]

A consequence of this choice is that the interpolation matrix approaches the identity matrix as $\backslash varepsilon\; \backslash to\; \backslash 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{{snd}}the so-called "bed-of-nails interpolant" (as seen in the plot to the right).

File:Edge of ill-conditioning.png

On the opposite side of the spectrum, the condition number of the interpolation matrix will diverge to infinity as $\backslash varepsilon\; \backslash 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^\{12\}$ for double-precision floating point).

There are sometimes other factors to consider when choosing a shape-parameter. For example the bump function

$$\backslash varphi(r)\; =$$

\begin{cases}

\exp\left( -\frac{1}{1 - (\varepsilon r)^2}\right) & \mbox{ for } r<\frac{1}{\varepsilon} \\

0 & \mbox{ otherwise}

\end{cases}

has a compact support (it is zero everywhere except when ) leading to a sparse interpolation matrix.

Some radial basis functions such as the polyharmonic splines have no shape-parameter.

• Kriging

{{reflist}}

Category:Numerical analysis

Category:Approximation theory

Category:Interpolation