Browse Prior Art Database

Fast Least Squares Spline Fitting

IP.com Disclosure Number: IPCOM000117030D
Original Publication Date: 1995-Dec-01
Included in the Prior Art Database: 2005-Mar-31
Document File: 2 page(s) / 37K

IBM

Related People

Flickner, M: AUTHOR [+5]

Abstract

Disclosed is a method to do least squares spline fitting via convolution. In general, the least squares fitting problem can be expressed in matrix form as P=HC where C is the k x 1 vector of control points, H is the k x k Gram matrix formed by a suitable inner product of the basis functions, and P is a k x 1 vector formed as the inner product of the data with the basis functions. From the above equation it is easy to see that control points can be computed by solving a linear system. If an orthogonal spline basis is used, then H is diagonal, thus having a trivial inverse.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 79% of the total text.

Fast Least Squares Spline Fitting

Disclosed is a method to do least squares spline fitting via
convolution.  In general, the least squares fitting problem can be
expressed in matrix form as P=HC where C is the k x 1 vector of
control points, H is the k x k Gram matrix formed by a suitable inner
product of the basis functions, and P is a k x 1 vector formed as the
inner product of the data with the basis functions.  From the above
equation it is easy to see that control points can be computed by
solving a linear system.  If an orthogonal spline basis is used, then
H is diagonal, thus having a trivial inverse.

The B-spline basis can be orthogonalized via the Gram-Schmidt
orthogonalization procedure to create a basis called the O-spline
basis.  For uniform splines, the O-spline basis can be normalized and
truncated creating another basis called Q-spline basis.  The Q-spline
basis has the properties that each basis function is a translation of
a single basis function.  This enables least squares spline fitting
via k inner products, where k is the number of knots in the spline.
This allows for considerable computational saving when compared to
solving a linear system.  The details on how to construct Q-splines
as well as proofs of strong error bounds can be found in (1).  Copies
of these reports can be found in (*).
(*)
author         Myron Flickner, Jim Hafner, Eduardo Rodriguez, and
Jorge Sanz
tit...