We have an unknown $m\times n$ matrix $X=(x\_{ij})\_{i=1,j=1}^{m,n}$. Assume we are given measurements of the differences 


$$x\_{i,j+1}-x\_{i,j}$$ 


and 


$$x\_{i+1,j}-x\_{i,j}$$ for all $(i,j)\in \{1,\dots,m\}\times\{1,\dots,n\}$ where $x\_{i,n+1}=x\_{i,1}$ and $x\_{m+1,j}=x\_{1,j}$. Assume the measurements are independent and have all the same standard deviation. Now we would like to reconstruct a difference $x\_{i,j}-x\_{1,1}$. For a given $m,n$ one can consider the **least squares** problem and find a linear combination of measurements such that the random variable has the smallest standard deviation. My question now is if there is an explicit expression for this linear combination and the standard deviation of the reconstruction. If not is the asymptotics $m,n\rightarrow \infty$ known? 



Reconstruct matrix given all differences of neighbors
Given


* $\mathrm R \in \mathbb R^{m \times n}$, whose $m$ rows are the differences of neighboring rows of $\mathrm X \in \mathbb R^{m \times n}$
* $\mathrm C \in \mathbb R^{m \times n}$, whose $n$ columns are the differences of neighboring columns of $\mathrm X \in \mathbb R^{m \times n}$


we would like to determine the *unknown* matrix $\mathrm X \in \mathbb R^{m \times n}$. Do note that we consider the 1st and $m$-th rows neighbors, and that we also consider the 1st and $n$-th columns neighbors.




---


### The subtraction matrix


We define the $d \times d$ [circulant](https://en.wikipedia.org/wiki/Circulant_matrix) matrix


$$\mathrm S\_d := \begin{bmatrix} -1 & 1 & 0 & \dots & 0 & 0\\ 0 & -1 & 1 & \dots & 0 & 0\\ 0 & 0 & -1 & \dots & 0 & 0\\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots\\ 0 & 0 & 0 & \dots & -1 & 1\\ 1 & 0 & 0 & \dots & 0 & -1\end{bmatrix}$$


Let


$$w\_d := \exp \left( i \frac{2 \pi}{d} \right)$$


From results on circulant matrices [0], we know that the [spectrum](https://en.wikipedia.org/wiki/Spectrum_of_a_matrix) of $\mathrm S\_d$ is


$$\{ w\_d^0 - 1, w\_d^1 - 1, \dots, w\_d^{d-1} - 1 \} = \{ 0, w\_d - 1, \dots, w\_d^{d-1} - 1 \}$$


In other words, the $d$ eigenvalues of $\mathrm S\_d$ are on the unit circle centered at $-1 + i 0$. Hence, we can conclude that $\mbox{rank} (\mathrm S\_d) = d-1$. Since $\mathrm S\_d 1\_d = 0\_d$, the (right) null space of $\mathrm S\_d$ is $\{ \gamma 1\_d \mid \gamma \in \mathbb R \}$.




---


### A linear system


We have two linear matrix equations in $\mathrm X$


$$\mathrm S\_m \mathrm X = \mathrm R \qquad\qquad\qquad \mathrm X \mathrm S\_n^{\top} = \mathrm C$$


which is a linear system of $2 m n$ scalar equations in $m n$ unknowns. Note that


* if $\bar{\mathrm X}$ is a *particular* solution of $\mathrm S\_m \mathrm X = \mathrm R$, then so is $\bar{\mathrm X} + \gamma \, 1\_m \mathrm v^{\top}$, where $\gamma \in \mathbb R$ and $\mathrm v \in \mathbb R^n$, as


$$\mathrm S\_m \left( \bar{\mathrm X} + \gamma \, 1\_m \mathrm v^{\top} \right) = \underbrace{\mathrm S\_m \bar{\mathrm X}}\_{= \mathrm R} + \gamma \, \underbrace{\mathrm S\_m 1\_m}\_{= 0\_m} \mathrm v^{\top} = \mathrm R + \mathrm O\_{m \times n} = \mathrm R$$


* if $\bar{\mathrm X}$ is a *particular* solution of $\mathrm X \mathrm S\_n^{\top} = \mathrm C$, then so is $\bar{\mathrm X} + \gamma \, \mathrm u 1\_n^{\top}$, where $\gamma \in \mathbb R$ and $\mathrm u \in \mathbb R^m$, as


$$\left( \bar{\mathrm X} + \gamma \, \mathrm u 1\_n^{\top} \right) \mathrm S\_n^{\top} = \underbrace{\bar{\mathrm X} \mathrm S\_n^{\top}}\_{= \mathrm C} + \gamma \, \mathrm u \underbrace{1\_n^{\top} \mathrm S\_n^{\top}}\_{= \mathrm 0\_n^{\top}} = \mathrm C + \mathrm O\_{m \times n} = \mathrm C$$


Thus, if $\bar{\mathrm X}$ is a *particular* solution of both $\mathrm S\_m \mathrm X = \mathrm R$ and $\mathrm X \mathrm S\_n^{\top} = \mathrm C$, then so is


$$\bar{\mathrm X} + \gamma \, 1\_m 1\_n^{\top}$$


where $\gamma \in \mathbb R$. Since there are infinitely many solutions, more information is needed to reconstruct $\mathrm X$.


Suppose now that we are given not only matrices $\mathrm R$ and $\mathrm C$, but also $s \in \mathbb R$, which denotes the *sum* of the $m n$ entries of $\mathrm X$. Appending the equation $1\_m^{\top} \mathrm X 1\_n = s$ to the linear system


$$\mathrm S\_m \mathrm X = \mathrm R \qquad\qquad\qquad \mathrm X \mathrm S\_n^{\top} = \mathrm C \qquad\qquad\qquad 1\_m^{\top} \mathrm X 1\_n = s$$


and [vectorizing](https://en.wikipedia.org/wiki/Vectorization_(mathematics)), we obtain a linear system of $2 m n + 1$ equations in $m n$ unknowns


$$\begin{bmatrix} \mathrm I\_n \otimes \mathrm S\_m\\ \mathrm S\_n \otimes \mathrm I\_m\\ 1\_{mn}^{\top}\end{bmatrix} \mbox{vec} (\mathrm X) = \begin{bmatrix} \mbox{vec} (\mathrm R)\\ \mbox{vec} (\mathrm C)\\ s\end{bmatrix}$$




---


### Minimizing the Frobenius norm


Let us look for the solution that has the least Frobenius norm. We have the quadratic program (QP)


$$\begin{array}{ll} \text{minimize} & \| \mathrm X \|\_{\text{F}}^2\\ \text{subject to} & \mathrm S\_m \mathrm X = \mathrm R\\ & \mathrm X \mathrm S\_n^{\top} = \mathrm C\end{array}$$


We define the Lagrangian


$$\mathcal L (\mathrm X, \Lambda\_1, \Lambda\_2) := \frac 12 \| \mathrm X \|\_{\text{F}}^2 - \langle \Lambda\_1, \mathrm S\_m \mathrm X - \mathrm R \rangle - \langle \Lambda\_2, \mathrm X \mathrm S\_n^{\top} - \mathrm C \rangle$$


Taking the partial derivative with respect to $\mathrm X$ and finding where it vanishes, we obtain


$$\mathrm X = \mathrm S\_m^{\top} \Lambda\_1 + \Lambda\_2 \mathrm S\_n$$


Left-multiplying by $\mathrm S\_m$ and right-multiplying by $\mathrm S\_n^{\top}$, we obtain two coupled linear matrix equations in the Lagrange multipliers $\Lambda\_1$ and $\Lambda\_2$


$$\begin{array}{rl} \mathrm S\_m \mathrm S\_m^{\top} \Lambda\_1 + \mathrm S\_m \Lambda\_2 \mathrm S\_n &= \mathrm R\\ \mathrm S\_m^{\top} \Lambda\_1 \mathrm S\_n^{\top} + \Lambda\_2 \mathrm S\_n \mathrm S\_n^{\top} &= \mathrm C\end{array}$$


[Vectorizing](https://en.wikipedia.org/wiki/Vectorization_(mathematics)), we obtain a linear system of $2 m n$ equations in $2 m n$ unknowns


$$\begin{bmatrix} \mathrm I\_n \otimes \mathrm S\_m \mathrm S\_m^{\top} & \mathrm S\_n^{\top} \otimes \mathrm S\_m\\ \mathrm S\_n \otimes \mathrm S\_m^{\top} & \mathrm S\_n \mathrm S\_n^{\top} \otimes \mathrm I\_m\end{bmatrix} \begin{bmatrix} \mbox{vec} (\Lambda\_1)\\ \mbox{vec} (\Lambda\_2)\end{bmatrix} = \begin{bmatrix} \mbox{vec} (\mathrm R)\\ \mbox{vec} (\mathrm C)\end{bmatrix}$$


Solving this linear system and unvectorizing the solutions, we obtain the optimal Lagrange multipliers $\Lambda\_1^\*$ and $\Lambda\_2^\*$. The *least-norm* solution is then given by


$$\mathrm X\_{\text{LN}} := \mathrm S\_m^{\top} \Lambda\_1^\* + \Lambda\_2^\* \mathrm S\_n$$




---


### Reference


[0] Robert M. Gray, [Toeplitz and Circulant Matrices: A Review](https://ee.stanford.edu/%7Egray/toeplitz.html).


