Fast least-squares curve fitting using quasi-orthogonal splines

Abstract

The paper presents a new approach to least-squares spline fitting of curves. A new approximately orthogonal basis, the Q-spline basis, for n-degree uniform spline space is developed. Using the Q-spline basis, it is shown that least squares spline fitting can be approximated via a single fixed sized inner product for each control point. Another convolution maps these Q-spline control points to the classical B-spline control points. Tight error bounds on the approximation induced errors are derived. Finally a procedure for discrete least squares spline fitting via convolution is presented along with several examples. A generalization of the result has relevance to the solution of regularized fitting problems.