The C++ library Eigen provides an "unsupported" splines module which is giving me troubles.
The task is typical: a data-acquisition device provides me with a time series that is sort-of regular and has some holes with missing data. I want to fill in the gaps, for maybe a dozen data points, using a high-order polynomial.
I'm familiar with a spline function defined by data points or knots which it passes through. The Eigen math library provides a Spline class, which accepts "knot vector" and a matrix of "control points." But the resulting function doesn't actually pass through the control points at the knot values. I'm not sure what the quantitative relationship is to the input data… would like to know.
It has another submodule which provides functions that do pass through the original, given data points. But for some reason that is implemented using QR decomposition, which is slow unless I break the data into chunks. Then the resulting function goes way out of bounds for any missing data point, and the problem gets worse if I raise the polynomial degree. The greatest deviation occurs at the first interpolated point and then the function exponentially returns back to the expected range. So there's something wrong with the coefficients. I would expect it to at least be symmetrical.
The library's source code cites the NURBS book (Les Piegl and Wayne Tiller, The NURBS book (2nd ed.), 1997, 9.2.1 Global Curve Interpolation to Point Data).
Is there something fundamental I'm missing about splines? Is there a quick fix? I'm just trying to take the shortest route to interpolation. The function I'm interpolating isn't a polynomial, and harmonic analysis might be better. But I'm not aware of a suitable tool.
The function that accepts a "knot vector" and "control points" is probably using this data to construct a b-spline. B-spline curves don't pass through (interpolate) their control points.
To construct a spline curve that interpolates the input data points, you typically have to solve a linear system, so QR decomposition is not surprising.
If you use a low-degree spline (say cubic, degree = 3), then the linear system will be "banded" and therefore easier/faster to solve. Also, a spline with low degree is less likely to oscillate wildly.
This page has an example that shows creation of an interpolating spline with the Eigen package: http://forum.kde.org/viewtopic.php?f=74&t=98871 (I think).
Alternatively, there are many other packages available for creating splines. Just search for "spline interpolation code".