# Underdetermined deconvolution of windowed output

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 = h'$. 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?

• I was confusing the terms 'ill posed' and 'ill-conditioned'. – egg Oct 17 '17 at 10:55

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.

• I agree that if we know a value of the input $x_0 = 1$ then the problem is well-conditioned i.e. determined. However what approach is to be adopted if we are not willing to use the adhoc method of guessing a value? What is the approach adopted by deblurring software? Or is it the case that the deblurring does not face the problem of under-determination? – egg Oct 17 '17 at 10:38
• One option would be to find the solution with the least squared Euclidean norm. The minimizer is $$x_0 =\frac{12}{5}$$ – Rodrigo de Azevedo Oct 17 '17 at 10:52
• This seems reasonable and relates to regularised least squares. Do you know how this approach can be utilised with Fourier deconvolution rather than solving a linear algebra problem? – egg Oct 17 '17 at 11:05
• Just take more measurements of the output. Then use least-squares. Problem solved! – Rodrigo de Azevedo Oct 17 '17 at 11:28
• In a sense, the problem is that the filter you used has length $2$. If you had used a longer filter, you would have obtained a longer output. You could then discard many samples of this longer output and the problem would still be overdetermined. One must have at least as many output samples as input samples. – Rodrigo de Azevedo Oct 19 '17 at 8:29