Dealing with non-monotonically increasing data

Question

How do you deal with data that you need to be monotonically increasing in order to work with interpolation libs and other functions, when it is in fact not monotonically increasing?

Answer 1

If you want to remove the nonmonotonic structure without changing anything else, you can do an isotonic least squares fit:

http://en.wikipedia.org/wiki/Isotonic_regression

Answer 2

I'm confused. Data needs not be monotonic to interpolate. (Yes, there are monotonic curve fitting tools, but that seems not to be what you are asking for.) For example (in matlab)

x = 0:20;
y = sin(x);
xi = 0:.01:20;
yi = spline(x,y,xi);
plot(x,y,'o',xi,yi,'r-')

Perhaps you have a problem where the data comes from a relationship that is not single valued. As an example, points that lie around the circumference of a circle.

The problem is any function at a given value of x must yield a single prediction. But if you have a relationship that is not single valued, What can you do?

The general idea is to create a third variable, that allows you to predict x(t) and y(t) parametrically. You really need that third piece of information, as the sequence of the points is crucial. Typically one uses the cumulative chordal arc length between the points as the parameter t. Of course, in the case of a circle, one could have used polar angle as the parameter, but for the general problem the cumulative linear arc length works well.

x = rand(10,1);
y = rand(10,1);
t = [0;cumsum(diff(x).^2 + diff(y).^2)];
ti = linspace(0,t(end),1000);
xi = spline(t,x,ti);
yi = spline(t,y,ti);
plot(x,y,'o',xi,yi,'r-')

Answer 3

You can use parametric interpolation methods to fit a curve through a sequence of given data points $(x_i,y_i)$ where $x_i$ does not necessarily have to be less than $x_{i+1}$: http://www.ams.org/journals/mcom/1997-66-217/S0025-5718-97-00796-5/