I am trying to approximate a function via a natural cubic spline. Suppose I sample the function on a grid i.e. I know the value of the function at a fixed number of equidistant points, say on 200 points. Further, suppose I want to choose a small number of knots (say 4 or 5) from amongst these sample points in order to define my spline. One obvious (but inefficient) way of doing this is to consider all 200 choose 5 combinations, and choose the best one, where best is defined as the spline which minimizes the squared error on all the 200 sample points. My question is, can I do better? i.e. is there a heuristic way of choosing the points which still yields reasonable (though not necessarily optimal) approximations, and is relatively efficient?
Knot placement for a natural cubic spline
1
$\begingroup$
approximation
interpolation
spline
1 Answers
1
I would first choose 5 reasonable points - my inclination would be equally spaced or Chebychev spacing (or your points closest to these). Then vary the choices by varying each point's index by 0, +1, and -1. Go through all 5 points and choose the one that improves the most. Keep on doing this until all the points chosen stay the same (i.e., no improvement is possible).
You also have to detect loops. This can be done by either storing all previous indices (using hashing to speed up the checking) or the ingenious trick of running in parallel one step and two steps and checking if the two threads agree.
-
01) Didn't know about the Remez algorithm. I'll take a look. Thanks. 2) I think I'll still have to store all the points, so that I don't evaluate the same set of points again. Though I guess in general I won't end up evaluating a given set of points more than twice, so perhaps the overhead of re-evaluation will be less than the overhead of storing and checking every time. I'll definitely explore this. 3) Instead of increasing the increments, I could also maybe restart at some random points (like in the EM algorithm), as long as the convergence happens quickly. Thanks again :) – 2012-12-20