Orthogonal Procrustes problem
The orthogonal Procrustes problem is a matrix approximation problem in linear algebra. In its classical form, one is given two matrices and and asked to find an orthogonal matrix which most closely maps to . Specifically,
where denotes the Frobenius norm. 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.
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 (for which the entries of are non-negative)
- 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, but not necessarily orthonormal.
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 )
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. For more information, see the Kabsch algorithm.
- Procrustes analysis
- Procrustes transformation
- Wahba's problem
- Kabsch algorithm
- Point set registration
- 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
- Golub, G.H.; Van Loan, C. (2013). Matrix Computations (4 ed.). JHU Press. p. 327. ISBN 1421407949.
- Schönemann, P.H. (1966), "A generalized solution of the orthogonal Procrustes problem" (PDF), Psychometrika, 31: 1–10, doi:10.1007/BF02289451, S2CID 121676935.
- Everson, R (1997), Orthogonal, but not Orthonormal, Procrustes Problems (PDF)
- 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