Knot placement for a natural cubic spline

Question

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?

Answer 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.