A Centroid Coincidence Theorem

While reviewing shape matching problem between 3D point sets of rigid object using least squares approximation. I found A Centroid Coincidence Theorem, which interest me. So I organize the proof of the theorem and related notions in here. 

I'll follow mathematical notation of [1] as possible as I can. But, since, the mathematical notations in [1] is to implicit, I write it more explicitly (because of my poor imagination and mathematical skills).

Problem

Let two 3-D point sets as $p_i = [x_i, y_i, z_i]^t, p^{'}_i = [x^{'}_i, y^{'}_i, z^{'}_i]^t, i= 1,2,\cdots,N$. Which is related by (1) where $R$ is $3\times 3$ rotation matrix, $T$ is $3\times 1$ translation vector, and $N_i$ a noise vector.
$$\begin{align}     p^{'}_i &= Rp_i + T + N_i \tag{1} \end{align}$$

And let mathematical formulation of shape matching of 3D point sets using least squares approximation as (2).

$$\begin{align}    \underset{R, T} {\operatorname{argmin}} \sum_{i=1}^{N} \| p^{'}_i - (Rp_i + T) \|^2  \tag{2} \end{align}$$

Then the Theorem 1 is satisfied..

Theorem 1 (A Centroid Coincidence Theorem) Let $\hat{R}$ and $\hat{T}$ be the least-squares solution to (2). Then the centroids of $\{ p^{'}_i \}$ and $\{ \hat{R} p_i + \hat{T} \}$ coincide.

Proof

Let
$$% '&=' sign in align region means align at equal sign. \begin{align}     p^{'}_i &= Rp_i + T + N_{i} \tag{3} \\     p^{''}_i &= [ x^{''}_i, y^{''}_i, z^{''}_i ] \triangleq \hat{R} p_i + \hat{T} \tag{4} \\     p &\triangleq \sum_{i=1}^{N} p_i \ (Centroid\ of\ \{ p_i \}) \tag{5} \\     p^{'} &\triangleq \sum_{i=1}^{N} p^{'}_i \ (Centroid\ of\ \{ p^{'}_i \}) \tag{6} \\     p^{''} &\triangleq \sum_{i=1}^{N} p^{''}_i \ (Centroid\ of\ \{ p^{''}_i \}). \tag{7} \\ \end{align}$$

We reformulate our problem as follows:

$$\begin{align}     \underset{ \{ p^{''}_i \} } {\operatorname{argmin}} \sum_{i=1}^{N} \| p^{'}_i - p^{''}_i \|^2  \tag{8} \end{align}$$

subject to the rigidity constraints

$$\begin{align}\| p^{''}_i - p^{''}_j \|^2 = \| p_i - p_j \|^2, \forall i, j \end{align}$$

Note that $p_i, p^{'}_i$ are known, and $p^{''}_i$ is unknown variable.

We can attempt to solve above problem with Lagrangian Multipliers.

Let

$$\begin{align} f( p^{''}_1 , \dots , p^{''}_N ) &= \sum_{i=1}^{N} w_i \| p^{'}_i - p^{''}_i \|^2 \tag{9} \\ g_{ij}( p^{''}_1 , \dots , p^{''}_N ) &= \| p^{''}_i - p^{''}_j \|^2 - \| p_i - p_j \|^2 \tag{10} \end{align}$$

Then, the equation for Lagrangian Multipliers can be formulated as follows: 

$$\begin{align}\nabla f( p^{''}_1 , \dots , p^{''}_N ) =  \sum_{i=1}^{N} \sum_{j=1}^{N} \lambda_{ij} \nabla g_{ij}( p^{''}_1 , \dots , p^{''}_N ) \tag{11}\end{align}$$

where $\lambda_{ij} = \lambda_{ji}$ (because, obiviously, $g_{ij}$ and $g_{ji}$ are same function.)

Then, system of equations is derived from Equ. (11) as follows:

$$\begin{align}       2w_{1}(x^{''}_1 - x^{'}_1) &= 4 \sum_{j=1}^{N} \lambda_{ij} (x^{''}_1 - x^{''}_j) \\       2w_{2}(x^{''}_2 - x^{'}_2) &= 4 \sum_{j=1}^{N} \lambda_{ij} (x^{''}_2 - x^{''}_j) \\      &\vdots \\       2w_{N}(x^{''}_N - x^{'}_N) &= 4 \sum_{j=1}^{N} \lambda_{ij} (x^{''}_N - x^{''}_j) \\ \end{align}$$
Summation of equations in above system produces, $$\begin{align} 2 \sum_{i = 1}^{N} w_i(x^{''}_i - x^{'}_i) &= 0 \\ \sum_{i = 1}^{N} w_i x^{''}_i &= \sum_{i = 1}^{N} w_i x^{'}_i \\ \end{align}$$ $$Q.E.D.$$

Insight

It shows that the determination of $R$ and $T$ can be decoupled by translating original point set with its center of mass.

Reference

[1] Lin, Zse Cherng, et al. "MOTION ESTIMATION FROM 3-D POINT SETS WITH AND WITHOUT CORRESPONDENCES." Unknown Host Publication Title. IEEE, 1986. 194-201.