How to rebuild a $N\times N$ matrix from the sums of all of its submatrices of size $M\times M$ ($M\ll N$)

Question

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!

Answer 1

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.

Answer 2

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.