Talk:Deconvolution/2D+
I got interested in higher dimensional deconvolution when contacted by someone about using it as a way of looking for trading indicators in financial time series. I set this task as an example of something that I'm speculating can be done well with functional and array processing languages, but only with difficulty otherwise, which I hope someone will weigh in to confirm or refute. In case anyone wants to know, consistent [test data] were generated partly by this higher dimensional convolution function,
<lang Ursala>conv = +^|(~&x+,*DrlDSNiCK9xxSNiCK9K7iFS+ *)=>times+ **+ *K7|\x+ iota; * ! plus:-0</lang>
invoked as (conv d)(h,f) with dimension d > 0 and conforming h and f. (This function essentially subsumes the Image convolution task as a special case with d = 2 and |h| = 3.) I suggest a development methodology based on warming up with Deconvolution/1D, then hand coding the solutions for the next few dimensions, and then looking for the pattern.
--Sluggo 03:24, 23 February 2010 (UTC)
Help
How do you help someone who knows how to program, but not how to de/convolve? I would like to attempt a solution but, not knowing Ursala, the example code given is of no help, and the maths only helps those that know rather than being a means to communicate to those outside the field. In Averages/Pythagorean means I was careful to add textual descriptions of the maths to help those people who know how to program, but whose eyes might start to glaze over when confronted with the equations. In fact, the second part of the task: "Show that the ..." was initially below the block of equations, and several implementers missed it completely in their haste to gloss over the equations.
Your task description is even more reliant on equations, and might be helped by much more non-math description - such as a scripting-like pseudo-code. --Paddy3118 07:51, 23 February 2010 (UTC)
Informal description
It can't hurt to try. Here is an informal description of an algorithm for it, with preference given to clarity over brevity. I'll record it here rather than in the task specification, because this isn't the only way to solve it or the best.
one dimension
First, the band function takes a pair of lists Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (g,f)}
representing the
spaces you want to deconvolve. The length of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle g}
is Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle |g|}
and the length
of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f}
is Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle |f|}
, and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle |g| \geq |f|}
. The band function
returns a matrix with Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle |g|}
rows and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle |h|}
columns, where the length of the
answer, Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle |h|}
, is given by
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle |g| - |f| + 1}
. Assuming all indices are numbered from 0, the entry in the
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle i}
-th row and the Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle j}
-th column of this matrix is Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f_{i+j}}
if
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle i \geq j}
and
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle i+j < |f|}
, but 0 otherwise. How you write the code to build it is up
to you. It doesn't have to be done with list combinators if the
language is better at handling arrays, but when it's done, the matrix
should look like the coefficient matrix for the system of equations
shown in the Deconvolution/1D task specification.
For the one dimensional case, the rest is easy. Plug this matrix and
the vector Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle g}
into a linear equation solver if the language has one, or
the function from the Reduced row echelon form task otherwise, and
you're done. The only minor complication is that you have to delete
some of the equations if the solver can't cope with having more
equations than unknowns. (In practice, it's better for noise reduction
if it can.) You can delete all but the first Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle |h|/2}
from the beginning
and last Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle |h|/2}
from the end (or one extra from somewhere if Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle |h|}
is an
odd number). If the solver precludes over determined systems
and the language also doesn't let you delete rows from matrices, you might
have to write the code in the band function to build it that way in
the first place.
two dimensions
For the two dimensional case, each member of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f}
and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle g}
is itself a
vector rather than a scalar. Proceed using the same algorithm as in
the band function above to construct a matrix Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A}
of vectors following
the same pattern, with which each Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle i,j}
-th element of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A}
being either a
vector from Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f}
, or a zero vector of conforming length.
I'm not saying it can't be done, but I'm not sure how pruning the matrix generalizes to higher dimensions, so the rest of this description assumes the solver copes with over determined systems. Such a solver is readily available in the [Lapack] library, which is callable from many languages.
Next, pair up each row of the matrix-of-vectors Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A}
with the corresponding member of
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle g}
. Since Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A}
is a matrix of vectors, each row of it can be considered a matrix
of scalars on its own. For each Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle i}
ranging from 0 to Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle |g|-1}
, the pair Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (g_i,A_i)}
of the Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle i}
-th member of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle g}
and the Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle i}
-th row of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A}
will consist of a vector Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle g_i}
and a matrix Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A_{i}}
. Pair up a copy of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle g_i}
with each row of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A_{i}}
and apply the 1 dimensional band function to each member of the list of all such pairs. This step will yield a list of matrices (of scalars) each with Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle |g_i|}
rows. Flatten this list of matrices into a single matrix with Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle |g_i|}
rows by concatenating them row-wise (i.e., horizontally). Having done so for all Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (g_i,A_i)}
pairs, flatten the resulting list of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle |g|}
matrices into one single matrix having Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle |g|*|g_0|}
rows by concatenating them column-wise (i.e., vertically). This matrix should then be fed to the linear equation solver along with a flattened copy of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle g}
.
The result returned by the linear equation solver will be a list of scalars, which must be unflattened into a list of vectors in the two dimensional case. Do so using whatever algorithm you prefer, provided that the length of each vector in the result is Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle |g_0| - |f_0| + 1} . (If the length of the result returned by the linear equation solver is not a multiple of this number, you've done it wrong.)
three dimensions
For three dimensions, Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f} and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle g} will be lists of matrices. Begin as above, but in this case populating the zero entries of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A} with conforming zero matrices rather than vectors or scalars. When you get to the point of operating on each Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (g_i,A_i)} pair, it turns out not to be a vector and a matrix of scalars as in the two dimensional case, but a list of vectors and matrix of vectors. At this point, pair up a copy of with each row of , and treat each of the pairs as an instance of the two dimensional problem. Construct the input matrix to the linear equation solver corresponding to each of these subproblems as explained above, but don't solve it. Instead, flatten them into a single matrix by concatenating them horizontally. Repeat for each , flatten the results vertically as explained above, and feed resulting data to the solver. (The top level will have to be flattened twice for the solver for the three dimensional case.) Take the solution and unflatten it first into sublists of the innermost dimension , and then unflatten the intermediate result further into sublists of length .
general
A four dimensional problem instance is to three as three is to two, and finishes with three unflattenings. Higher dimensions are analogous. Whether the language has suitable abstraction mechanisms to express a general form for this algorithm is part of what the task is intended to establish.
-- Sluggo 02:08, 24 February 2010 (UTC)