7
$\begingroup$

I noticed that spline interpolation with a degree higher than 3 (everything beyond cubic splines) have a very high interpolation error, hence the prediction is mostly awful. I've come across various lecture notes, slides and Youtube videos that simply indicate that cubic splines (3rd degree) are optimal and that anything beyond that is a bad idea. These sources however never mention why this is the case.

Can anyone explain to me why this is the case and maybe give me a title/link to a journal/conference paper that explains this or maybe even gives a proof.

$\endgroup$
  • 1
    $\begingroup$ I have to reference this overfitting phenomena, but I can't find any academic literature that mention this. Do you guys maybe know of an article/book/thesis I can use? $\endgroup$ – goocreations Oct 1 '13 at 15:14
10
$\begingroup$

There is no such proof because it's not always true. It's a rule of thumb, because I guarantee that you could come up with a situation- an infinite number of situations actually- where higher order splines would do better than cubic splines. The optimal spline order for any given situation is the exact same order as the system you are trying to model. If the order is the same and your data points are error free (never the case, of course, except for in theoretical problems), then you should be able to model the system perfectly.

The reason they recommend not to go higher than cubic splines is because overfitting is really, really bad. Overfitting can greatly magnify errors, while "underfitting" (choosing a spline method with an order lower than the order of the system you are modelling) introduces some low pass filtering that is either not that bad or sometimes even beneficial.

$\endgroup$
  • $\begingroup$ +1. Note that choosing a lower order fit than the model being representing is not 'pseudo' low-pass filtering - it is a form of low pass filtering in its own right. $\endgroup$ – Tarin Ziyaee Oct 24 '13 at 17:34
  • $\begingroup$ @user4619 You're right. I meant that it is not low-pass filtering in the sense that we usually think about with FIR and IIR filters, but it is low-pass filtering, it's just not easily characterizable. Edited the answer. $\endgroup$ – Jim Clay Oct 25 '13 at 13:33
3
$\begingroup$

Here is a rough outline (which may or may not be correct). Spline is a polynomial interpolation, i.e. every section of the curve between to neighboring support points is a polynomial. A polynomial of order N has N+1 coefficients (degrees of freedom) and hence can satisfy 4 boundary conditions per section. The choice of boundary conditions determines the type of interpolation. For a spline that is hitting the supporting points exactly and creating a continuous first and second derivatives.

For higher order splines you can get higher order derivatives to be continuous as well but that tends to add a lot of high frequency content at sharper transitions and often results in "ringing" or excessive oscillation. The original words "spline" stems from a flexible ruler that people used to make "mechanical" interpolations. I think you can actually show by analyzing the ruler mechanics the cubic spline matches that behavior.

As with most things, it depends on your application and what you want to do. An interesting alternative to cubic splines are hermitian interpolations which can guarantee monotony and make sure that the interpolation never swings outside the supporting points. From the MATLAB help function

Tips

spline constructs  in almost the same way pchip constructs . However, spline chooses the slopes at the  differently, namely to make even  continuous. This has the following effects:

   - spline produces a smoother result, i.e.  is continuous.    
   - spline produces a more accurate result if the data consists of values of a smooth function.    
   - pchip has no overshoots and less oscillation if the data are not smooth.    
   - pchip is less expensive to set up.
   - The two are equally expensive to evaluate.
$\endgroup$
2
$\begingroup$

There are several kinds of splines, with conflicting goals:

  • go near the input data points
  • smooth curves vs. wiggly

For a few data points, you may want to interpolate exactly; but for thousands of points, or even a dozen with noise, interpolating exactly will wiggle. Most spline fitters have parameters to tradeoff nearness of fit vs. overall smoothness. Here's a plot of degree 1 splines (piecewise linear, connect-the-dots) with data = line + noise. You see that fitting the data exactly zig-zags up and down, while maximum smoothing gives a straight line:

enter image description here There are splines for different jobs, depending on the input data and the new points in between: tens / millions of points, how noisy, scattered / on a grid, 1d 2d 3d ... On a regular grid in 3d for example, a spline of degree $d$ will look at $(d + 1)^3$ neighbors of each query point: 1 (nearest neighbour), 8 (trilinear), 27, 64 ... Can you afford 64 ? Do you need 64 ? It depends.

(Very briefly, B-splines smooth;
Catmull-Rom splines interpolate, e.g. frames of movies;
mixtures like 1/3 B + 2/3 CR are usefully in between.)

How does polynomial degree affect wiggliness ? See Runge's phenomenon .

On overshoot in 1d 2d 3d ... see (ahem) this question on math.stackexchange.
On the dangers of EXtrapolation with splines beyond linear, see this on SO.

See also stackoverflow.com/questions/tagged/spline .

$\endgroup$
0
$\begingroup$

Another way to look at this is by noticing that most interesting images and data sets are "smooth" to a certain degree. Interpolating gaussian noise, for example, should work better with higher order splines.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.