Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Orthogonal Procrustes problem
open-in-new
<h2 id="solution">Solution</h2> <p>This problem was originally solved by <a href="/facts/Peter_Sch%25C3%25B6nemann/otRgmgDp">Peter Schönemann</a> in a 1964 thesis, and shortly after appeared in the journal Psychometrika.<a class="footnote-ref" id="fnref:4" href="#fn:4"><sup>4</sup></a> </p><p>This problem is equivalent to finding the nearest orthogonal matrix to a given matrix M = B A T {\displaystyle M=BA^{T}} , i.e. solving the <i>closest orthogonal approximation problem</i> </p> min R ‖ R − M ‖ F s u b j e c t t o R T R = I {\displaystyle \min _{R}\|R-M\|_{F}\quad \mathrm {subject\ to} \quad R^{T}R=I} . <p>To find matrix R {\displaystyle R} , one uses the <a href="/facts/Singular_value_decomposition/8t3v6wk3">singular value decomposition</a> (for which the entries of Σ {\displaystyle \Sigma } are non-negative) </p> M = U Σ V T {\displaystyle M=U\Sigma V^{T}\,\!} <p>to write </p> R = U V T . {\displaystyle R=UV^{T}.\,\!} <h3>Proof of Solution</h3> <p>One proof depends on the basic properties of the <a href="/facts/Frobenius_inner_product/E8DB5N9E">Frobenius inner product</a> that induces the <a href="/facts/Frobenius_norm/UJvsb9fF">Frobenius norm</a>: </p> R = arg min Ω | | Ω A − B ‖ F 2 = arg min Ω ⟨ Ω A − B , Ω A − B ⟩ F = arg min Ω ‖ Ω A ‖ F 2 + ‖ B ‖ F 2 − 2 ⟨ Ω A , B ⟩ F = arg min Ω ‖ A ‖ F 2 + ‖ B ‖ F 2 − 2 ⟨ Ω A , B ⟩ F = arg max Ω ⟨ Ω A , B ⟩ F = arg max Ω ⟨ Ω , B A T ⟩ F = arg max Ω ⟨ Ω , U Σ V T ⟩ F = arg max Ω ⟨ U T Ω V , Σ ⟩ F = arg max Ω ⟨ S , Σ ⟩ F where S = U T Ω V {\displaystyle {\begin{aligned}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 ,BA^{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{aligned}}} This quantity S {\displaystyle S} is an orthogonal matrix (as it is a product of orthogonal matrices) and thus the expression is maximised when S {\displaystyle S} equals the identity matrix I {\displaystyle I} . Thus I = U T R V R = U V T {\displaystyle {\begin{aligned}I&=U^{T}RV\\R&=UV^{T}\\\end{aligned}}} <p>where R {\displaystyle R} is the solution for the optimal value of Ω {\displaystyle \Omega } that minimizes the norm squared | | Ω A − B ‖ F 2 {\displaystyle ||\Omega A-B\|_{F}^{2}} . </p> <h2 id="generalizedconstrained-procrustes-problems">Generalized/constrained Procrustes problems</h2> <p>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 <a href="/facts/Orthogonal/JVIjYPog">orthogonal</a>, but not necessarily <a href="/facts/Orthonormal/JfgL1nAh">orthonormal</a>.<a class="footnote-ref" id="fnref:5" href="#fn:5"><sup>5</sup></a> </p><p>Alternately, one might constrain it by only allowing <a href="/facts/Rotation_matrix/c2K2Ftl8">rotation matrices</a> (i.e. orthogonal matrices with <a href="/facts/Determinant/eGYqJ2TF">determinant</a> 1, also known as <a href="/facts/Orthogonal_matrix/WDXBXYB5">special orthogonal matrices</a>). In this case, one can write (using the above decomposition M = U Σ V T {\displaystyle M=U\Sigma V^{T}} ) </p> R = U Σ ′ V T , {\displaystyle R=U\Sigma 'V^{T},\,\!} <p>where Σ ′ {\displaystyle \Sigma '\,\!} is a modified Σ {\displaystyle \Sigma \,\!} , with the smallest singular value replaced by det ( U V T ) {\displaystyle \det(UV^{T})} (+1 or -1), and the other singular values replaced by 1, so that the determinant of R is guaranteed to be positive.<a class="footnote-ref" id="fnref:6" href="#fn:6"><sup>6</sup></a> For more information, see the <a href="/facts/Kabsch_algorithm/UTs3sopK">Kabsch algorithm</a>. </p><p>The <i>unbalanced</i> Procrustes problem concerns minimizing the norm of A U − B {\displaystyle AU-B} , where A ∈ R m × ℓ , U ∈ R ℓ × n {\displaystyle A\in \mathbb {R} ^{m\times \ell },U\in \mathbb {R} ^{\ell \times n}} , and B ∈ R m × n {\displaystyle B\in \mathbb {R} ^{m\times n}} , with m > ℓ ≥ n {\displaystyle m>\ell \geq n} , or alternately with complex valued matrices. This is a problem over the <a href="/facts/Stiefel_manifold/oUn0uPWQ">Stiefel manifold</a> U ∈ U ( m , ℓ ) {\displaystyle U\in U(m,\ell )} , and has no currently known closed form. To distinguish, the standard Procrustes problem ( A ∈ R m × m {\displaystyle A\in \mathbb {R} ^{m\times m}} ) is referred to as the <i>balanced</i> problem in these contexts. </p> <h2 id="see-also">See also</h2> <ul><li><a href="/facts/Procrustes_analysis/slCzxoKk">Procrustes analysis</a></li> <li><a href="/facts/Procrustes_transformation/D2PDHkyf">Procrustes transformation</a></li> <li><a href="/facts/Wahba%2527s_problem/qbJVLbJE">Wahba's problem</a></li> <li><a href="/facts/Kabsch_algorithm/UTs3sopK">Kabsch algorithm</a></li> <li><a href="/facts/Point_set_registration/EevAmm50">Point set registration</a></li></ul> <h2 id="references">References</h2> <ol> <li id="fn:1"><p>Gower, J.C; Dijksterhuis, G.B. (2004), Procrustes Problems, Oxford University Press <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li> <li id="fn:2"><p>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 <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li> <li id="fn:3"><p>Golub, G.H.; Van Loan, C. (2013). Matrix Computations (4 ed.). JHU Press. p. 327. ISBN 978-1421407944. <a href="978-1421407944" target="_blank">978-1421407944</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li> <li id="fn:4"><p>Schönemann, P.H. (1966), "A generalized solution of the orthogonal Procrustes problem" (PDF), Psychometrika, 31: 1–10, doi:10.1007/BF02289451, S2CID 121676935. <a href="/wiki/Peter_Sch%C3%B6nemann" target="_blank">/wiki/Peter_Sch%C3%B6nemann</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></p></li> <li id="fn:5"><p>Everson, R (1997), Orthogonal, but not Orthonormal, Procrustes Problems (PDF) <a href="http://empslocal.ex.ac.uk/people/staff/reverson/uploads/Site/procrustes.pdf" target="_blank">http://empslocal.ex.ac.uk/people/staff/reverson/uploads/Site/procrustes.pdf</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></p></li> <li id="fn:6"><p>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, S2CID 1611749 <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></p></li> </ol>