Support not-equispaced points

[pavelkomarov]

Right now the whole repo's interface is method(x, dt, **params), but what if my samples don't have a consistent dt? It would be more flexible to allow users to give function values and a same-length set of locations those values come from. Not all methods work with not-equispaced points or become much more expensive (Fourier spectral and Savitsky-Golay, e.g.), so perhaps we leave those with dt, or we could raise errors.

[pavelkomarov]

We can accomplish this by making the dt parameter (possibly renamed but still in the second position) optionally a scalar or a list, with the scalar treated as dt and a list of same length as x treated as the sample points.

[pavelkomarov]

For Kalman Filters there is a neat trick to support this, detailed in the beginning of this paper https://ieeexplore.ieee.org/document/6887356. I plan to write it up as a short section in the Taxonomy paper, because it's pretty invaluable if steps between samples are irregular. I'm happy to implement it here, especially if/as I touch the Kalman module for #97, because I think it's pretty elegant.

But in general for each method, the strategy for extending to irregular dt varies, and extending them all will be a ton of lift. We may decide to only extend this support for a few methods and call it a day, leaving some dangling issues open for would-be contributors of the future.

[pavelkomarov]

Methods variable dt can maybe work for:

• Kalman via matrix exponentiation, which is more expensive than just having the same A matrix all the time but is pretty elegant and short to implement.
• Splines, which can be fit with irregular data, although a cursory search says this also may be more expensive. But that extra expense could be offloaded on to the scipy fit.
• Finite Difference. In principle, you can use stencils with irregular, non-integer locations. Try it with this online tool. But that means solving a stencil-width-sized inverse problem to determine coefficients at every single timestep. Kind of gross, and there is a danger of amplifying noise per the discovery from first_order only differs from second_order at the endpoints #104 that the endpoint FD formulas were no good. This is all clearly more expensive than using a fixed formula, but could be done and wouldn't be too too hard, just a touch complicated.
• Fourier-spectral, the FFT only works if points are equispaced, but you can of course fit basis functions with any spacing you like in $O(N^3)$ instead of $O(N log N)$. I do this for some of my functions in spectral-derivatives, but not for Fourier. We could offload the work on to my other package, so for the purposes of this one it might not be too bad.

Methods variable dt can't easily work for:

• TVR is doing a FD to relate variables to derivative values, but dynamically calculating a bunch of coefficients to form the CVXPY problem wouldn't be a fun time.
• Median smoothing with irregular number of points in a sliding window might work but is kind of an odd thing to do. Median is already a strange, not-very-good-at-smoothing method.
• Savgoldiff becomes no-longer-a-closed-form filter when points are irregularly spaced. Formulating the inverse problem you have to solve at each step could be annoying and would break our ability to rely on a nice scipy filter.

Unsure:

• Smoothed FD inherits the problem from FD.

The derivative package demonstrates taking a whole time vector instead of one dt, but for many of those methods the time vector is just equispaced, and a dt is just taken and used from the space between the first couple points.

[pavelkomarov]

I think I've figured out how you'd do full-on RTS with irregular time steps: You just have to find $C_\text{RTS}$ (a.k.a. $L$) with the appropriate $A$ from a matrix exponentiation integration situation, exactly as you do for taking the forward steps. Basically you could save off all the state evolution matrices as you go and use them in reverse. Not 100% sure that's right, but it feels like it's probably the approach.

[pavelkomarov]

I think I'm going to make irregular steps its own discussion section of the paper, with a few examples to highlight how it can work for Finite Difference, Kalman, and maybe Savitzky-Golay or Spline or Spectral, just to give a flavor and say it's possible if you get creative and are willing to incur some greater computational costs. It comes up pretty frequently, so it would be a service to our readers and help serve as a guide for future implementation related to this issue. It can also be an advertisement that our software handles this wrinkle.

[pavelkomarov]

I spent some more time thinking about this and made a table in the paper, including some stuff out of scope for this repo for completeness. I'm going to discuss FD, Splines, and Kalman in there, and I think that's about the extent of what we should ever do to support this case in this repo, since most methods turn out to not be very friendly to variable $\Delta t$, foundationally, because of the mathematical machinery they're built from.

[pavelkomarov]

The fact splines naturally handle irregular data points means that method should be super easy to extend, and we can try to support this issue with only UI tinkering, decoupled from heavier mathematical changes.

[pavelkomarov]

#148 extends splinediff 🎉. I'd like to also extend the Kalman module to do this, which is a lot more mathematically involved but can be done without asymptotically worse cost. And then perhaps we can close the issue, unless we'd also like to extend Iterated FD per my thinking in the paper, or sort out #146 and figure out how to make polydiff work with irregular steps.

The FD extension not only incurs extra computational cost but also requires the algorithm to be a little adaptive, since irregular stencils can result in large coefficients that amplify noise. The strategy would be to use wider stencils or lower orders to push coefficient values down. Not sure it's worth it, although it's neat it's possible. My guess is our enthusiasm and time budgets for that are nonexistent.