Preconditioners for low order thin plate spline approximations

A commonly used method for fitting smooth functions to noisy data is the thin-plate spline method. Traditional thin-plate splines use radial basis functions and consequently require the solution of a dense linear system of equations whose dimension grows linearly with the number of data points. Here we discuss a method based on low order polynomial functions with locally supported basis functions. An advantage of such an approach is that the resulting system of equations is sparse and its dimension depends linearly on the number of nodes in the finite element grid instead of the number of data points. Another advantage is that an iterative solver, such as the conjugate gradient method, can be used. However it can be shown that the system of equations is similar to those arising from Tikhonov regularisation, and consequently the equations are ill-conditioned for certain choices of the parameters. To ensure that the method is robust an appropriate preconditioner must be used. In this paper we present the discrete thin-plate spline method and explore a set of preconditioners. We discuss some of the properties that are unique to our particular formulation and verify that the multiplicative Schwarz method is an effective preconditioner.