Allow `squeeze` to search over non-monotonic polynomials

[Sparks29032]

I think we should just allow squeeze to be non-monotonic. Like my previous suggestion, sort the grid (and in parallel the function values). Since we have discrete data, overlap is unlikely. In the case of overlap, take the average value of the overlaps. We would no longer have this error. I suggest warning the user if the final (only the final) squeeze parameters results in non-monotonicity and allowing them to disable it with another setting:

Warning: The squeeze morph has interpolated your morphed function from a non-monotonically increasing grid. This can result in strange behavior in the regions {list_of_regions}. To disable this setting, please enable --check-increasing.

If the final result is still on a monotonic increasing grid, good! That means only the intermediates were non-monotonic. This change only benefits us since if we do not implement this, the user will see an error on all cases where the grid is non-monotonic, and they recover the same behavior using check-increasing (or perhaps a better name for this option).

Use something like this to find non-unique values efficiently.

Use np.diff and check for negatives to quickly find the region where the interpolation has resulted in non-monotonicity. Specifically, for each set of continuous negative values in np.diff(a) for some array a, your non-monotonic region is a[idx2+1] to a[idx1] where idx1 is the index of where the negative region in np.diff(a) starts and and idx2 is the index where it ends. For example, if np.diff(a) is negative on the range 10-20, your non-monotonic region is a[21] to a[10]. You will not have index out of bounds errors from this since np.diff returns an array one smaller than the original.

Note that the grid size can change, but we implemented ways to handle that in morphrgrid.py.

[sbillinge]

I am ok with this. It is a bit odd, but if there is a unique mapping from domain to the function value, I guess it is ok, right?

[ycexiao]

@Sparks29032, I have one small question. Assume the resulting x_sqeeze is composed of sequential intervals c_1,c_2,... x_squeeze is monotonic in each interval. Two neighboring intervals have opposite monotonicity. If the continuous interval of c_i and c_j overlaps, but not the discrete grid. When we run sort, we will find that adjacent regions in the resulting y values will change abruptly from one interval to another, and the derivative's relation is not preserved. Are they expected?

[Sparks29032]

@ycexiao It is possible the derivative can become unbounded, but if our target is a sufficiently smooth function, I expect there to be some Lipschitz condition bounding our derivative as well since we are still performing a regression to minimize over this function. Furthermore, the changes in derivative are bounded by the lengths of these interval, so if your squeeze is small, the derivative is not going to become super jumpy. It may be interesting to formalize this claim and give some bounds relative to the maximum derivative in a region, though I digress.

In the scenario we do get extremely unexpected behavior, since we report the region of non-monotonicity, the user should know that this is a convergence artifact.

We should definitely run some numerical experiments to see the general behavior. Here is a suggested test:

• Take a case where squeeze converges when given all-zero initial values.
• Now randomly sample the initial values (perhaps from a zero-centered Gaussian) and see if we still converge to a similar polynomial.
  • Note that this does not mean that the coefficients are similar, but rather the residual between the two polynomials is small.

Here is another:

• Let your target function be the sine function applied to the grid of the objective function.
• See if you converge...

Some motivation for the second test. Take y = sin(x) sampled on the grid with spacing 0.1. Since sine is 2pi periodic, each sampled y point must necessarily be distinct. Thus, we can sort all the y. One can show (I will not do so here) that as the interval of our grid goes to infinity, the maximum of the discrete derivative of x with respect to y (this is the converse of your concern) also goes to infinity. This is sort of a worst case scenario.

[ycexiao]

@Sparks29032, sorry, I didn't get some parts about the tests. Can you explain more?

Take a case where squeeze converges when given all-zero initial values.

Which input's initial value?

Let your target function be the sine function applied to the grid of the objective function.

What is the objective function here? The morph y?

[Sparks29032]

Initial values for the squeeze parameters.

Objective function for both is squeeze. I just motivated the example using a function of y.

[Sparks29032]

Need more discussion. Can move this to 0.4.0 release.