Radial basis function interpolation

Last updated November 20, 2023

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.

Examples

Let $f(x)=\exp(x\cos(3\pi x))$ 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=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{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 $\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), 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$ .

The function

f(x)=\exp(x\cos(3\pi x))

sampled at 15 uniform nodes between 0 and 1, interpolated using the Gaussian RBF with a shape parameter of

\varepsilon =3

.

The interpolation error,

s(x)-f(x)

, for the plot to the left.

Motivation

The Mairhuber–Curtis theorem says that for any open set $V$ in $\mathbb {R} ^{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{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.^[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 $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.^[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]

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 {r^{2}+C}}$ for the multiquadric, however nowadays the formula $\varphi (r)={\sqrt {1+(\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 $\varphi (0)=1$ as seen in the plots of the Gaussian functions and the bump functions.

A Gaussian function for several choices of $\varepsilon$
A plot of the scaled bump function 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 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^{12}$ for double-precision floating point).

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

\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 $r<{\tfrac {1}{\varepsilon }}$ ) leading to a sparse interpolation matrix.

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

Related Research Articles

<span class="mw-page-title-main">Gradient</span> Multivariate derivative (mathematics)

In vector calculus, the gradient of a scalar-valued differentiable function $of several variables is the vector field whose value at a point gives the direction and the rate of fastest increase. The gradient transforms like a vector under change of basis of the space of variables of . If the gradient of a function is non-zero at a point, the direction of the gradient is the direction in which the function increases most quickly from, and the magnitude of the gradient is the rate of increase in that direction, the greatest absolute directional derivative. Further, a point where the gradient is the zero vector is known as a stationary point. The gradient thus plays a fundamental role in optimization theory, where it is used to maximize a function by gradient ascent. In coordinate-free terms, the gradient of a function may be defined by:$

In mathematics, the Haar wavelet is a sequence of rescaled "square-shaped" functions which together form a wavelet family or basis. Wavelet analysis is similar to Fourier analysis in that it allows a target function over an interval to be represented in terms of an orthonormal basis. The Haar sequence is now recognised as the first known wavelet basis and is extensively used as a teaching example.

In mathematics, a unit vector in a normed vector space is a vector of length 1. A unit vector is often denoted by a lowercase letter with a circumflex, or "hat", as in $.$

In vector calculus, the Jacobian matrix of a vector-valued function of several variables is the matrix of all its first-order partial derivatives. When this matrix is square, that is, when the function takes the same number of variables as input as the number of vector components of its output, its determinant is referred to as the Jacobian determinant. Both the matrix and the determinant are often referred to simply as the Jacobian in literature.

In mathematics, a linear form is a linear map from a vector space to its field of scalars.

Levinson recursion or Levinson–Durbin recursion is a procedure in linear algebra to recursively calculate the solution to an equation involving a Toeplitz matrix. The algorithm runs in $Θ(n 2)$ time, which is a strong improvement over Gauss–Jordan elimination, which runs in Θ(n³).

In linear algebra, a Vandermonde matrix, named after Alexandre-Théophile Vandermonde, is a matrix with the terms of a geometric progression in each row: an $matrix$

<span class="mw-page-title-main">Path integral formulation</span> Formulation of quantum mechanics

The path integral formulation is a description in quantum mechanics that generalizes the stationary action principle of classical mechanics. It replaces the classical notion of a single, unique classical trajectory for a system with a sum, or functional integral, over an infinity of quantum-mechanically possible trajectories to compute a quantum amplitude.

Screw theory is the algebraic calculation of pairs of vectors, such as forces and moments or angular and linear velocity, that arise in the kinematics and dynamics of rigid bodies. The mathematical framework was developed by Sir Robert Stawell Ball in 1876 for application in kinematics and statics of mechanisms.

In statistics, econometrics, and signal processing, an autoregressive (AR) model is a representation of a type of random process; as such, it is used to describe certain time-varying processes in nature, economics, behavior, etc. The autoregressive model specifies that the output variable depends linearly on its own previous values and on a stochastic term ; thus the model is in the form of a stochastic difference equation which should not be confused with a differential equation. Together with the moving-average (MA) model, it is a special case and key component of the more general autoregressive–moving-average (ARMA) and autoregressive integrated moving average (ARIMA) models of time series, which have a more complicated stochastic structure; it is also a special case of the vector autoregressive model (VAR), which consists of a system of more than one interlocking stochastic difference equation in more than one evolving random variable.

In mathematics a radial basis function (RBF) is a real-valued function $whose value depends only on the distance between the input and some fixed point, either the origin, so that, or some other fixed point, called a center, so that . Any function that satisfies the property is a radial function. The distance is usually Euclidean distance, although other metrics are sometimes used. They are often used as a collection which forms a basis for some function space of interest, hence the name.$

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 cubic splines in one dimension.

In the field of mathematical modeling, a radial basis function network is an artificial neural network that uses radial basis functions as activation functions. The output of the network is a linear combination of radial basis functions of the inputs and neuron parameters. Radial basis function networks have many uses, including function approximation, time series prediction, classification, and system control. They were first formulated in a 1988 paper by Broomhead and Lowe, both researchers at the Royal Signals and Radar Establishment.

<span class="mw-page-title-main">Hierarchical RBF</span>

In computer graphics, a hierarchical RBF is an interpolation method based on Radial basis functions (RBF). Hierarchical RBF interpolation has applications in the construction of shape models in 3D computer graphics, treatment of results from a 3D scanner, terrain reconstruction, and others.

In mathematics, a set of n functions f₁, f₂, ..., f_n is unisolvent on a domain Ω if the vectors

In statistics, polynomial regression is a form of regression analysis in which the relationship between the independent variable x and the dependent variable y is modelled as an nth degree polynomial in x. Polynomial regression fits a nonlinear relationship between the value of x and the corresponding conditional mean of y, denoted E(y |x). Although polynomial regression fits a nonlinear model to the data, as a statistical estimation problem it is linear, in the sense that the regression function E(y | x) is linear in the unknown parameters that are estimated from the data. For this reason, polynomial regression is considered to be a special case of multiple linear regression.

In statistics and in machine learning, a linear predictor function is a linear function of a set of coefficients and explanatory variables, whose value is used to predict the outcome of a dependent variable. This sort of function usually comes in linear regression, where the coefficients are called regression coefficients. However, they also occur in various types of linear classifiers, as well as in various other models, such as principal component analysis and factor analysis. In many of these models, the coefficients are referred to as "weights".

The Kansa method is a computer method used to solve partial differential equations. Its main advantage is it is very easy to understand and program on a computer. It is much less complicated than the finite element method. Another advantage is it works well on multi variable problems. The finite element method is complicated when working with more than 3 space variables and time.

In machine learning, the radial basis function kernel, or RBF kernel, is a popular kernel function used in various kernelized learning algorithms. In particular, it is commonly used in support vector machine classification.

The Onsager–Machlup function is a function that summarizes the dynamics of a continuous stochastic process. It is used to define a probability density for a stochastic process, and it is similar to the Lagrangian of a dynamical system. It is named after Lars Onsager and Stefan Machlup who were the first to consider such probability densities.

References

↑ Hardy, Rolland (March 1971). "Multiquadric equations of topography and other irregular surfaces". Journal of Geophysical Research. 76 (8): 1905–1915. doi:10.1029/JB076i008p01905.
↑ Richard, Franke (January 1982). "Scattered Data Interpolation: Tests of Some Methods". Mathematics of Computation. 38 (157): 181–200. doi: 10.1090/S0025-5718-1982-0637296-4 .
↑ Buhmann, Martin; Nira, Dyn (June 1993). "Spectral convergence of multiquadric interpolation". Proceedings of the Edinburgh Mathematical Society. 36 (2): 319–333. doi: 10.1017/S0013091500018411 .
↑ Mairhuber, John C. (1956). "On Haar's Theorem Concerning Chebychev Approximation Problems Having Unique Solutions". Proceedings of the American Mathematical Society. 7 (4): 609–615. JSTOR 2033359.
↑ Hardy, Rolland L. (1971). "Multiquadric equations of topography and other irregular surfaces". Journal of Geophysical Research. 7 (8): 1905–1915. doi:10.1029/JB076i008p01905.
↑ Fasshaur, Greg (2007). Meshfree Approximation Methods with MATLAB. World Scientific Publishing. ISBN 978-981-270-633-1.

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[1] Hardy, Rolland (March 1971). "Multiquadric equations of topography and other irregular surfaces". Journal of Geophysical Research. 76 (8): 1905–1915. doi:10.1029/JB076i008p01905.

[2] Richard, Franke (January 1982). "Scattered Data Interpolation: Tests of Some Methods". Mathematics of Computation. 38 (157): 181–200. doi: 10.1090/S0025-5718-1982-0637296-4 .

[3] Buhmann, Martin; Nira, Dyn (June 1993). "Spectral convergence of multiquadric interpolation". Proceedings of the Edinburgh Mathematical Society. 36 (2): 319–333. doi: 10.1017/S0013091500018411 .

[4] Mairhuber, John C. (1956). "On Haar's Theorem Concerning Chebychev Approximation Problems Having Unique Solutions". Proceedings of the American Mathematical Society. 7 (4): 609–615. JSTOR 2033359.

[5] Hardy, Rolland L. (1971). "Multiquadric equations of topography and other irregular surfaces". Journal of Geophysical Research. 7 (8): 1905–1915. doi:10.1029/JB076i008p01905.

[6] Fasshaur, Greg (2007). Meshfree Approximation Methods with MATLAB. World Scientific Publishing. ISBN 978-981-270-633-1.

[1]

[2]

[3]

[4]

[5]

[6]