I have a dataset that conforms to the restriction that if x2 >= x1 and y2 >= y1, then f(x2, y2) >= f(x1, y1). I would like to find a method of interpolation that preserves this assumption even among the interpolated values. Using e.g. scipy.interpolate.LinearNDInterpolator does not, and I suspect it's because (for example) as you move up, you might move closer to a point that is left of you, bringing the interpolated value down. Is there an existing interpolation implementation that will preserve upward-rightward monotonicity?

EDIT with more context:

I am attempting to write a program that will estimate the difficulty rating of a Stepmania chart.

• I wrote a routine that parses the steps from the chart file, and runs them through a simple algorithm that produces two numbers, essentially one representing the chart's speed and another its length. (I don't think the details of this process are relevant to this question but I'm happy to describe them if need be.)
• I have a corpus of charts that I assume are rated accurately. I run each of these charts through the above routine. This gives a set of x (speed) / y (length) / z (rating) values -- these are NOT yet monotonic in the way I described.
• I process those points with to force monotonicity, and extract the _training_set and _training_set_scores values, and store them. This is the dataset over which I want to interpolate.
• To estimate the rating of a new chart, I determine its speed and length values, then ask (currently) scipy.interpolate.LinearNDInterpolator for the rating estimate. This is the part that I want to preserve monotonicity, and this interpolation algo does not do that.

I have a dataset that conforms to the restriction that if x2 >= x1 and y2 >= y1, then f(x2, y2) >= f(x1, y1). I would like to find a method of interpolation that preserves this assumption even among the interpolated values. Using e.g. scipy.interpolate.LinearNDInterpolator does not, and I suspect it's because (for example) as you move up, you might move closer to a point that is left of you, bringing the interpolated value down. Is there an existing interpolation implementation that will preserve upward-rightward monotonicity?

EDIT with more context:

I am attempting to write a program that will estimate the difficulty rating of a Stepmania chart.

• I wrote a routine that parses the steps from the chart file, and runs them through a simple algorithm that produces two numbers, essentially one representing the chart's speed and another its length. (I don't think the details of this process are relevant to this question but I'm happy to describe them if need be.)
• I have a corpus of charts that I assume are rated accurately. I run each of these charts through the above routine. This gives a set of x (speed) / y (length) / z (rating) values -- these are NOT yet monotonic in the way I described.
• I process those points with https://github/alexfields/multiisotonic to force monotonicity, and extract the _training_set and _training_set_scores values, and store them. This is the dataset over which I want to interpolate.
• To estimate the rating of a new chart, I determine its speed and length values, then ask (currently) scipy.interpolate.LinearNDInterpolator for the rating estimate. This is the part that I want to preserve monotonicity, and this interpolation algo does not do that.

• python
• numpy
• scipy
• interpolation

• 1 You mentioned a restriction. But you did not motivate the restriction, nor give sufficient details for meaningful input. What is the nature of the manifold you are exploring, and what business use case motivates the problem? I am particularly concerned about IEEE – 754 roundoff issues impacting your strict monotonicity requirement. – J_H Commented Mar 15 at 21:45
• That's true, I will update the question now with the context of the question. I didn't originally because the use case is extremely "casual", and only serves as an approximation anyway, I mostly just want that constraint to be satisfied and almost no other consideration is relevant. – R. Woods Commented Mar 15 at 23:27
• I'm only aware of a 1D monotonic interpolator in SciPy, not an ND interpolator. – jared Commented Mar 16 at 3:40

1 Answer 1

The documentation is at pains to observe that things won't always work out:

For example, in two dimensions, the points (1,3) and (2,2) are not ordered

I assume that when you write "to force monotonicity", you're describing a filtering step which discards ambiguous cases such as the point pair described in the docs. There is a generative process out there in the world, people dancing to certain charts, which produces both ordered and unordered point pair observations. We can choose to discard a subset of observations. It's unclear how such technical filtering would impact your business Use Case.

then ask scipy.interpolate.LinearNDInterpolator for the rating estimate. This is the part that I want to preserve monotonicity, and this interpolation algo does not do that.

I can't reproduce the behavior you observe, and I see no documented reasons why LinearNDInterpolator is required to preserve the monotonicity constraints you desire. In particular, the size-of-effect is unclear, when I read the OP. Are we talking about FP roundoff in the last place? Or are there e.g. 10% errors observed, which make a measurable difference to the Business Problem that your use case is examining?

If there's random fuzz on your input values, and as described above you have a filtering step, you might consider applying a more aggressive filtering function. We're happy to play guessing games, but they're not always productive. If there is some hidden aspect in play, well then, spell it out for us.

cf: Kriging where by hypothesis there is an underlying smooth function, which we sample at just a limited number of discrete points.