# Difference between revisions of "Polyharmonic spline"

en>GregorB m (Section order per WP:FOOTERS) |
en>CmdrObot (sp: et.al.→et al.) |
||

Line 2: | Line 2: | ||

[[function approximation]] and data [[interpolation]]. | [[function approximation]] and data [[interpolation]]. | ||

They are very useful for interpolation of scattered data | They are very useful for interpolation of scattered data | ||

in many dimensions. A special case are [[ | in many dimensions. A special case are [[thin plate spline]]s.<ref>R.L. Harder and R.N. Desmarais: [http://www.mendeley.com/research/interpolation-using-surface-splines-1 Interpolation using surface splines]. Journal of Aircraft, 1972, Issue 2, pp. 189-191</ref><ref>J. Duchon: Splines minimizing rotation-invariant semi-norms in Sobolev spaces. Constructive Theory of Functions of Several Variables, W. Schempp and K. Zeller (eds), Springer, Berlin, pp.85-100</ref> | ||

== Definition == | == Definition == | ||

Line 103: | Line 103: | ||

top most formula for the provided <math>\mathbf{x}</math>. | top most formula for the provided <math>\mathbf{x}</math>. | ||

Many practical details to implement and use polyharmonic splines are given in the book of Fasshauer<ref>G.F. Fasshauer G.F.: [http://books.google.com/books?id=gtqBdMEqryEC Meshfree Approximation Methods with MATLAB]. World Scientific Publishing Company, 2007, ISPN-10: 9812706348</ref> | Many practical details to implement and use polyharmonic splines are given in the book of Fasshauer.<ref>G.F. Fasshauer G.F.: [http://books.google.com/books?id=gtqBdMEqryEC Meshfree Approximation Methods with MATLAB]. World Scientific Publishing Company, 2007, ISPN-10: 9812706348</ref> In Iske<ref> | ||

A. Iske: [http://www.springeronline.com/sgw/cda/frontpage/0,10735,5-10042-22-22344683-0,00.html Multiresolution Methods in Scattered Data Modelling], Lecture Notes in Computational Science and Engineering, 2004, Vol. 37, ISBN 3-540-20479-2, Springer-Verlag, Heidelberg.</ref> polyharmonic splines are treated as special cases of other multiresolution methods in scattered data modelling. | A. Iske: [http://www.springeronline.com/sgw/cda/frontpage/0,10735,5-10042-22-22344683-0,00.html Multiresolution Methods in Scattered Data Modelling], Lecture Notes in Computational Science and Engineering, 2004, Vol. 37, ISBN 3-540-20479-2, Springer-Verlag, Heidelberg.</ref> polyharmonic splines are treated as special cases of other multiresolution methods in scattered data modelling. | ||

Line 144: | Line 144: | ||

Recently, methods have been developed to overcome the aforementioned difficulties. For example | Recently, methods have been developed to overcome the aforementioned difficulties. For example | ||

Beatson et | Beatson et al.<ref>R.K. Beatson, M.J.D. Powell, and A.M. Tan A.M.: [http://imajna.oxfordjournals.org/cgi/content/short/27/3/427 Fast evaluation of polyharmonic splines in three dimensions]. IMA Journal of Numerical Analysis, 2007, 27, pp. 427-450.</ref> present a method to interpolate polyharmonic splines at one point in 3 dimensions in O(log(N)) instead of O(N). | ||

==See also== | ==See also== | ||

Line 150: | Line 150: | ||

*[[Radial basis function]] | *[[Radial basis function]] | ||

*[[Subdivision surface]] (emerging alternative to spline-based surfaces) | *[[Subdivision surface]] (emerging alternative to spline-based surfaces) | ||

*[[Spline (mathematics)|Spline]] | *[[Spline (mathematics)|Spline]] | ||

*[[Thin plate spline]] (a special case of a polyharmonic spline) | *[[Thin plate spline]] (a special case of a polyharmonic spline) | ||

## Latest revision as of 18:59, 23 June 2013

**Polyharmonic splines** are used for
function approximation and data interpolation.
They are very useful for interpolation of scattered data
in many dimensions. A special case are thin plate splines.^{[1]}^{[2]}

## Definition

where

- is a real-valued vector of nx independent variables,
- are N vectors of the same size as (often called centers) that the interpolated curve shall pass
- are the N weights of the basis functions.
- are the nx+1 weights of the polynomial.
- The linear polynomial with the weighting factors improves the interpolation close to the "boundary" and especially the extrapolation "outside" of the centers . If this is not desired, this term can also be removed (see also figure below).

The basis functions of **polyharmonic splines** are radial basis functions of the form:

Other values of exponent k are not useful (such as ), because a solution of the interpolation problem might no longer exist. To avoid problems at r=0 (since ln(0) = -∞), the polyharmonic splines with the natural logarithm might be implemented as:

The weights and are determined such that the function passes through given points (i=1,2,...,N) and fulfill the orthogonality conditions:

To compute the weights, a symmetric, linear system of equations has to be solved:

where

Under very mild conditions (essentially, that at least nx+1 points are not in a subspace; e.g. for nx=2 that at least 3 points are not on a straight line), the system matrix of the linear system of equations is nonsingular and therefore a unique solution of the equation system exists.

Once the weights are determined, interpolation requires to just evaluate the top most formula for the provided .

Many practical details to implement and use polyharmonic splines are given in the book of Fasshauer.^{[3]} In Iske^{[4]} polyharmonic splines are treated as special cases of other multiresolution methods in scattered data modelling.

## Examples

The next figure shows the interpolation through four points (marked by "circles") using different types of polyharmonic splines. The "curvature" of the interpolated curves grows with the order of the spline and the extrapolation at the left boundary (x < 0) is reasonable. The figure also includes the radial basis functions phi = exp(-r^{2}) which gives a good interpolation as well. Finally, the figure includes also
the non-polyharmonic spline phi = r^{2} to demonstrate, that this
radial basis function is not able to pass through the predefined points
(the linear equation has no solution and is solved in a least squares sense).

The next figure shows the same interpolation as in the first figure, with the only exception that the points to be interpolated are scaled by a factor of 100 (and the case phi = r^{2} is no longer included). Since phi = (scale*r)^{k} =
(scale^{k})*r^{k}, the factor (scale^{k}) can be extracted from matrix **A** of the linear equation system and therefore the solution is not influenced by the scaling. This is different for the logarithmic form of the spline, although the scaling has not much influence. This analysis is reflected in the figure, where the interpolation shows not much differences. Note, for other radial basis functions, such as phi = exp(-k*r^{2}) with k=1, the interpolation is no longer reasonable and it would be necessary to adapt k.

The next figure shows the same interpolation as in the first figure, with
the only exception that the polynomial term of the function is not
taken into account (and the case phi = r^{2} is no longer included). As can be seen from the figure, the extrapolation for x < 0 is no longer as "natural" as in the first figure for some of the basis functions. This indicates, that the polynomial term is useful if extrapolation occurs.

## Discussion

The main advantage of polyharmonic spline interpolation is that usually very good interpolation results are obtained for scattered data without performing any "tuning", so automatic interpolation is feasible. This is not the case for other radial basis functions. For example, the Gaussian function needs to be tuned, so that k is selected according to the underlying grid of the independent variables. If this grid is non-uniform, a proper selection of k to achieve a good interpolation result is difficult or impossible.

Main disadvantages are:

- To determine the weights, a linear system of equations must be solved, which is
**non-sparse**. The solution of a non-sparse linear system becomes no longer practical if the dimension n is larger as about 1000 (since the storage requirements are O(n^{2}) and the number of operations to solve the linear system is O(n^{3}). For example n=10000 requires about 100 Mbyte of storage and 1000 Gflops of operations).

- To perform the interpolation of M data points requires operations in the order of O(M*N). In many applications, like image processing, M is much larger than N, and if both numbers are large, this is no longer practical.

Recently, methods have been developed to overcome the aforementioned difficulties. For example
Beatson et al.^{[5]} present a method to interpolate polyharmonic splines at one point in 3 dimensions in O(log(N)) instead of O(N).

## See also

- Inverse distance weighting
- Radial basis function
- Subdivision surface (emerging alternative to spline-based surfaces)
- Spline
- Thin plate spline (a special case of a polyharmonic spline)

## References

- ↑ R.L. Harder and R.N. Desmarais: Interpolation using surface splines. Journal of Aircraft, 1972, Issue 2, pp. 189-191
- ↑ J. Duchon: Splines minimizing rotation-invariant semi-norms in Sobolev spaces. Constructive Theory of Functions of Several Variables, W. Schempp and K. Zeller (eds), Springer, Berlin, pp.85-100
- ↑ G.F. Fasshauer G.F.: Meshfree Approximation Methods with MATLAB. World Scientific Publishing Company, 2007, ISPN-10: 9812706348
- ↑ A. Iske: Multiresolution Methods in Scattered Data Modelling, Lecture Notes in Computational Science and Engineering, 2004, Vol. 37, ISBN 3-540-20479-2, Springer-Verlag, Heidelberg.
- ↑ R.K. Beatson, M.J.D. Powell, and A.M. Tan A.M.: Fast evaluation of polyharmonic splines in three dimensions. IMA Journal of Numerical Analysis, 2007, 27, pp. 427-450.