A novel(?), first order smooth, invertible interpolation scheme

[RobinSchmidt]

The last week, I have been working on a new way to interpolate monotonically increasing (or decreasing) data. The way I came up with has a couple of nice, desirable features. Firstly, of course, the resulting interpolants will be also monotonic within their segments between the nodes and therefore invertible. Secondly, the inverse interpolant is of the exact same functional form and the process of inverting the interpolant is actually trivial. I call this interpolation scheme "linear fractional interpolation" which I like to abbreviate as "linfrac". The whole scheme is centered around the so called "linear fractional transformation" which is a function of the general form y = f(x) = (ax + b) / (cx + d). Just like cubic Hermite interpolation, linfrac interpolation requires the user to provide target values for the slopes at the datapoints that are then matched by both curve segments adjacent to the respective node.

The implementation is currently located in Prototypes.h in the class rsLinearFractionalInterpolator (currently available only in the "work" branch of the repo). There are also some comments there that explain in some more detail the mathematical ideas behind this interpolation scheme. Here is a plot that was created with this implementation:

The important curve is the light-gray one that I labeled as "Linear Fractional". It shows the continuous interpolating function that is produced by this scheme from the white datapoints. Beyond the actual datapoints left and right, there's also some extrapolation going on. For reference, in this dark cyanish tone is the linear interpolant and in the purpleish tone a cubic Hermite interpolant. The darker gray curve is the inverse linfrac interpolant. The target values for the derivatives for the Hermite as well as the linfrac interpolant were obtained by a numerical differentiation routine from class rsNumericDifferentiator.

As we can can clearly see, the linfrac interpolant produces a monotonic interpolation curve, as desired. This is in stark contrast to the Hermite interpolant which features a strong oscillation in the middle. We can also clearly see that the inverse linfrac interpolant mirrors the the linfrac interpolant across the line y = x, as we expect from an inverse function.

I'll soon post some more details about the math behind it...

[RobinSchmidt]

My motivation behind developing this scheme was that I actually do occasionally need an invertible interpolation scheme for monotonic data. An example for this is in the sinusoidal modeling framework in the analysis part where I first time-warp the input signal to flatten out the pitch variations, then do the analysis on the pitch-flattened signal, and then undo the pre-flattening by un-warping the time-stamps of the analysis datapoints. This unwarping step involves an inverse interpolation of the time warping map. And that warping map is a bunch of monotonically increasing datapoints that I need to interpolate in the pre-warping step and then inverse-interpolate in post-unwarping step. The way I'm currently doing it is to just use linear interpolation for pre-warping and post-unwarping. Linear interpolation is trivially invertible - but it's admittedly not very smooth. I thought, it might be nicer to have a smoother interpolation scheme for that. Potentially, that may improve the quality of the sinusoidal analysis framework when I eventually integrate it there. ...I guess, it will probably not make a big difference - linear interpolation should actually be good enough for this particular purpose - but who knows? We'll see. But having such a thing in the library may certainly come in handy at some point.

[RobinSchmidt]

...OK - now let's talk a little bit about the math.

Linear interpolation is easily invertible but it's not first order smooth. Polynomial interpolation schemes can be made even smoother than first order but are in general not invertible - at least not easily - and even if it is invertible (because one has somehow restricted the interpolant to be monotonic), the inverse interpolating function will be of a completely different kind, i.e. come from a different class of functions and has to be computed with a different (more complicated) algorithm. For example, if you interpolate data given in arrays x[n], y[n] using piecewise cubic polynomials to produce a continuous function y = f(x), the (exact) inversion of the produced interpolant y = f(x) that gives our x = f(y), will not be a piecewise cubic but instead will be defined by using a root-finder applied to the piecewise cubic y = f(x). So, the inverse interpolant will be something like a piecewise "cube-rooty" function which is a very different type of function than a cubic polynomial. It's actually even more complicated than a simple cube-root function, but you get the point.

Linear fractional interpolation solves this problem by using as interpolants between the nodes functions of the general form

y = f(x) = (ax + b) / (cx + d).

These functions are also known as "linear fractional transformations" because they consist of a fraction or quotient of two linear functions. One nice feature of the linear fractional transformations (which we will abbreviate as "linfrac maps" or just "linfracs" in the following) is that they form a group, implying that the inverses are also in the set and compositions of such functions yield another element from the set. One might hope that with the 4 tweakable parameters, one could satisfy 4 constraints to let the values and derivatives match some prescribed value at the ends of the intervals. However, unfortunately, that's not so simple. When trying to solve the resulting system of equations, it turns out that it can only be solved, if the two slopes at the ends of the interval are reciprocals of one another so we can't prescribe them independently. I think, it is because the linfrac has actually only 3 degrees of freedom rather than 4 because scaling all coeffs by the same number gives the same transformation. Maybe that's why fixing the endpoints and one derivative already locks everything into place. To allow ourselves more control, we will use two linfracs per segment that join together at an internal node somewhere within the segment. At this internal node, the two sub-segments will also join smoothly to first order such that the overall smoothness of the interpolant is unchanged.

...

[RobinSchmidt]

The construction of the interpolant for a segment works as follows. We will assume that we want to find a function f(x) that maps the unit interval monotonically and invertibly to itself. That means the function should produce f(0) = 0 and f(1) = 1. Additionally, it should produce f'(0) = d0 and f'(1) = d1 for some pair of prescribed slope values at the interval boundaries. We use d0, d1 for "derivative" rather than s0, s1 for "slope" because we will use s1 later for something else. These slope values will ensure that the overall interpolant will have matching slopes at the segment boundaries. Where we get these d0, d1 values from doesn't matter here. It may make sense to produce them by numerical differentiation of the actual data, but that's a different topic. Here, we just assume them to be given.

In addition to the regular linfrac, we will also make use of a symmetrized variant that consists of two appropriately scaled and shifted versions of the orginal map, one for the domain 0..0.5 and another for the domain 0.5..1. They join smoothly at 0.5,0.5 and implement an inflection point there. The overall shape in 0..1 will be that of a sigmoid or a saddle - a sigmoid when d0 > 1 and a saddle when d0 < 1. The idea is now to combine a regular concave or convex linfrac with such a sigmoid/saddle and then with another convex/concave one. So all in all we use 3 linfracs applied in sequence to obtain a nesting of 3 maps:

concave/convex -> sigmoid/saddle -> concave/convex

These 3 linfracs in succession will give use (more than) enough freedom to meet our requirements for the derivatives at 0 and 1 at the expense of having to introduce a switch. Because at the end of the day, all 3 will combine into one single linfrac due to the composition rule - but it will have to be a different one for the first and last section of the interval 0..1. It's the fact that the middle one is the symmetrized variant which gives us this additional amount of control. The symmetrized variant lies not in our group of linfracs so it gives us indeed something new - namely, the ability to introduce inflection points. The end result of this construction will be a piecewise linfrac made from two pieces. In a way, the symmetrized linfrac serves as a prototype for the more general piecewise linfracs.

[RobinSchmidt]

OK - so we start from the assumption that we first use a regular linfrac in sequence with a symmetrized one and another regular one. A symmetrized linfrac will have the same derivative as a regular one at the origin. The regular ones will have a reciprocated derivative at 1,1
while the symmetrized one has the same derivative at 1,1 (after all, it's symmetric around 0.5,0.5). So all in all, at the origin, the overall slope will be given by the product of the slopes of the 3 individual linfracs, which we will denote by s1,s2,s3. At 1,1 the overall
slope will be given by s2/(s1*s3). The goal is now to produce the 3 slope parameters for our 3 linfracs from the 2 slope requirements d0, d1 that are given. So we have to solve the following system of equations

  d0 = s1*s2*s3
  d1 = s2/(s1*s3)

Let's define s13 = s1*s3 to get a system in 2 variables:

  d0 = s2*s13
  d1 = s2/s13

If we multiply both equations, we get

d0*d1 = s2^2

so we should use

s2 = sqrt(d0*d1)

Now, we can use either of the two equations to compute s13 as:

s13 = d0/s2 = s2/d1

What's left is to distribute the combined slope s13 to s1 and s3 (remember that s13 = s1*s3). The most natural way to do this is to just set s1 = s3 = sqrt(s13) but we could also introduce a shape parameter in 0..1 and set s1 = s13^shape, s3 = s13/s1. For shape = 0.5, this reduces to the sqrt formula. I'm not sure, if such a shape parameter is useful, though. The shapes obtained from the sqrt formula look most symmetric and seem to make most sense. I think, for later inversion, the shape needs either to be 0.5 or we need to use 1 - shape for the inverse interpolation. I've not yet figured out the details of that. [....Update: Yeah - that seems to be indeed the case. In my implementation, I have now shifted the user parameter for the shape such that now, the neutral value is at zero. One can actually go even beyond the range -0.5...+0.5 - even high values such as -8 or +8 still produce acceptable results - just remember to negate it for the inverse interpolation....or just use zero which gives the nicest shape anyway]

Now that we have our 3 slopes s1,s2,s3, we can combine the three linfracs into one for each section of the unit interval. Because the second, middle, symmetrized linfrac splits at 0.5, we need to figure out where the first map produces 0.5. This is easily done by evaluating
an inverse linfrac, i.e. one with slope 1/s1, at 0.5. This gives us our split point xs. The first combined map will be used for x = 0..xs and the second combined map will be used for x = xs..1. Now we need to produce the coefficients for the two maps. The first map will also
be of the restricted kind with b = 0 and d = 1, but for the second, we'll need the fully flexible variant with all 4 coeffs a,b,c,d. To figure out the coeffs of the maps, we'll just have to apply them in succession algebraically to a variable x and then read off the coeffs
of the result. This is best done with a computer algebra system. The formulas for the coeffs for the combined maps were found with the following Sage code. We have two versions because we need to switch between them:

1st part:

 var("s1 s2 s3")
 y1 = s1*x / ((s1-1)*x + 1)     # 1st map
 y2 = 2*y1                      # scale 
 y3 = s2*y2 / ((s2-1)*y2 + 1)   # 2nd map 
 y4 = y3/2                      # scale
 y5 = s3*y4 / ((s3-1)*y4 + 1)   # 3rd map
 num = numerator(y5)
 den = denominator(y5)
 num.expand().collect(x), den.expand().collect(x)

2nd part:

 var("s1 s2 s3")
 y1 = s1*x / ((s1-1)*x + 1)              # 1st map
 y2 = 2*y1-1                             # scale, shift 
 y3 = ((1/s2)*y2) / (((1/s2)-1)*y2 + 1)  # 2nd map, parentheses around ((1/s2)*y2) important!  
 y4 = (y3+1)/2                           # shift, scale
 y5 = s3*y4 / ((s3-1)*y4 + 1)            # 3rd map
 num = numerator(y5)
 den = denominator(y5)
 num.expand().collect(x), den.expand().collect(x)

The results of this are implemented in the functions calcComposedCoeffsLeft() , calcComposedCoeffsRight(). For more details, just look at the code itself and its comments.

[RobinSchmidt]

The plots in the original post were created by the function monotonicInterpolation() in MathExperiments.cpp which is part of the TestRosicAndRapt folder/project. Also of interest might be the experiment implemented in linearFractionalInterpolation() in the same file. It produces this beautiful looking plot:

It shows the different shapes for the normalized map [0..1] -> [0..1] for a desired slope of 1 at the origin x,y = 0,0 and slopes from 1/128, to 128 at x,y = 1,1 (exponentially increasing by a factor of 2). I think, it looks a bit like an onion or some sort of christmas tree decoration. Quite pretty...I wonder, if it could be used for graphics.