Deconvolution/2D+
You are encouraged to solve this task according to the task description, using any language you may know.
This task is a straightforward generalization of Deconvolution/1D to higher dimensions. For example, the one dimensional case would be applicable to audio signals, whereas two dimensions would pertain to images. Define the discrete convolution in dimensions of two functions
taking -tuples of integers to real numbers as the function
also taking -tuples of integers to reals and satisfying
for all -tuples of integers . Assume and (and therefore ) are non-zero over only a finite domain bounded by the origin, hence possible to represent as finite multi-dimensional arrays or nested lists , , and .
For this task, implement a function (or method, procedure, subroutine, etc.) deconv
to perform deconvolution (i.e., the inverse of convolution) by solving for given and . (See Deconvolution/1D for details.)
- The function should work for of arbitrary length in each dimension (i.e., not hard coded or constant) and of any length up to that of in the corresponding dimension.
- The
deconv
function will need to be parameterized by the dimension unless the dimension can be inferred from the data structures representing and . - 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.
- Debug your solution using the following data. Be sure to verify both that the deconvolution of with is and that the deconvolution of with is . Display the results in a human readable form for only the three dimensional case only.
dimension 1:
h: [-8, 2, -9, -2, 9, -8, -2] f: [ 6, -9, -7, -5] g: [-48, 84, -16, 95, 125, -70, 7, 29, 54, 10]
dimension 2:
h: [ [-8, 1, -7, -2, -9, 4], [4, 5, -5, 2, 7, -1], [-6, -3, -3, -6, 9, 5]] f: [ [-5, 2, -2, -6, -7], [9, 7, -6, 5, -7], [1, -1, 9, 2, -7], [5, 9, -9, 2, -5], [-8, 5, -2, 8, 5]] g: [ [40, -21, 53, 42, 105, 1, 87, 60, 39, -28], [-92, -64, 19, -167, -71, -47, 128, -109, 40, -21], [58, 85, -93, 37, 101, -14, 5, 37, -76, -56], [-90, -135, 60, -125, 68, 53, 223, 4, -36, -48], [78, 16, 7, -199, 156, -162, 29, 28, -103, -10], [-62, -89, 69, -61, 66, 193, -61, 71, -8, -30], [48, -6, 21, -9, -150, -22, -56, 32, 85, 25]]
dimension 3:
h: [ [[-6, -8, -5, 9], [-7, 9, -6, -8], [2, -7, 9, 8]], [[7, 4, 4, -6], [9, 9, 4, -4], [-3, 7, -2, -3]]] f: [ [[-9, 5, -8], [3, 5, 1]], [[-1, -7, 2], [-5, -6, 6]], [[8, 5, 8],[-2, -6, -4]]] g: [ [ [54, 42, 53, -42, 85, -72], [45, -170, 94, -36, 48, 73], [-39, 65, -112, -16, -78, -72], [6, -11, -6, 62, 49, 8]], [ [-57, 49, -23, 52, -135, 66], [-23, 127, -58, -5, -118, 64], [87, -16, 121, 23, -41, -12], [-19, 29, 35, -148, -11, 45]], [ [-55, -147, -146, -31, 55, 60], [-88, -45, -28, 46, -26, -144], [-12, -107, -34, 150, 249, 66], [11, -15, -34, 27, -78, -50]], [ [56, 67, 108, 4, 2, -48], [58, 67, 89, 32, 32, -8], [-42, -31, -103, -30, -23, -8], [6, 4, -26, -10, 26, 12]]]
These test data and some for higher dimensions can be downloaded [here].
Ursala
This is done mostly with list operations that are either primitive or standard library functions in the language (e.g., zipp
, zipt
, and pad
). The equations are solved by
the dgelsd
function from the Lapack library.
The break
function breaks a long list into a sequence of sublists according to a given template, and the band
function is taken from the Deconvolution/1D solution.
<lang Ursala>#import std
- import nat
break = ~&r**+ zipt*+ ~&lh*~+ ~&lzyCPrX|\+ -*^|\~&tK33 :^/~& 0!*t
band = pad0+ ~&rSS+ zipt^*D(~&r,^lrrSPT/~<K33tx zipt^/~&r ~&lSNyCK33+ zipp0)^/~&rx ~&B->NlNSPC ~&bt
deconv = # takes the number of dimensions to a deconvolution function
~&?\math..div! iota; (~&al^?\~&ar @alh2faltPrXPRX break)++ ^^(
~&B->NlC~&bt*++ gang@t+ ~~*+ @h|\+ ~&!*, @t lapack..dgelsd++ ^^\(=>~&l ~&L+@r) ~&||0.!**++ -+ =>band ^(~&l,pad0*+ band);+ *=p+ +^\~&l ~&K7LS++ *D@r, (^|/~&)*t+ =><~&> @r ^C\~& ~&K7++ pad0*K7;+ *@h+-)
</lang> test program: <lang Ursala>h = <<<-6.,-8.,-5.,9.>,<-7.,9.,-6.,-8.>,<2.,-7.,9.,8.>>,<<7.,4.,4.,-6.>,<9.,9.,4.,-4.>,<-3.,7.,-2.,-3.>>> f = <<<-9.,5.,-8.>,<3.,5.,1.>>,<<-1.,-7.,2.>,<-5.,-6.,6.>>,<<8.,5.,8.>,<-2.,-6.,-4.>>>
g =
<
< <54.,42.,53.,-42.,85.,-72.>, <45.,-170.,94.,-36.,48.,73.>, <-39.,65.,-112.,-16.,-78.,-72.>, <6.,-11.,-6.,62.,49.,8.>>, < <-57.,49.,-23.,52.,-135.,66.>, <-23.,127.,-58.,-5.,-118.,64.>, <87.,-16.,121.,23.,-41.,-12.>, <-19.,29.,35.,-148.,-11.,45.>>, < <-55.,-147.,-146.,-31.,55.,60.>, <-88.,-45.,-28.,46.,-26.,-144.>, <-12.,-107.,-34.,150.,249.,66.>, <11.,-15.,-34.,27.,-78.,-50.>>, < <56.,67.,108.,4.,2.,-48.>, <58.,67.,89.,32.,32.,-8.>, <-42.,-31.,-103.,-30.,-23.,-8.>, <6.,4.,-26.,-10.,26.,12.>>>
- cast %eLLLm
test =
<
'h': deconv3(g,f), 'f': deconv3(g,h)>
</lang> output:
< 'h': < < < -6.000000e+00, -8.000000e+00, -5.000000e+00, 9.000000e+00>, < -7.000000e+00, 9.000000e+00, -6.000000e+00, -8.000000e+00>, < 2.000000e+00, -7.000000e+00, 9.000000e+00, 8.000000e+00>>, < < 7.000000e+00, 4.000000e+00, 4.000000e+00, -6.000000e+00>, < 9.000000e+00, 9.000000e+00, 4.000000e+00, -4.000000e+00>, < -3.000000e+00, 7.000000e+00, -2.000000e+00, -3.000000e+00>>>, 'f': < < <-9.000000e+00,5.000000e+00,-8.000000e+00>, <3.000000e+00,5.000000e+00,1.000000e+00>>, < <-1.000000e+00,-7.000000e+00,2.000000e+00>, <-5.000000e+00,-6.000000e+00,6.000000e+00>>, < <8.000000e+00,5.000000e+00,8.000000e+00>, <-2.000000e+00,-6.000000e+00,-4.000000e+00>>>>