Scattered data reconstruction by regularization in B-spline and associated wavelet spaces

Abstract

The problem of fitting a nice curve or surface to scattered, possibly noisy, data arises in many applications in science and engineering. In this paper we solve the problem using a standard regularized least square framework in an approximation space spanned by the shifts and dilates of a single compactly supported function φ{symbol}. We first provide an error analysis to our approach which, roughly speaking, states that the error between the exact (probably unknown) data function and the obtained fitting function is small whenever the scattered samples have a high sampling density and a low noise level. We then give a computational formulation in the univariate case when φ{symbol} is a uniform B-spline and in the bivariate case when φ{symbol} is the tensor product of uniform B-splines. Though sparse, the arising system of linear equations is ill-conditioned; however, when written in terms of a short support wavelet basis with a well-chosen normalization, the resulting system, which is symmetric positive definite, appears to be well-conditioned, as evidenced by the fast convergence of the conjugate gradient iteration. Finally, our method is compared with the classical cubic/thin-plate smoothing spline methods via numerical experiments, where it is seen that the quality of the obtained fitting function is very much equivalent to that of the classical methods, but our method offers advantages in terms of numerical efficiency. We expect that our method remains numerically feasible even when the number of samples in the given data is very large. © 2009 Elsevier Inc. All rights reserved.