# How to algorithmically determine the best order of fit?

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?

• 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. – whuber Nov 1 '13 at 21:16
• 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. – Glen_b Nov 1 '13 at 23:16
• 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. – rhombidodecahedron Nov 2 '13 at 13:57
• 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. – Cowboy Trader Nov 3 '13 at 0:36

## 1 Answer

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.