Ex. 14.8

Ex. 14.8

Derive the solution (14.57) to the Procrustes problem (14.56). Derive also the solution to the Procrustes problem with scaling (14.58).

Soln. 14.8

We first derive the solution (14.57). We need to solve the following optimization problem

$$\begin{array}{rcl}& & \underset{\mu ,\mathbf{\text{R}}}{min}\text{trace}\left[{({\mathbf{\text{X}}}_2-({\mathbf{\text{X}}}_1\mathbf{\text{R}}+\mathbf{\text{1}}{\mu }^T))}^T({\mathbf{\text{X}}}_2-({\mathbf{\text{X}}}_1\mathbf{\text{R}}+\mathbf{\text{1}}{\mu }^T))\right]\\ & & \text{s.t.}{\mathbf{\text{R}}}^T\mathbf{\text{R}}=\mathbf{\text{I}}.\end{array}$$

The Lagrangian for the problem is

$$\begin{array}{rcl}L(\mu ,\mathbf{\text{R}},\mathbf{\text{A}})& =& \text{trace}\left[{({\mathbf{\text{X}}}_2-({\mathbf{\text{X}}}_1\mathbf{\text{R}}+\mathbf{\text{1}}{\mu }^T))}^T({\mathbf{\text{X}}}_2-({\mathbf{\text{X}}}_1\mathbf{\text{R}}+\mathbf{\text{1}}{\mu }^T))\right]\\ & & +\text{trace}[\mathbf{\text{A}}({\mathbf{\text{R}}}^T\mathbf{\text{R}}-\mathbf{\text{I}})].\end{array}$$

By properties of derivatives on trace operator, we calculate the derivatives w.r.t to $\mu ,\mathbf{\text{R}}$ and set them to zero, which gives

$$\begin{array}{rcl}\frac{\partial L(\mu ,\mathbf{\text{R}},\mathbf{\text{A}})}{\partial \mu }& =& -2{\mathbf{\text{X}}}_2^T\cdot \mathbf{\text{1}}+{\mathbf{\text{R}}}^T{\mathbf{\text{X}}}_1^T\cdot \mathbf{\text{1}}+2N\mu =0\\ \frac{\partial L(\mu ,\mathbf{\text{R}},\mathbf{\text{A}})}{\partial \mathbf{\text{R}}}& =& 2{\mathbf{\text{X}}}_1^T{\mathbf{\text{X}}}_1\mathbf{\text{R}}-2{\mathbf{\text{X}}}_1^T{\mathbf{\text{X}}}_2-2{\mathbf{\text{X}}}_1^T\mathbf{\text{1}}{\mu }^T+\mathbf{\text{R}}(\mathbf{\text{A}}+{\mathbf{\text{A}}}^T)=0\end{array}$$

From the first equation above, we get

$$\begin{array}{rcl}\hat{\mu }& =& \frac{1}{N}{\mathbf{\text{X}}}_2^T\cdot \mathbf{\text{1}}-\frac{1}{N}{\mathbf{\text{R}}}^T\cdot {\mathbf{\text{X}}}_1^T\cdot \mathbf{\text{1}}\\ & =& {\overline{x}}_2-{\mathbf{\text{R}}}^T{\overline{x}}_1.\end{array}$$

Plug above into the second condition for $\mathbf{\text{R}}$ we get (by some algebra)

$$\begin{array}{}\text{(1)}& {\widetilde{\mathbf{\text{X}}}}_1^T{\widetilde{\mathbf{\text{X}}}}_2={\widetilde{\mathbf{\text{X}}}}_1^T{\widetilde{\mathbf{\text{X}}}}_1\mathbf{\text{R}}+\mathbf{\text{R}}\overline{\mathbf{\text{A}}},\end{array}$$

where

$$\begin{array}{rcl}{\widetilde{\mathbf{\text{X}}}}_i& =& {\mathbf{\text{X}}}_i-\mathbf{\text{1}}{\overline{x}}_i^T\\ \overline{\mathbf{\text{A}}}& =& \frac{\mathbf{\text{A}}+{\mathbf{\text{A}}}^T}{2}.\end{array}$$

Since ${\mathbf{\text{R}}}^T\mathbf{\text{R}}=\mathbf{\text{I}}$, multiply ${\mathbf{\text{R}}}^T$ on both sides of $\text{(1)}$ we get

$${\mathbf{\text{R}}}^T{\widetilde{\mathbf{\text{X}}}}_1^T{\widetilde{\mathbf{\text{X}}}}_2={\mathbf{\text{R}}}^T{\widetilde{\mathbf{\text{X}}}}_1^T{\widetilde{\mathbf{\text{X}}}}_1\mathbf{\text{R}}+\overline{\mathbf{\text{A}}}.$$

Since both summands on the right hand side are symmetric, we know that ${\mathbf{\text{R}}}^T{\widetilde{\mathbf{\text{X}}}}_1^T{\widetilde{\mathbf{\text{X}}}}_2={\widetilde{\mathbf{\text{X}}}}_2^T{\widetilde{\mathbf{\text{X}}}}_1^T\mathbf{\text{R}}$. Now it's easy to verify that

$$\widehat{\mathbf{\text{R}}}=\mathbf{\text{U}}{\mathbf{\text{V}}}^T$$

satisfies the condition, where ${\widetilde{\mathbf{\text{X}}}}_1{\widetilde{\mathbf{\text{X}}}}_2=\mathbf{\text{U}}\mathbf{\text{D}}{\mathbf{\text{V}}}^T$.

For the problem with scaling (14.58), the idea is the similar. The Lagrangian is

$$\begin{array}{rcl}L(\beta ,\mathbf{\text{R}},\mathbf{\text{A}})& =& \text{trace}[({\mathbf{\text{X}}}_2-\beta {\mathbf{\text{X}}}_1\mathbf{\text{R}}{)}^T({\mathbf{\text{X}}}_2-\beta {\mathbf{\text{X}}}_1\mathbf{\text{R}})]+\text{trace}[\mathbf{\text{A}}({\mathbf{\text{R}}}^T\mathbf{\text{R}}-\mathbf{\text{I}})].\end{array}$$

We have

$$\begin{array}{rcl}\frac{\partial L(\beta ,\mathbf{\text{R}},\mathbf{\text{A}})}{\partial \beta }& =& -2\text{trace}[{\mathbf{\text{X}}}_2{\mathbf{\text{R}}}^T{\mathbf{\text{X}}}_1^T]+2\beta \text{trace}[{\mathbf{\text{R}}}^T{\mathbf{\text{X}}}_1^T{\mathbf{\text{X}}}_1\mathbf{\text{R}}]\\ & =& -2\text{trace}[{\mathbf{\text{X}}}_2{\mathbf{\text{R}}}^T{\mathbf{\text{X}}}_1^T]+2\beta \text{trace}[\mathbf{\text{R}}{\mathbf{\text{R}}}^T{\mathbf{\text{X}}}_1^T{\mathbf{\text{X}}}_1]\\ & =& -2\text{trace}[{\mathbf{\text{X}}}_2{\mathbf{\text{R}}}^T{\mathbf{\text{X}}}_1^T]+2\beta \text{trace}[{\mathbf{\text{X}}}_1^T{\mathbf{\text{X}}}_1].\end{array}$$

Therefore we see

$$\begin{array}{}\text{(2)}& \hat{\beta }=\frac{\text{trace}[{\mathbf{\text{R}}}^T{\mathbf{\text{X}}}_1^T{\mathbf{\text{X}}}_2]}{\Vert {\mathbf{\text{X}}}_1{\Vert }_F}.\end{array}$$

With $\hat{\beta }$ fixed, we already derived $\widehat{\mathbf{\text{R}}}$ in the first part of this exercise, with ${\widetilde{\mathbf{\text{X}}}}_1$ replaced with $\hat{\beta }{\widetilde{\mathbf{\text{X}}}}_1$. Therefore we know $\widehat{\mathbf{\text{R}}}=\mathbf{\text{U}}{\mathbf{\text{V}}}^T$ as before. Plug $\widehat{\mathbf{\text{R}}}$ into $\text{(2)}$ we have

$$\begin{array}{rcl}\hat{\beta }& =& \frac{\text{trace}[\mathbf{\text{V}}{\mathbf{\text{U}}}^T\mathbf{\text{U}}\mathbf{\text{D}}{\mathbf{\text{V}}}^T]}{\Vert {\mathbf{\text{X}}}_1{\Vert }_F}\\ & =& \frac{\text{trace}[\mathbf{\text{D}}]}{\Vert {\mathbf{\text{X}}}_1{\Vert }_F}.\end{array}$$