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?

  • $\begingroup$ 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). $\endgroup$ – bubba Feb 21 '16 at 2:41
  • $\begingroup$ 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. $\endgroup$ – user52485 Feb 21 '16 at 16:42
  • $\begingroup$ Interpolation and fitting with splines are both common (in my business, anyway). $\endgroup$ – bubba Feb 22 '16 at 12:27

An outline of an approach:

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.

  • $\begingroup$ Thanks for the thoughts. This was my first thought too -- there are two unfavorable bits. First, the least squares approach favors the function passing close to the data; I'd like equal preference for anywhere within the rounding error. $\endgroup$ – user52485 Feb 21 '16 at 16:51
  • $\begingroup$ Second, when you split the curve, what do you do with the endpoints. You could split the curve and use that exact curve point as a new segment start/end point -- if the curve is far off, this will prevent the algorithm from converging. Or, you could choose a data point in the middle of your range and designate it as a curve start/end point. This makes that one point exact (no tolerance). I have attempted piecewise least squares formulations with un-anchored split points; I have not managed to make them stable. $\endgroup$ – user52485 Feb 21 '16 at 16:51
  • $\begingroup$ Regarding your second comment: you don't really split the curve. You just add another segment (or, in b-spline terms, you just add another knot). $\endgroup$ – bubba Feb 22 '16 at 12:22
  • 1
    $\begingroup$ Regarding your first point: I suppose you could design a smooth "distance" function that is zero when euclidean distance is less than epsilon and then increases. That will make the problem non-linear, I think. But the regular least-squares solution will give you a good place to start, so your iterations might succeed. $\endgroup$ – bubba Feb 22 '16 at 12:26

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.