RosettaCodeData/Task/Deconvolution-1D/00DESCRIPTION

The convolution of two functions <math>\mathit{F}</math> and <math>\mathit{H}</math> of
an integer variable is defined as the function <math>\mathit{G}</math>
satisfying

:<math> G(n) = \sum_{m=-\infty}^{\infty} F(m) H(n-m) </math>

for all integers <math>\mathit{n}</math>. Assume <math>F(n)</math> can be non-zero only for <math>0</math> &le; <math>\mathit{n}</math> &le; <math>|\mathit{F}|</math>, where <math>|\mathit{F}|</math> is the "length" of <math>\mathit{F}</math>, and similarly for <math>\mathit{G}</math> and <math>\mathit{H}</math>, so that the functions can be modeled as finite sequences by identifying <math>f_0, f_1, f_2, \dots</math> with <math>F(0), F(1), F(2), \dots</math>, etc.
Then for example, values of <math>|\mathit{F}| = 6</math> and <math>|\mathit{H}| = 5</math> would determine the following value of <math>\mathit{g}</math> by definition.

:<math>
\begin{array}{lllllllllll}
g_0 &= &f_0h_0\\
g_1 &= &f_1h_0 &+ &f_0h_1\\
g_2 &= &f_2h_0 &+ &f_1h_1 &+ &f_0h_2\\
g_3 &= &f_3h_0 &+ &f_2h_1 &+ &f_1h_2 &+ &f_0h_3\\
g_4 &= &f_4h_0 &+ &f_3h_1 &+ &f_2h_2 &+ &f_1h_3 &+ &f_0h_4\\
g_5 &= &f_5h_0 &+ &f_4h_1 &+ &f_3h_2 &+ &f_2h_3 &+ &f_1h_4\\
g_6 &= &       &  &f_5h_1 &+ &f_4h_2 &+ &f_3h_3 &+ &f_2h_4\\
g_7 &= &       &  &       &  &f_5h_2 &+ &f_4h_3 &+ &f_3h_4\\
g_8 &= &       &  &       &  &       &  &f_5h_3 &+ &f_4h_4\\
g_9 &= &       &  &       &  &       &  &       &  &f_5h_4
\end{array}
</math>

We can write this in matrix form as:

:<math>
\left(
\begin{array}{l}
g_0 \\
g_1 \\
g_2 \\
g_3 \\
g_4 \\
g_5 \\
g_6 \\
g_7 \\
g_8 \\
g_9 \\
\end{array}
\right) = \left(
\begin{array}{lllll}
f_0\\
f_1 & f_0\\
f_2 & f_1 & f_0\\
f_3 & f_2 & f_1 & f_0\\
f_4 & f_3 & f_2 & f_1 & f_0\\
f_5 & f_4 & f_3 & f_2 & f_1\\
    & f_5 & f_4 & f_3 & f_2\\
    &     & f_5 & f_4 & f_3\\
    &     &     & f_5 & f_4\\
    &     &     &     & f_5
\end{array}
\right) \; \left(
\begin{array}{l}
h_0 \\
h_1 \\
h_2 \\
h_3 \\
h_4 \\
\end{array} \right)
</math>

or

:<math>
g = A \; h
</math>

For this task, implement a function (or method, procedure, subroutine, etc.) <code>deconv</code> to perform ''deconvolution'' (i.e., the ''inverse'' of convolution) by constructing and solving such a system of equations represented by the above matrix <math>A</math> for <math>\mathit{h}</math> given <math>\mathit{f}</math> and <math>\mathit{g}</math>.

* The function should work for <math>\mathit{G}</math> of arbitrary length (i.e., not hard coded or constant) and <math>\mathit{F}</math> of any length up to that of <math>\mathit{G}</math>. Note that <math>|\mathit{H}|</math> will be given by <math>|\mathit{G}| - |\mathit{F}| + 1</math>.
* There may be more equations than unknowns. If convenient, use a function from a [http://www.netlib.org/lapack/lug/node27.html library] that finds the best fitting solution to an overdetermined system of linear equations (as in the [[Multiple regression]] task).  Otherwise, prune the set of equations as needed and solve as in the [[Reduced row echelon form]] task.
* Test your solution on the following data. Be sure to verify both that <code>deconv</code><math>(g,f) = h</math> and <code>deconv</code><math>(g,h) = f</math> and display the results in a human readable form.
<code>
h = [-8,-9,-3,-1,-6,7]<br>
f = [-3,-6,-1,8,-6,3,-1,-9,-9,3,-2,5,2,-2,-7,-1]<br>
g = [24,75,71,-34,3,22,-45,23,245,25,52,25,-67,-96,96,31,55,36,29,-43,-7]
</code>