Talk:Deconvolution/2D+: Difference between revisions
Content added Content deleted
(→Help) |
(→Help) |
||
Line 9: | Line 9: | ||
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. --[[User:Paddy3118|Paddy3118]] 07:51, 23 February 2010 (UTC) |
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. --[[User:Paddy3118|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 <code>band</code> function takes a pair of lists <math>(g,f)</math> representing the |
|||
spaces you want to deconvolve. The length of <math>g</math> is <math>|g|</math> and the length |
|||
of <math>f</math> is <math>|f|</math>, and <math>|g| \geq |f|</math>. The <code>band</code> function |
|||
returns a matrix with <math>|g|</math> rows and <math>|h|</math> columns, where the length of the |
|||
answer, <math>|h|</math>, is given by |
|||
<math>|g| - |f| + 1</math>. Assuming all indices are numbered from 0, the entry in the |
|||
<math>i</math>-th row and the <math>j</math>-th column of this matrix is <math>f_{i+j}</math> if |
|||
<math>i \geq j</math> and |
|||
<math>i+j < |f|</math>, 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 <math>g</math> 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 <math>|h|/2</math> from the beginning |
|||
and last <math>|h|/2</math> from the end (or one extra from somewhere if <math>|h|</math> 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 <math>f</math> and <math>g</math> is itself a |
|||
vector rather than a scalar. Proceed using the same algorithm as in |
|||
the <code>band</code> function above to construct a matrix <math>A</math> of vectors following |
|||
the same pattern, with which each <math>i,j</math>-th element of <math>A</math> being either a |
|||
vector from <math>f</math>, 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 [[http://www.netlib.org/lapack Lapack]] library, |
|||
which is callable from many languages. |
|||
Next, pair up each row of the matrix-of-vectors <math>A</math> with the corresponding member of |
|||
<math>g</math>. Since <math>A</math> is a matrix of vectors, each row of it can be considered a matrix |
|||
of scalars on its own. For each i ranging from 0 to <math>|g|-1</math>, the pair <math>(g_i,A_i)</math> |
|||
of the <math>i</math>-th member of <math>g</math> and the <math>i</math>-th row of <math>A</math> will |
|||
consist of a vector <math>g_i</math> and a matrix <math>A_{i}</math>. Pair up a copy of <math>g_i</math> with each row of <math>A_{i}</math> and apply the 1 dimensional <code>band</code> function to each member |
|||
of the list of all such pairs. This step will yield a list of matrices (of |
|||
scalars) each with <math>|g_i|</math> rows. Flatten this list of matrices into a |
|||
single matrix with <math>|g_i|</math> rows by concatenating them row-wise (i.e., |
|||
horizontally). Having done so for all <math>(g_i,A_i)</math> pairs, flatten the |
|||
resulting list of <math>|g|</math> matrices into a one large matrix having <math>|g|*|g_0|</math> 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 <math>g</math>. |
|||
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 <math>|g_0| - |f_0| + 1</math>. (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, <math>f</math> and <math>g</math> will be lists of matrices. Begin as |
|||
above, but in this case populating the zero entries of <math>A</math> with |
|||
conforming zero matrices rather than vectors or scalars. When you get |
|||
to the point of operating on each <math>(g_i,A_i)</math> 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 <math>g_i</math> with each row of <math>A_{i}</math>, 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 <math>i</math>, |
|||
flatten the results vertically as explained above, and feed resulting |
|||
data to the solver. (The top level <math>g</math> 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 <math>|g_{00}| - |f_{00}| + 1</math>, and then |
|||
unflatten the intermediate result further into sublists of length <math>|g_0| - |f_0| + 1</math>. |
|||
=== 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. |