.
Orthogonal Procrustes problem
The orthogonal Procrustes problem [1] is a matrix approximation problem in linear algebra. In its classical form, one is given two matrices A and B and asked to find an orthogonal matrix R which most closely maps A to B. [2] Specifically,
\( R = \arg\min_\Omega \|A\Omega-B\|_F \quad\mathrm{subject\ to}\quad \Omega^T \Omega=I, \)
where \( \|\cdot\|_F\) denotes the Frobenius norm.
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 Peter Schonemann in a 1964 thesis. The individual solution was later published. [3] A proof is also given in [4]
This problem is equivalent to finding the nearest orthogonal matrix to a given matrix \( M=A^{T}B.\) To find this orthogonal matrix R, one uses the singular value decomposition
\( M=U\Sigma V^*\,\!\)
to write
\( R=UV^*.\,\!\)
Proof
One proof depends on basic properties of the standard matrix inner product that induces the Frobenius norm:
\( \begin{align} R &= \arg\min_\Omega \|A\Omega-B\|_F^2 \\ &= \arg\min_\Omega \langle A\Omega-B, A\Omega-B \rangle \\ &= \arg\min_\Omega \|A\|_F^2 + \|B\|_F^2 - 2 \langle A\Omega , B \rangle \\ &= \arg\max_\Omega \langle \Omega , A^T B \rangle \\ &= \arg\max_\Omega \langle U^T \Omega V , \Sigma \rangle \\ &= U \left( \arg\max_{\Omega^{'}} \langle \Omega^{'}, \Sigma \rangle \right) V^T \\ &= U V^T. \end{align} \)
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. [5]
Alternately, one might constrain it by only allowing rotation matrices (i.e. orthogonal matrices with determinant 1, also known as special orthogonal matrices). In this case, one can write (using the above decomposition \(M=U\Sigma V^*)\)
\( R=U\Sigma'V^*,\,\!\)
where \( \Sigma'\,\!\) is a modified \( \Sigma\,\!,\) with the smallest singular value replaced by \( \operatorname{sign}(\det(UV^*)) \)(+1 or -1), and the other singular values replaced by 1, so that the determinant of R is guaranteed to be positive. [6] For more information, see the Kabsch algorithm.
See also
Procrustes analysis
Procrustes transformation
References
Gower, J.C; Dijksterhuis, G.B. (2004), Procrustes Problems, Oxford University Press
Hurley, J.R.; Cattell, R.B. (1962), "Producing direct rotation to test a hypothesized factor structure", Behavioral Science 7 (2): 258–262, doi:10.1002/bs.3830070216
Schonemann, P.H. (1966), "A generalized solution of the orthogonal Procrustes problem" (PDF), Psychometrika 31: 1–10, doi:10.1007/BF02289451.
Zhang, Z. (1998), "A Flexible New Technique for Camera Calibration", (PDF), MSR-TR-98-71 http://research.microsoft.com/en-us/um/people/zhang/Papers/TR98-71.pdf Missing or empty |title= (help)
Everson, R (1997), Orthogonal, but not Orthonormal, Procrustes Problems
Eggert, DW; Lorusso, A; Fisher, RB (1997), "Estimating 3-D rigid body transformations: a comparison of four major algorithms", Machine Vision and Applications 9 (5): 272–290, doi:10.1007/s001380050048
Undergraduate Texts in Mathematics
Graduate Studies in Mathematics
Retrieved from "http://en.wikipedia.org/"
All text is available under the terms of the GNU Free Documentation License
