2
$\begingroup$

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?

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

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
4
  • $\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$ Commented Feb 21, 2016 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$ Commented Feb 21, 2016 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
    Commented Feb 22, 2016 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
    Commented Feb 22, 2016 at 12:26

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .