Orthogonal Procrustes Problem
   HOME

TheInfoList



Click Here for Items Related To - Orthogonal Procrustes Problem
OR:
Orthogonal Procrustes Problem on:   [Wikipedia]   [Google]   [Amazon]

The orthogonal Procrustes problem is a matrix approximation problem in
linear algebra Linear algebra is the branch of mathematics concerning linear equations such as :a_1x_1+\cdots +a_nx_n=b, linear maps such as :(x_1, \ldots, x_n) \mapsto a_1x_1+\cdots +a_nx_n, and their representations in vector spaces and through matrix (mathemat ...
. In its classical form, one is given two
matrices Matrix (: matrices or matrixes) or MATRIX may refer to: Science and mathematics * Matrix (mathematics), a rectangular array of numbers, symbols or expressions * Matrix (logic), part of a formula in prenex normal form * Matrix (biology), the ...
A and B and asked to find an
orthogonal matrix In linear algebra, an orthogonal matrix, or orthonormal matrix, is a real square matrix whose columns and rows are orthonormal vectors. One way to express this is Q^\mathrm Q = Q Q^\mathrm = I, where is the transpose of and is the identi ...
\Omega which most closely maps A to B. Specifically, the orthogonal Procrustes problem is an
optimization problem In mathematics, engineering, computer science and economics Economics () is a behavioral science that studies the Production (economics), production, distribution (economics), distribution, and Consumption (economics), consumption of goo ...
given by Frobenius norm In the field of mathematics, norms are defined for elements within a vector space. Specifically, when the vector space comprises matrices, such norms are referred to as matrix norms. Matrix norms differ from vector norms in that they must also ...
. 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 Peter Schönemann in a 1964 thesis, and shortly after appeared in the journal Psychometrika. This problem is equivalent to finding the nearest orthogonal matrix to a given matrix M=BA^, i.e. solving the ''closest orthogonal approximation problem'' :\min_R\, R-M\, _F \quad\mathrm\quad R^T R=I. To find matrix R, one uses the
singular value decomposition In linear algebra, the singular value decomposition (SVD) is a Matrix decomposition, factorization of a real number, real or complex number, complex matrix (mathematics), matrix into a rotation, followed by a rescaling followed by another rota ...
(for which the entries of \Sigma are non-negative) :M=U\Sigma V^T\,\! to write :R=UV^T.\,\!


Proof of Solution

One proof depends on the basic properties of the Frobenius inner product that induces the
Frobenius norm In the field of mathematics, norms are defined for elements within a vector space. Specifically, when the vector space comprises matrices, such norms are referred to as matrix norms. Matrix norms differ from vector norms in that they must also ...
: : \begin 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 S = U^T \Omega V \\ \end :This quantity S is an orthogonal matrix (as it is a product of orthogonal matrices) and thus the expression is maximised when S equals the identity matrix I. Thus : \begin I &= U^T R V \\ R &= U V^T \\ \end where R is the solution for the optimal value of \Omega that minimizes the norm squared , , \Omega A-B\, _F^2 .


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 In mathematics, orthogonality (mathematics), orthogonality is the generalization of the geometric notion of ''perpendicularity''. Although many authors use the two terms ''perpendicular'' and ''orthogonal'' interchangeably, the term ''perpendic ...
, but not necessarily
orthonormal In linear algebra, two vectors in an inner product space are orthonormal if they are orthogonal unit vectors. A unit vector means that the vector has a length of 1, which is also known as normalized. Orthogonal means that the vectors are all perpe ...
. Alternately, one might constrain it by only allowing rotation matrices (i.e. orthogonal matrices with
determinant In mathematics, the determinant is a Scalar (mathematics), scalar-valued function (mathematics), function of the entries of a square matrix. The determinant of a matrix is commonly denoted , , or . Its value characterizes some properties of the ...
1, also known as special orthogonal matrices). In this case, one can write (using the above decomposition M=U\Sigma V^T) :R=U\Sigma'V^T,\,\! where \Sigma'\,\! is a modified \Sigma\,\!, with the smallest singular value replaced by \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. For more information, see the Kabsch algorithm. The ''unbalanced'' Procrustes problem concerns minimizing the norm of AU - B, where A \in \mathbb^, U \in \mathbb^, and B \in \mathbb^, with m > \ell \ge n, or alternately with complex valued matrices. This is a problem over the
Stiefel manifold In mathematics, the Stiefel manifold V_k(\R^n) is the set of all orthonormal ''k''-frames in \R^n. That is, it is the set of ordered orthonormal ''k''-tuples of vectors in \R^n. It is named after Swiss mathematician Eduard Stiefel. Likewise one ...
U \in U(m,\ell), and has no currently known closed form. To distinguish, the standard Procrustes problem (A \in \mathbb^{m\times m}) 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

Linear algebra Matrix theory Singular value decomposition