How to resolve the algorithm Deconvolution/1D step by step in the Raku programming language
How to resolve the algorithm Deconvolution/1D step by step in the Raku programming language
Table of Contents
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:
Step by Step solution about How to resolve the algorithm Deconvolution/1D step by step in the Raku programming language
Source code in the raku programming language
sub deconvolve (@g, @f) {
my \h = 1 + @g - @f;
my @m;
@m[^@g;^h] »+=» 0;
@m[^@g; h] »=« @g;
for ^h -> \j { for @f.kv -> \k, \v { @m[j+k;j] = v } }
(rref @m)[^h;h]
}
sub convolve (@f, @h) {
my @g = 0 xx + @f + @h - 1;
@g[^@f X+ ^@h] »+=« (@f X× @h);
@g
}
# Reduced Row Echelon Form simultaneous equation solver
# Can handle over-specified systems of equations (N unknowns in N + M equations)
sub rref (@m) {
@m = trim-system @m;
my ($lead, $rows, $cols) = 0, @m, @m[0];
for ^$rows -> $r {
return @m unless $lead < $cols;
my $i = $r;
until @m[$i;$lead] {
next unless ++$i == $rows;
$i = $r;
return @m if ++$lead == $cols;
}
@m[$i, $r] = @m[$r, $i] if $r != $i;
@m[$r] »/=» $ = @m[$r;$lead];
for ^$rows -> $n {
next if $n == $r;
@m[$n] »-=» @m[$r] »×» (@m[$n;$lead] // 0);
}
++$lead;
}
@m
}
# Reduce to N equations in N unknowns; a no-op unless rows > cols
sub trim-system (@m) {
return @m unless @m ≥ @m[0];
my (\vars, @t) = @m[0] - 1;
for ^vars -> \lead {
for ^@m -> \row {
@t.append: @m.splice(row, 1) and last if @m[row;lead];
}
}
while @t < vars and @m { @t.push: shift @m }
@t
}
my @h = (-8,-9,-3,-1,-6,7);
my @f = (-3,-6,-1,8,-6,3,-1,-9,-9,3,-2,5,2,-2,-7,-1);
my @g = (24,75,71,-34,3,22,-45,23,245,25,52,25,-67,-96,96,31,55,36,29,-43,-7);
.say for ~@g, ~convolve(@f, @h),'';
.say for ~@h, ~deconvolve(@g, @f),'';
.say for ~@f, ~deconvolve(@g, @h),'';
You may also check:How to resolve the algorithm Simple database step by step in the C# programming language
You may also check:How to resolve the algorithm Sorting algorithms/Radix sort step by step in the NetRexx programming language
You may also check:How to resolve the algorithm Determine if two triangles overlap step by step in the Phix programming language
You may also check:How to resolve the algorithm Loops/Break step by step in the Lingo programming language
You may also check:How to resolve the algorithm Cartesian product of two or more lists step by step in the 11l programming language