The orthogonal Procrustes problem is a
matrix approximation
In linear algebra, the singular value decomposition (SVD) is a factorization of a real or complex matrix. It generalizes the eigendecomposition of a square normal matrix with an orthonormal eigenbasis to any \ m \times n\ matrix. It is related ...
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 matrices.
...
. In its classical form, one is given two
matrices
Matrix most commonly refers to:
* ''The Matrix'' (franchise), an American media franchise
** ''The Matrix'', a 1999 science-fiction action film
** "The Matrix", a fictional setting, a virtual reality environment, within ''The Matrix'' (franchis ...
and
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 identity ma ...
which most closely maps
to
. Specifically,
:
where
denotes the
Frobenius norm
In mathematics, a matrix norm is a vector norm in a vector space whose elements (vectors) are matrices (of given dimensions).
Preliminaries
Given a field K of either real or complex numbers, let K^ be the -vector space of matrices with m rows ...
. This is a special case of
Wahba's problem
In applied mathematics, Wahba's problem, first posed by Grace Wahba in 1965, seeks to find a rotation matrix ( special orthogonal matrix) between two coordinate systems from a set of (weighted) vector observations. Solutions to Wahba's problem are ...
(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
In Greek mythology, Procrustes (; Greek: Προκρούστης ''Prokroustes'', "the stretcher ho hammers out the metal), also known as Prokoptas, Damastes (Δαμαστής, "subduer") or Polypemon, was a rogue smith and bandit from Attica ...
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
Peter Hans Schönemann (July 15, 1929 – April 7, 2010) was a German born psychometrician and statistical expert. He was professor emeritus in the Department of Psychological Sciences at Purdue University. His research interests included multivari ...
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
, i.e. solving the ''closest orthogonal approximation problem''
:
.
To find matrix
, one uses the
singular value decomposition
In linear algebra, the singular value decomposition (SVD) is a factorization of a real or complex matrix. It generalizes the eigendecomposition of a square normal matrix with an orthonormal eigenbasis to any \ m \times n\ matrix. It is related ...
(for which the entries of
are non-negative)
:
to write
:
Proof
One proof depends on basic properties of the
Frobenius inner product
In mathematics, the Frobenius inner product is a binary operation that takes two matrices and returns a scalar. It is often denoted \langle \mathbf,\mathbf \rangle_\mathrm. The operation is a component-wise inner product of two matrices as though t ...
that induces the
Frobenius norm
In mathematics, a matrix norm is a vector norm in a vector space whose elements (vectors) are matrices (of given dimensions).
Preliminaries
Given a field K of either real or complex numbers, let K^ be the -vector space of matrices with m rows ...
:
:
:This quantity
is an orthogonal matrix (as it is a product of orthogonal matrices) and thus the expression is maximised when
equals the identity matrix
. Thus
:
where
is the solution for the optimal value of
that minimizes the norm squared
.
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 is the generalization of the geometric notion of ''perpendicularity''.
By extension, orthogonality is also used to refer to the separation of specific features of a system. The term also has specialized meanings in ...
, but not necessarily
orthonormal
In linear algebra, two vectors in an inner product space are orthonormal if they are orthogonal (or perpendicular along a line) unit vectors. A set of vectors form an orthonormal set if all vectors in the set are mutually orthogonal and all of un ...
.
Alternately, one might constrain it by only allowing
rotation matrices (i.e. orthogonal matrices with
determinant
In mathematics, the determinant is a scalar value that is a function of the entries of a square matrix. It characterizes some properties of the matrix and the linear map represented by the matrix. In particular, the determinant is nonzero if and ...
1, also known as
special orthogonal matrices). In this case, one can write (using the above decomposition
)
:
where
is a modified
, with the smallest singular value replaced by
(+1 or -1), and the other singular values replaced by 1, so that the determinant of R is guaranteed to be positive.
[{{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–290, year=1997, doi=10.1007/s001380050048, s2cid=1611749] For more information, see the
Kabsch algorithm The Kabsch algorithm, named after Wolfgang Kabsch, is a method for calculating the optimal rotation matrix that minimizes the RMSD ( root mean squared deviation) between two paired sets of points. It is useful in graphics, cheminformatics to compar ...
.
See also
*
Procrustes analysis
In statistics, Procrustes analysis is a form of statistical shape analysis used to analyse the distribution of a set of shapes. The name ''Procrustes'' ( el, Προκρούστης) refers to a bandit from Greek mythology who made his victims fi ...
*
Procrustes transformation
A Procrustes transformation is a geometric transformation that involves only translation, rotation, uniform scaling, or a combination of these transformations. Hence, it may change the size, position, and orientation of a geometric object, but n ...
*
Wahba's problem
In applied mathematics, Wahba's problem, first posed by Grace Wahba in 1965, seeks to find a rotation matrix ( special orthogonal matrix) between two coordinate systems from a set of (weighted) vector observations. Solutions to Wahba's problem are ...
*
Kabsch algorithm The Kabsch algorithm, named after Wolfgang Kabsch, is a method for calculating the optimal rotation matrix that minimizes the RMSD ( root mean squared deviation) between two paired sets of points. It is useful in graphics, cheminformatics to compar ...
*
Point set registration
In computer vision, pattern recognition, and robotics, point-set registration, also known as point-cloud registration or scan matching, is the process of finding a spatial transformation (''e.g.,'' scaling, rotation and translation) that aligns t ...
References
Linear algebra
Matrix theory
Singular value decomposition