I am doing a least squares polynomial interpolation for 10,000 data sets that look mostly like one period of a sine curve, but whose values are not evenly spaced in the time domain, and can sometimes be quite noisy. A lot of them do just fine with a 3rd order fit (a + bx + cx^2 + dx^3) but some oscillate wildly (Runge's phenomenon) and need a 2nd order instead, and some are much better fitted with a 5th or even 8th order fit.

What methods exist for determining which fit is best with respect to avoiding both underfitting and overfitting?

One thing I think that I can do is to choose the largest order $m$ such that $m<2\sqrt{n}$ where $n$ is the number of points in my data set, and also check to make sure that there are some number of points in $2\sqrt{n}$ equally sized bins spanning the space. On the other hand, however, I would also like to penalize for having more parameters than necessary. Maybe I can also minimize $SSE(m)/(n-m-1)$. What better methods are out there for doing this?

  • $\begingroup$ Could you share with us the purpose of this fitting exercise? What will be done with your fits once you obtain them? That will help people identify good solutions among the myriad approaches that could apply. $\endgroup$
    – whuber
    Nov 1, 2013 at 21:16
  • 1
    $\begingroup$ Fitting high order polynomials is rarely a good idea. There are alternatives, but I'd like to understand what you are trying to do better first. $\endgroup$
    – Glen_b
    Nov 1, 2013 at 23:16
  • $\begingroup$ I'm working with a group of stellar astrophysicists - the fits will subsequently be used as models for further analysis. Some stars are very simple (almost perfectly sinusoidal) but some are far more complex. I'm playing with a variety of interpolation models and I'm trying to find the most robust way to automatically find out what would fit each star's characteristics. For a large subset of them, polynomial fits between 3rd and 10th order work fine. It's easy enough to inspect by eye to make this decision, but I would like to do it algorithmically. $\endgroup$ Nov 2, 2013 at 13:57
  • $\begingroup$ If you are not going to use any probabilistic models then cross validation is an option. If you have some idea of the probabilistic nature of the noise contaminating the samples then there are some tools like MLE+AIC, MDL, MML, etc. $\endgroup$ Nov 3, 2013 at 0:36

1 Answer 1


The obvious answer is to pick the polynomial order with the best cross-validation.

A slight improvement is to use something like Gaussian Processes, which tend to do the right thing without tuning parameters.

If you don't need function approximation and you're trying to lump them into groups, you could do perform some kind of kernel-based clustering, like Spectral Clustering. The use of a kernel is crucial here because you can confer to the algorithm exactly what it is that makes these observations similar.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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