1
$\begingroup$

What I have is sums of smaller submatrices of size $M\times M$ ($M$ is much smaller than $N$, say $N/6$ or less). The sums of all possible submatrices at all positions are known. I am trying to rebuild the entire $N\times N$ matrix.

For example, if there is a $4\times 4$ matrix $X$ with the values

$\begin{array}{cccc} 1 & 2 & 3 & 4\\ 5 & 6 & 7 & 8\\ 9 & 1 & 2 & 3\\ 4 & 5 & 6 & 7\\ \end{array}$

And I have the sums of submatrices of size $2\times 2$ (for all possible positions - assuming that the matrix is surrounded by infinite number of zero values).

The first known submatrix sum would thus be $0+0+0+1=1$: $\hskip-0.3in \begin{array}{ccccc} \fbox{$\begin{matrix} 0 & 0 \\ 0 & 1\end{matrix}$}\!\!\!\! & {\atop 2} & {\atop 3} & {\atop 4}\\ \begin{matrix} \hphantom{0} & 5\end{matrix}\!\!\!\! & 6 & 7 & 8\\ \begin{matrix} \hphantom{0} & 9\end{matrix}\!\!\!\! & 1 & 2 & 3\\ \begin{matrix} \hphantom{0} & 4\end{matrix}\!\!\!\! & 5 & 6 & 7\\ \end{array}$

...and the second submatrix sum, $0+0+1+2=3$:

$\begin{array}{cccc} \fbox{$\begin{matrix} 0 & 0 \\ 1 & 2\end{matrix}$}\!\!\!\!\!\! & {\atop 3} & {\atop 4} \\ \begin{matrix} 5 & 6\end{matrix}\!\!\!\!\!\! & 7 & 8\\ \begin{matrix} 9 & 1\end{matrix}\!\!\!\!\!\! & 2 & 3\\ \begin{matrix} 4 & 5\end{matrix}\!\!\!\!\!\! & 6 & 7\\ \end{array}$

The third sum would be $5$, the fourth $7$, and so on for each row and column in $X$. There are $(N+1)\times(N+1)$ of these sums, and they can be written as the matrix $Y$ (containing all available submatrix sums):

$\begin{matrix} 1 & 3 & 5 & 7 & 4\\ 6 & 14& 18&22 & 12\\ 14 & 21 & 16&20 & 11\\ 13 & 19& 14& 18&10 \\ 4 & 9& 11&13 & 7 \end{matrix}$

The question is, how to rebuild / calculate the original $N\times N$ matrix $X$ from the $(N+1)\times(N+1)$ matrix $Y$, from the available submatrix sums? If it is not possible to calculate exactly, how well can it be approximated?

Any hints are appreciated!

2 Answers 2

4

Wait a minute, if your matrix is padded with infinite zeros, then this is really easy.

You have Y(i,j) = \sum_{\substack{i'=0\text{ to }M-1 \\ j'=0\text{ to }M-1}} X(i-i',j-j'), so X(i,j) = Y(i,j) - \sum_{\substack{i'=0\text{ to }M-1 \\ j'=0\text{ to }M-1 \\ (i,j) \neq (0,0)}} X(i-i',j-j'). That just says that for any $M\times M$ submatrix, you can find the value at the bottom right corner if you know all the other entries.

So start with the upper left corner: clearly, $X(1,1) = Y(1,1)$ because all the rest of the entries are zero as they are outside the $N\times N$ matrix. Now that you know $X(1,1)$, you can find $X(1,2) = Y(1,2) - X(1,1)$, and then $X(1,3) = Y(1,3) - \ldots$, and thus fill in the whole first row of $X$. Then you do the same thing, marching down the rest of the rows, and you're done.

  • 0
    Thanks Rahul! Thats very useful. Would you also know a solution (or an approximation) in case there are unknown values around the matrix X, instead of zeroes?2011-08-07
3

You have effectively applied a box blur filter. This is diagonal in Fourier space, so you can undo it by performing a Fourier transform, dividing by the filter's frequency response, and transforming back. For that to work, you need to choose a transform size such that none of the Fourier modes is annihilated by the filter (else you can't reconstruct them). This will be the case e.g. if the transform size is a sufficiently large prime. Since I don't know how much you already know about these things, I'll stop here; feel free to ask if any of that isn't clear.

  • 0
    A more concrete way of seeing the same thing: You can have a checkerboard of $1$s and $-1$s as input. The resulting output (assuming surrounding zeros) will be zero in the interior and on the margins and non-zero only at the corners. If the surrounding values are not zero, they could produce the same pattern on the boundary, so in that case you couldn't distinguish this input from an all-zero input.2011-08-08