Orthogonal Procrustes problem


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 either by stretching their limbs or cutting them off.

Contents

Solution

This problem was originally solved by Peter Schonemann in a 1964 thesis. The individual solution was later published. [3]

This problem is equivalent to finding the nearest orthogonal matrix to a given matrix M = ATB. To find this orthogonal matrix R, one uses the singular value decomposition

M=U\Sigma V^*\,\!

to write

R=UV^*.\,\!

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. [4]

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ΣV * )

R=U\Sigma'V^*,\,\!

where \Sigma'\,\! is a modified \Sigma\,\!, with the smallest singular value replaced by det(UV * ) (+1 or -1), and the other singular values replaced by 1, so that the determinant of R is guaranteed to be positive.[5]

See also

References

  1. ^ Gower, J.C; Dijksterhuis, G.B. (2004), Procrustes Problems, Oxford University Press 
  2. ^ 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 
  3. ^ Schonemann, P.H. (1966), "A generalized solution of the orthogonal Procrustes problem", Psychometrika 31: 1–10, doi:10.1007/BF02289451, http://www2.psych.purdue.edu/~phs/pdf/3.pdf. 
  4. ^ Everson, R (1997), Orthogonal, but not Orthonormal, Procrustes Problems, http://citeseer.ist.psu.edu/everson97orthogonal.html 
  5. ^ 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 

Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Procrustes — Damastes redirects here. See also Huntsman spider. For the Larry Niven story, see Procrustes (short story). Theseus and Procrustes, Attic red figure neck amphora, 570–560 BC, Staatliche Antikensammlungen (Inv. 2325) In Greek mythology Pr …   Wikipedia

  • Orthogonal matrix — In linear algebra, an orthogonal matrix (less commonly called orthonormal matrix[1]), is a square matrix with real entries whose columns and rows are orthogonal unit vectors (i.e., orthonormal vectors). Equivalently, a matrix Q is orthogonal if… …   Wikipedia

  • 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 refers to a bandit from Greek mythology who made his victims fit his bed either by stretching… …   Wikipedia

  • Procrustes transformation — A Procrustes transformation is a geometric transformation involving only translation, scaling, and rigid transformation. Named after the mythical Greek robber, Procrustes. See also * Procrustes analysis * Orthogonal Procrustes problem * Affine… …   Wikipedia

  • Problème de Procuste orthogonal — Le problème de Procuste orthogonal est une variante du problème de Procuste, où une condition d orthogonalité est posée sur la matrice de transformation utilisée. La solution, trouvée en 1964[1] , consiste à utiliser la décomposition en valeurs… …   Wikipédia en Français

  • Peter Schonemann — Peter H. Schönemann is a German born psychometrician and statistical expert. He is Professor Emeritus in the Department of Psychological Sciences at Purdue University. His research interests include multivaritate statistics, multidimensional… …   Wikipedia

  • Singular value decomposition — Visualization of the SVD of a 2 dimensional, real shearing matrix M. First, we see the unit disc in blue together with the two canonical unit vectors. We then see the action of M, which distorts the disk to an ellipse. The SVD decomposes M into… …   Wikipedia

  • List of mathematics articles (O) — NOTOC O O minimal theory O Nan group O(n) Obelus Oberwolfach Prize Object of the mind Object theory Oblate spheroid Oblate spheroidal coordinates Oblique projection Oblique reflection Observability Observability Gramian Observable subgroup… …   Wikipedia

  • Analyse procustéenne — En statistiques, l analyse procustéenne est une technique pour comparer des formes. Elle est utilisée pour déformer un objet afin de le rendre autant que faire se peut semblable à une référence (potentiellement arbitraire), ne laissant apparaître …   Wikipédia en Français

  • List of statistics topics — Please add any Wikipedia articles related to statistics that are not already on this list.The Related changes link in the margin of this page (below search) leads to a list of the most recent changes to the articles listed below. To see the most… …   Wikipedia