# Deriving the Convolution Kernel of the Inverse of a Signal

Let $y$ be the inverse (in the sense of convolution) of $x$, i.e.

$$x \star y = \delta$$

Context: $x[n]$ is a discrete signal defined for $n = 0,\ldots, N$. We can assume $x[n] = 0$ if $n \not\in [0,\ldots, N]$.

How to compute the inverse of $x$ (for the convolution)?

\begin{align}(x\star y)[0]&=x[0] y[0] = 1\implies y[0] = \frac{1}{x[0]}\\ (x\star y)[1]&=x[1] y[0] + x[0] y[1] = 0\implies y[1] = -\frac{x[1]}{x[0]^2}\\ (x\star y)[2]&=x[2] y[0] + x[1] y[1] + x[0] y[2] = 0\implies y[2] = -\frac{x[2]}{x[0]^2} + \frac{x[1]^2}{x[0]^3} \end{align}

I tried to find $y[3]$ manually, but I don't see a general formula appearing...

(I would post this as a comment, but I don't have enough rep)

If I understand your question correctly, the operation you want to do is called Deconvolution. Considering the more general problem $x \star y = z$, we can find a solution according to wikipedia as $x = IFT(Z/Y) = IFT(FT(Z)/FT(Y))$, (where $FT$ is the Fourier Transform and $IFT=FT^{-1}$ the inverse FT).

Consider a signal $x[n]$ of a finite length $N$. We are interested in a signal $y[n]$ where $$y[n]\star x[n]=\delta[n]\tag{1}$$ Assume $x[n]$ is the impulse response of an FIR filter and the transfer function is $X(z)$. The inverse filter is an IIR filter whose transfer function is $\frac{1}{X(z)}$. The impulse response of the inverse filter is $$y[n]=\mathcal{Z}^{-1}\left\{\frac{1}{X(z)}\right\}$$

The other way to see it: Convolution becomes product in the $z$-domain, where $\mathcal{Z}\left\{\delta[n]\right\}=1$.

It should be noted that depending on the zeros of $X(z)$ we can have different regions of convergence (ROC) for $\frac{1}{X(z)}$, and consequently different $y[n]$. This means that solutions of $(1)$ may not be unique.

Since the length of the $y[n]$ is theoretically infinite, for implementation you should use a truncated signal which results in an approximated $\delta$. You can use long-division algorithm to find $y$ with desired length.

• to do this practically, the OP will likely set $$z=e^{j2\pi \tfrac{k}{N}}$$ and will have to worry a little about what to do in the occasion of $|X(z)|$ being too close to zero. – robert bristow-johnson Dec 29 '16 at 1:25
• @robertbristow-johnson this would be interesting as an answer! – Basj Jan 2 '17 at 19:58

Since Convolution is a Linear Operation the easiest way to derive the coefficients is using a Matrix Representation of the problem.

Take the kernel $$y$$ and build from it the Convolution Matrix.
Then write the vector representation of the Delta Funciton $$d$$ and solve:

$$Y x = d$$

In case the problem is solvable (Namely there is an inverse operator of $$Y$$) you'll get you answer.
Of course you can always use Least Squares Solution.

Full code for building Convolution Matrix was given in Estimating a Signal Given a Noisy Measurement of the Signal and Its Derivative (Denoising) and Deconvolution of Synthetic 1D Signals - How To?

• Could you show an example? – David Aug 19 '18 at 16:28