Problem Statement

The convolution of two functions

F

{\displaystyle {\mathit {F}}}

and

H

{\displaystyle {\mathit {H}}}

of an integer variable is defined as the function

G

{\displaystyle {\mathit {G}}}

satisfying for all integers

n

{\displaystyle {\mathit {n}}}

. Assume

F ( n )

{\displaystyle F(n)}

can be non-zero only for

0

{\displaystyle 0}

≤

n

{\displaystyle {\mathit {n}}}

≤

|

F

|

{\displaystyle |{\mathit {F}}|}

, where

|

F

|

{\displaystyle |{\mathit {F}}|}

is the "length" of

F

{\displaystyle {\mathit {F}}}

, and similarly for

G

{\displaystyle {\mathit {G}}}

and

H

{\displaystyle {\mathit {H}}}

, so that the functions can be modeled as finite sequences by identifying

f

0

,

f

1

,

f

2

, …

{\displaystyle f_{0},f_{1},f_{2},\dots }

with

F ( 0 ) , F ( 1 ) , F ( 2 ) , …

{\displaystyle F(0),F(1),F(2),\dots }

, etc. Then for example, values of

|

F

|

= 6

{\displaystyle |{\mathit {F}}|=6}

and

|

H

|

= 5

{\displaystyle |{\mathit {H}}|=5}

would determine the following value of

g

{\displaystyle {\mathit {g}}}

by definition. We can write this in matrix form as: or For this task, implement a function (or method, procedure, subroutine, etc.) deconv to perform deconvolution (i.e., the inverse of convolution) by constructing and solving such a system of equations represented by the above matrix

A

{\displaystyle A}

for

h

{\displaystyle {\mathit {h}}}

given

f

{\displaystyle {\mathit {f}}}

and

g

{\displaystyle {\mathit {g}}}

.

h = [-8,-9,-3,-1,-6,7] f = [-3,-6,-1,8,-6,3,-1,-9,-9,3,-2,5,2,-2,-7,-1] g = [24,75,71,-34,3,22,-45,23,245,25,52,25,-67,-96,96,31,55,36,29,-43,-7]

Let's start with the solution:

var [const] GSL=Import("zklGSL");	// libGSL (GNU Scientific Library)
fcn dconv1D(f,g){
   fsz,hsz:=f.len(), g.len() - fsz +1;
   A:=GSL.Matrix(g.len(),hsz);
   foreach n,fn in ([0..].zip(f)){ foreach rc in (hsz){ A[rc+n,rc]=fn } }
   h:=A.AxEQb(g);
   h
}

f:=GSL.VectorFromData(-3,-6,-1,8,-6,3,-1,-9,-9,3,-2,5,2,-2,-7,-1);
g:=GSL.VectorFromData(24,75,71,-34,3,22,-45,23,245,25,52,25,-67,-96,96,31,55,36,29,-43,-7);
h:=dconv1D(f,g);
h.format().println();

f:=dconv1D(h,g);
f.format().println();

fcn deconv(g,f){
   flen, glen, delta:=f.len(), g.len(), glen - flen + 1;
   result:=List.createLong(delta); // allocate list with space for items
   foreach n in (delta){
      e:=g[n];
      lowerBound:=(if (n>=flen) n - flen + 1 else 0);
      foreach i in ([lowerBound .. n-1]){ e-=result[i]*f[n - i]; }
      result.append(e/f[0]);
    }
    result;
}

h:=T(-8,-9,-3,-1,-6,7);
f:=T(-3,-6,-1,8,-6,3,-1,-9,-9,3,-2,5,2,-2,-7,-1);
g:=T(24,75,71,-34,3,22,-45,23,245,25,52,25,-67,
                   -96,96,31,55,36,29,-43,-7);
println(deconv(g, f) == h, " ", deconv(g, f));
println(deconv(g, h) == f, " ", deconv(g, h));