4
$\begingroup$

I'm curious about the derivation for the Procrustes transformation. I'm following ESLII: see figure 14.25 and problem 14.8 (Procrustes distance with scaling).

Given matrices $\mathbf{X}_1$ and $\mathbf{X}_2$, both $n$-by-$p$, the problem is \begin{equation*} \min_{\beta, \mathbf{R}} \, \lVert \mathbf{X}_2 - \beta\, \mathbf{X}_1 \mathbf{R} \rVert^2_F \end{equation*} where $\mathbf{R}$ is an orthogonal matrix, i.e. $\mathbf{R}^\intercal \, \mathbf{R} = \mathbf{I}$.

The solution is: \begin{equation*} \hat{\mathbf{R}} = \mathbf{U} \, \mathbf{V}^\intercal \end{equation*} \begin{equation*} \hat{\beta} = \frac{\mathrm{trace}\left(\mathbf{D}\right)}{\lVert \mathbf{X}_1\rVert^2_F} \end{equation*} where $\mathbf{X}_1^\intercal \mathbf{X}_2 = \mathbf{U} \mathbf{D} \mathbf{V}^\intercal$ is a singular value decomposition (i.e. $\mathbf{D}$ is diagonal, and $\mathbf{V}$ and $\mathbf{U}$ are orthonormal).

How does one derive these solutions? I tried differentiating the objective function in the minimization problem with respect to $\mathbf{R}$ and got \begin{equation*} \mathbf{X}_2 \mathbf{X}_1^\intercal = \beta \, \mathbf{X}_1 \,\mathbf{R}\, \mathbf{X}_1^\intercal. \end{equation*} Is that first order condition correct? If so, how does one get from there to the solution?

$\endgroup$
3
$\begingroup$

Start with solving the Procrustes problem without scaling, i.e. without $\beta$.

We have $$\newcommand{\Y}{\mathbf Y} \newcommand{\X}{\mathbf X} \newcommand{\R}{\mathbf R} \newcommand{\U}{\mathbf U} \newcommand{\D}{\mathbf D} \newcommand{\V}{\mathbf V} \newcommand{\P}{\mathbf P} \DeclareMathOperator{trace}{tr} \|\Y-\X\R\|^2 = \|\Y\|^2+\|\X\R\|^2-2\trace(\Y^\top\X\R),$$ where the first two terms are constant. So the problem reduces to minimizing $$\trace(\Y^\top\X\R)=\trace(\U\D\V^\top\R)=\trace(\V^\top\R\U\cdot\D),$$ where I introduced the same SVD as in your question. The above operations are very standard, but now comes the crucial step: inside the trace we have a product of three orthogonal matrices which is itself an orthogonal matrix (denote it as $\P$), times diagonal $\D$. The trace is then equal to $$\sum P_{ii} D_{i}\le\sum D_{i}$$ because diagonal elements of an orthogonal $\P$ can not be larger than 1. To maximize this expression one should take $\P$ equal to the identity matrix. This corresponds to $\hat\R=\V\U^\top$.


To solve the Procrustes problem with scaling, rewrite the Frobenius norm as I did above and note that the optimal $\R$ does not depend on $\beta$. So one can solve for $\R$ first, as above. After plugging in $\hat\R$, one immediately obtains $\hat\beta$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.