Theory and Application of a Nonconforming Finite Element Method for the Efficient Approximation of Thin Plate Splines
by
Markus Hegland
Australian National University

The interpolation problem for thin plate splines in more than 1 dimension leads to a symmetric indefinite dense linear system of equations. Thus the direct solution of the interpolation equations is of complexity O(n³) and very large interpolation problems are not feasible even on high performance computers. Various methods have been investigated in the past in order to deal with this computational curse. These algorithms are based on conjugate gradients, multipole expansion and Lagrange interpolation. The fastest of these approaches allow the solution of interpolation problems with more than 10, 000 points on modern workstations especially if the interpolation points are on regular grids.

However, in the case of the smoothing problem one often encounters even larger numbers of data points, around 10⁶ or more in data mining applications. Unlike in the case of the interpolation problem one is not free to choose the location of these points which are typically scattered irregularly over the domain.

The approach discussed here uses finite elements to approximate the thin-plate splines. The elements are tensor products of piecewise linear functions in the variables. They are computed from a new variational characterisation of the thin-plate splines on compact domains which does not require high-order derivatives. The smoothing parameter is determined with a fast GCV method based on Krylov spaces. Applications to data mining and generalisations to higher dimensions using additive models will also be presented.

This is joint work with S. Roberts, R. Sidje, I. Altas, K. Burrage, N. Potter and O. Nielsen.

http://discus.anu.edu.au/~marcus

Date received: December 18, 1998