Underdetermined deconvolution of windowed output

Question

Consider a discrete 'blurred' output $h[t]$ given by the convolution of filter $f[t]$ and signal $g[t]$. This question considers recovering $g[t]$ from a window (subset) of $h[t]$. This causes the problem to be under-determined.

$$h[t] = (f * g)[t]$$

Original signal $g[t]$:

$$g[t] = [1,5,3,5,7,7]$$

Moving average filter $f$ of window size 2:

$$f[t] = [0.5,0.5,0,0,0,0,0]$$

The full 'blurred' output $h$ is given by:

$$h[t] = [0.5,3,4,4,6,7,3.5]$$

Given $h$ the problem of recovering $g$ is well-posed and can be recovered simply using Fourier transforms:

$$g[t] = \mathcal{F}^{-1}\left\{\frac{\mathcal{F}\left\{h[t]\right\}}{\mathcal{F}\left\{f[t]\right\}}\right\}$$

However in practice the recovery needs to be made from a windowed output $h'[t]$:

$$h[t]' = [3,4,4,6,7]$$

The problem of recovering $g[t]$ from $h'[t]$ is ill-conditioned since there are an infinite number of solutions. One approach I have seen suggested is to take $g[1] = h'[1]$. In this case the recovered profile $g'[t]$ is given by:

$$g'[t] = [3,3,5,3,9,5]$$

My understanding is that most approaches are based on regularisation however most sources seem to focus on ill-conditioning resulting from additive noise rather than ill-conditioning resulting from a windowed output. What are the approaches typically used for this problems? Can you apply it to this toy example?

Answer 1

Using more conventional notation, let $x_k$ and $y_k$ denote the $k$-th input and $k$-th output, respectively.

$$\begin{array}{rl} y_1 &= 3 = \frac 12 x_1 + \frac 12 x_0\\ y_2 &= 4 = \frac 12 x_2 + \frac 12 x_1\\ y_3 &= 4 = \frac 12 x_3 + \frac 12 x_2\\ y_4 &= 6 = \frac 12 x_4 + \frac 12 x_3\\ y_5 &= 7 = \frac 12 x_5 + \frac 12 x_4\end{array}$$

We have an underdetermined system of $5$ linear equations in $6$ unknowns. Let $x_0$ be a parameter.

$$\begin{bmatrix} \frac{1}{2} & 0 & 0 & 0 & 0\\ \frac{1}{2} & \frac{1}{2} & 0 & 0 & 0\\ 0 & \frac{1}{2} & \frac{1}{2} & 0 & 0\\ 0 & 0 & \frac{1}{2} & \frac{1}{2} & 0\\ 0 & 0 & 0 & \frac{1}{2} & \frac{1}{2}\end{bmatrix} \begin{bmatrix} x_1\\ x_2\\ x_3\\ x_4\\ x_5\end{bmatrix} = \begin{bmatrix} 3\\ 4\\ 4\\ 6\\ 7\end{bmatrix} - \frac 12 x_0 \begin{bmatrix} 1\\ 0\\ 0\\ 0\\ 0\end{bmatrix}$$

Using SymPy, we can solve the linear system

>>> from sympy import *
>>> from fractions import Fraction
>>> A = Fraction(1,2) * Matrix( [[1,0,0,0,0],
                                 [1,1,0,0,0],
                                 [0,1,1,0,0],
                                 [0,0,1,1,0],
                                 [0,0,0,1,1]] )
>>> y = Matrix([3,4,4,6,7])
>>> x0 = Symbol('x0')
>>> A**-1 * (y - Fraction(1,2)*x0*Matrix([1,0,0,0,0]))
Matrix([
[-x0 + 6],
[ x0 + 2],
[-x0 + 6],
[ x0 + 6],
[-x0 + 8]])

Thus, the solution set is a line parametrized as follows

$$\mathrm x \in \left\{ \begin{bmatrix} 6\\ 2\\ 6\\ 6\\ 8\end{bmatrix} + x_0 \begin{bmatrix} -1\\ \,\,\,\, 1\\ -1\\ \,\,\,\, 1\\ -1\end{bmatrix} : x_0 \in \mathbb R \right\}$$

Note that if we choose $x_0 = 1$ then we recover the original input vector. You chose $x_0 = 3$ instead.