Deconvolution/1D
You are encouraged to solve this task according to the task description, using any language you may know.
The convolution of two functions and of an integer variable is defined as the function satisfying
for all integers . Assume can be non-zero only for ≤ < , where is the "length" of , and similarly for and , so that the functions can be modeled as finite sequences by identifying with , etc..
Then for example, values of and would determine the following value of by definition.
For this task, implement a function (or method, procedure, subroutine,
etc.) deconv
to perform deconvolution by constructing and solving such a
system of equations for given and
.
- The function should work for of arbitrary length (i.e., not hard coded or constant) and of any length up to that of . Note that will be given by .
- There may be more equations than unknowns. If convenient, use a function from a [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
deconv
anddeconv
and display the results in a human readable form.
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]
Ursala
The user defined function band
constructs the required
matrix as a list of lists given the pair of sequences to be
deconvolved, and the lapack..dgelsd
function solves the system. Some other library functions used are zipt
(zipping two unequal length
lists by truncating the longer one) zipp0
(zipping unequal length lists by padding the
shorter with zeros) and pad0
(making a list of lists all
the same length by appending zeros to the short ones).
<lang Ursala>#import std
- import nat
- import flo
band = pad0+ ~&rSS+ zipt^*D(~&r,^lrrSPT/~<K33tx zipt^/~&r ~&lSNyCK33+ zipp0)^/~&rx ~&B->NlNSPC ~&bt
deconv = lapack..dgelsd^\~&l ~&||0.!**+ band </lang> test program: <lang Ursala>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.>
- cast %eLm
test =
<
'h': deconv(g,f), 'f': deconv(g,h)>
</lang> output:
< 'h': < -8.000000e+00, -9.000000e+00, -3.000000e+00, -1.000000e+00, -6.000000e+00, 7.000000e+00>, 'f': < -3.000000e+00, -6.000000e+00, -1.000000e+00, 8.000000e+00, -6.000000e+00, 3.000000e+00, -1.000000e+00, -9.000000e+00, -9.000000e+00, 3.000000e+00, -2.000000e+00, 5.000000e+00, 2.000000e+00, -2.000000e+00, -7.000000e+00, -1.000000e+00>>