View source for Orthogonal Procrustes problem

The '''orthogonal Procrustes problem'''<ref>{{Citation | last1=Gower | first1=J.C | last2=Dijksterhuis | first2=G.B. | year=2004 | title=Procrustes Problems | publisher = Oxford University Press}}</ref> is a matrix approximation problem in [[Linear algebra|linear algebra]].  In its classical form, one is given two [[Matrix (mathematics)|matrices]] <math>A</math> and <math>B</math> and asked to find an [[Orthogonal matrix|orthogonal matrix]] <math>\Omega</math> which most closely maps <math>A</math> to <math>B</math>.<ref>{{Citation | last1=Hurley | first1=J.R. | last2=Cattell | first2=R.B. | year=1962 | title=Producing direct rotation to test a hypothesized factor structure | journal = Behavioral Science | volume = 7 | pages=258&ndash;262 | doi=10.1002/bs.3830070216 | issue=2}}</ref><ref>{{cite book| last1=Golub| first1=G.H. | last2=Van Loan | first2=C. | year=2013| title=Matrix Computations | publisher = JHU Press | page=327 | isbn=978-1421407944 | edition=4}}</ref> Specifically, the orthogonal Procrustes problem is an [[Optimization problem|optimization problem]] given by
<math display="block>
\begin{aligned}
   \underset{\Omega}{\text{minimize}}\quad & \|\Omega A-B\|_F \\
    \text{subject to}\quad & \Omega^T
\Omega = I,
\end{aligned}
</math>

where <math>\|\cdot\|_F</math> denotes the Frobenius norm.  This is a special case of [[Wahba's problem]] (with identical weights; instead of considering two matrices, in Wahba's problem the columns of the matrices are considered as individual vectors). Another difference is that Wahba's problem tries to find a proper rotation matrix instead of just an orthogonal one.

The name Procrustes refers to a bandit from Greek mythology who made his victims fit his bed by either stretching their limbs or cutting them off.

== Solution ==
This problem was originally solved by [[Biography:Peter Schönemann|Peter Schönemann]] in a 1964 thesis, and shortly after appeared in the journal Psychometrika.<ref>{{Citation | last=Schönemann | first=P.H. |  year=1966 | title=A generalized solution of the orthogonal Procrustes problem | journal=Psychometrika | volume=31 | pages=1–10 | url=https://web.stanford.edu/class/cs273/refs/procrustes.pdf | doi=10.1007/BF02289451 | s2cid=121676935 | postscript=.}}</ref>

This problem is equivalent to finding the nearest orthogonal matrix to a given matrix <math>M=BA^{T}</math>, i.e. solving the ''closest orthogonal approximation problem''
:<math>\min_R\|R-M\|_F \quad\mathrm{subject\ to}\quad R^T R=I</math>. 
To find matrix <math>R</math>, one uses the [[Singular value decomposition|singular value decomposition]] (for which the entries of <math>\Sigma</math> are non-negative)
:<math>M=U\Sigma V^T\,\!</math>
to write
:<math>R=UV^T.\,\!</math>

=== Proof of Solution ===

One proof depends on the basic properties of the [[Frobenius inner product]] that induces the Frobenius norm:
:<math>
\begin{align}
R &= \arg\min_\Omega ||\Omega A-B\|_F^2 \\
&= \arg\min_\Omega  \langle \Omega A-B, \Omega A-B \rangle_F  \\
&= \arg\min_\Omega  \|\Omega A\|_F^2 + \|B\|_F^2 - 2 \langle \Omega A , B \rangle_F \\
&= \arg\min_\Omega  \|A\|_F^2 + \|B\|_F^2 - 2 \langle \Omega A , B \rangle_F  \\
&= \arg\max_\Omega  \langle \Omega A , B \rangle_F  \\
&= \arg\max_\Omega  \langle \Omega , B A^T \rangle_F  \\
&= \arg\max_\Omega  \langle \Omega, U\Sigma V^T \rangle_F  \\
&= \arg\max_\Omega  \langle U^T \Omega V , \Sigma \rangle_F  \\
&= \arg\max_\Omega  \langle S , \Sigma \rangle_F  \quad \text{where } S = U^T \Omega V \\
\end{align}
</math>
:This quantity <math>S</math> is an orthogonal matrix (as it is a product of orthogonal matrices) and thus the expression is maximised when <math>S</math> equals the identity matrix <math>I</math>. Thus
:<math>
\begin{align}
I &= U^T R V  \\
R &= U V^T \\
\end{align}
</math>
where <math> R </math> is the solution for the optimal value of <math> \Omega </math> that minimizes the norm squared <math>||\Omega A-B\|_F^2  </math>.

== Generalized/constrained Procrustes problems ==
There are a number of related problems to the classical orthogonal Procrustes problem.  One might generalize it by seeking the closest matrix in which the columns are orthogonal, but not necessarily orthonormal.<ref>{{Citation| last=Everson| first=R| year=1997| title=Orthogonal, but not Orthonormal, Procrustes Problems| url=http://empslocal.ex.ac.uk/people/staff/reverson/uploads/Site/procrustes.pdf}}</ref>

Alternately, one might constrain it by only allowing [[Rotation matrix|rotation matrices]] (i.e. orthogonal matrices with [[Determinant|determinant]] 1, also known as [[Orthogonal matrix|special orthogonal matrices]]).  In this case, one can write (using the above decomposition <math>M=U\Sigma V^T</math>)

:<math>R=U\Sigma'V^T,\,\!</math>

where <math>\Sigma'\,\!</math> is a modified <math>\Sigma\,\!</math>, with the smallest singular value replaced by <math>\det(UV^T)</math> (+1 or -1), and the other singular values replaced by 1, so that the determinant of R is guaranteed to be positive.<ref>{{Citation|last1=Eggert|first1=DW| last2=Lorusso|first2=A| last3=Fisher|first3=RB| title=Estimating 3-D rigid body transformations: a comparison of four major algorithms| journal=Machine Vision and Applications| volume=9| issue=5| pages=272&ndash;290| year=1997|doi=10.1007/s001380050048|s2cid=1611749}}</ref> For more information, see the [[Kabsch algorithm]].

The ''unbalanced'' Procrustes problem concerns minimizing the norm of <math>AU - B</math>, where <math>A \in \mathbb{R}^{m\times \ell}, U \in \mathbb{R}^{\ell \times n}</math>, and <math>B \in \mathbb{R}^{m\times n}</math>, with <math>m > \ell \ge n</math>, or alternately with complex valued matrices. This is a problem over the [[Stiefel manifold]] <math>U \in U(m,\ell)</math>, and has no currently known closed form. To distinguish, the standard Procrustes problem (<math>A \in \mathbb{R}^{m\times m}</math>) is referred to as the ''balanced'' problem in these contexts.

== See also ==
* [[Procrustes analysis]]
* [[Procrustes transformation]]
* [[Wahba's problem]]
* [[Kabsch algorithm]]
* [[Point set registration]]

== References ==
<references/>

[[Category:Linear algebra]]
[[Category:Matrix theory]]
[[Category:Singular value decomposition]]

{{Sourceattribution|Orthogonal Procrustes problem}}