Arbitrary function approximation in one dimension

Question

Suppose we have some arbitrary function $f: X \mapsto Y, X \in \mathbb{R}, Y \in [0, 1]$. It may be smooth but it may not. I am looking for some way to approximate this function given samples drawn from it, such that as the number of samples approaches infinity, the function approximation will get close to the true function. Where would be a good place to start?

Answer 1

Roughness penalty methods seem like a good fit. Here you fit a curve $f$ to a set of data points that minimizes the sum of squared errors with a roughness penalty:

$$ \sum_i \left( y_i - f(x_i) \right)^2 + \lambda \int \left( f''(x) \right)^2 dx $$

The penalty term has nice intuitive appeal, it penalizes the roughness for your curve, the total amount that the curve changes direction. This allows you to avoid just interpolating all the data points. By varying the penalty, you can control the overall smoothness of the approximation:

If you do want to just interpolate all the data points, you can find the interpolating curve which minimizes the penalty term, this is the limit of the above process as $\lambda \rightarrow 0$.

The method also has great practical appeal:

• It turns out that the solutions are natural cubic splines with knots at your data points. So a totally non-parametric statement can be reinterpreted as a parametric model.
• In the interpolation case, the solution is still a cubic spline. This turns out to be the interpolating curve of minimum roughness. In some sense, this is the interpolating curve with the minimum internal stress.
• It turns out that the curves can be fit in linear time (linear in the number of data points).
• It was used mechanically back in the day for engineering drawings, in particular, shipbuilding. A flexible metal spline was used to interpolate pegs on a drawing, which created curves of minimum energy that interpolated the pegs. This is the inspiration for the curve fitting method.

For more on cubic splines, you can see this answer. For more than you'll ever probably need to know about roughness penalty methods, check out this book.