Interpolation of rounded data

I would like to interpolate (not fit) a data set whose points have been rounded.

Lets say I have some observations $y_i$ of a function sampled at $x_i$. The sample locations $x_i$ may be considered exact, but the observations $y_i$ were rounded to the hundredths place (except perhaps the first/last points, which may be considered exact if possible).

I would like to interpolate (say a piecewise cubic Bezier) where the interpolation passes within the rounding error of each observation.

I don't want to fit a global function (say a high order polynomial) because of all the problems with high order fits.

I don't want traditional interpolation because the $x_i$ are tightly sampled enough that the errors in $y_i$ give my later analysis problems.

The only approach I can think of so far is a general nonlinear optimization where the optimization variables are assumed error values $\epsilon_i$ for each observation, and the Bezier interpolation goes through $y_i+\epsilon_i$. Each $\epsilon_i$ would be constrained to stay within the appropriate bounds.

The objective function would be (something like) to minimize the changes in 3rd derivative at the Bezier segment joints (assuming the interpolation used was C2).

Hopefully this formulation wouldn't suffer lots of local optima, and an initial guess of $\epsilon_i=0$ would suffice.

As an Engineer, I would approach this problem numerically -- I could probably use an unconstrained optimizer with bounds constraints. If I squint, I see there is hope that the objective function might actually be linear. Good news for the lack of local optima -- but I probably wouldn't try to formulate it as a linear programming problem.

Is there a better way? Does this problem have a name? Any better ideas?

• You say "interpolate (not fit)". But then you say that the curve should pass through the data points "to within rounding error", which means you're doing fitting, not interpolation of the data values. Exactly interpolating the $y$ values doesn't really make sense, since they are rounded, so I assume you just want to get close (i.e. fitting). Commented Feb 21, 2016 at 2:41
• Ok, you can call it fitting if you want. However, I want the point to go exactly through the rounding error band with equal probability (not more likely to be nearest the data point). Likewise, a piecewise approach seems more appropriate, and they are more often associated with interpolation. Commented Feb 21, 2016 at 16:42
• Interpolation and fitting with splines are both common (in my business, anyway). Commented Feb 22, 2016 at 12:27

Choose some reasonable starting number, $n$. If you have no better ideas, just use $n=1$. Do a least-squares fit of your data using a cubic spline curve with $n$ segments. This is a linear problem, and software is available to do it. Check the deviation from the data points. If any of them are too large, increase $n$ and try again. If you want to be clever, add spline segments only in regions where the deviations from the data are large.
I'm assuming here that the desired curve is of the form $y=f(x)$. If you want a parametric curve of the form $x=x(t), y=y(t)$, then things are more complicated.