# Undo finite difference with arbitrary timesteps

I'm wondering if there is a way to undo a finite difference filter with arbitrary timesteps.

In the simplest case of a two-sample finite difference of a time-series $$x[n]$$, $$\begin{equation} y[n] = x[n] - x[n-1], \end{equation}$$ we can perfectly undo the operation (assuming x is known) by a cumulative sum, i.e., by defining $$\begin{equation} z = x,\qquad z[n] = z[n-1] + y[n] \equiv x[n]. \end{equation}$$ A first generalization of this would be a filter to undo a finite difference by multiple samples, i.e., recovering $$x[n]$$ from $$\begin{equation} y[n] = x[n] - x[n-k], \end{equation}$$ with $$k$$ as an arbitrary integer.

Does such a procedure exist? It seems trivial to reconstruct every k'th sample (again assuming $$x$$ is known), using $$\begin{equation} z = x,\qquad z[n] = z[n-1] + y[k n] \equiv x[kn]. \end{equation}$$ If I further assume that all samples between $$x$$ and $$x[k]$$ are known, I could also define $$\begin{equation} z^m = x[m],\qquad z^m[n] = z^m[n-1] + y[k n + m] \equiv x[kn + m], \end{equation}$$ which would allow us to stitch together the whole time series. But in my application, the samples $$x\dots x[k]$$ are not known. Is there a better way?

Or if there isn't (i.e., if one always requires to know the samples $$x\dots x[k]$$ for this to work), does anyone know a reference with a nice proof for that?

And extension to the question would be if there is an even more general solution to this problem, where we have an arbitrary timeshift implemented by interpolation. I.e., we have an input signal of the form $$\begin{equation} y[n] = x[n] - \sum_k c_k x[n-k], \end{equation}$$ with $$c_k$$ as known interpolation filter coefficients, and want to recover $$x[n]$$.

Does such a procedure exist?

Of course. All systems that you are describing are just FIR filters, i.e.

$$y[n] = \sum_{k=0}^{N-1} h[k] \cdot x[n-k]$$ and their Z-transform is

$$H(z) = \sum_{k=0}^{N-1} h[k] \cdot z^{-k}$$

The inverse becomes

$$G(z) = H^{-1}(z) = \frac{1}{\displaystyle\sum_{k=0}^{N-1} h[k] \cdot z^{-k}}$$

This is an "all pole" filter. The main issue here is stability. If your original FIR filter has zeros outside the unit circle, than the inverse will have poles outside the unit and hence it's unstable (or/and non-causal). There is a physical explanation for this: the FIR filter has "destroyed" information and it's not recoverable through an inverse filter.

Let's look at your first example. The impulse response is simply $$h_1 = [1 -1]$$ and the inverse is

$$G_1(z) = \frac{1}{1-z^{-1}}$$

That has a pole at $$z=1$$ so it's only marginally stable. The differentiators "destroys" any information at DC (0 Hz) and hence the inverse has infinite gain at DC.

Your other examples can be treated the same way. As long as the FIR has all zeros inside the unit circle (which means it's minimum phase), the inverse exists and is an all pole IIR filter that is also minimum phase.

• The metastability of $z / (z - 1)$ also means that the response to random white noise grows without bound. Specifically, any measurement noise, or quantization noise that isn't guaranteed by the system design to have specific spectral characteristics. Dec 7, 2021 at 18:34
• Thanks for the detailed answer. I have some reading to do to fully understand it, but I think it contains all the information I needed. It also pointed me to the right vocabulary to find this question, which also gives the explicit recursive formula to undo an arbitrary FIR filter (with the same warning about stability). Dec 7, 2021 at 19:17