Undo finite difference with arbitrary timesteps

Question

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[0] is known) by a cumulative sum, i.e., by defining \begin{equation} z[0] = x[0],\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[0]$ is known), using \begin{equation} z[0] = x[0],\qquad z[n] = z[n-1] + y[k n] \equiv x[kn]. \end{equation} If I further assume that all samples between $x[0]$ and $x[k]$ are known, I could also define \begin{equation} z^m[0] = 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[0]\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[0]\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]$.

Answer 1

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.