Problema de Procrustes ortogonal

Problema de aproximación de matrices en álgebra lineal

El problema ortogonal de Procrustes ^[1] es un problema de aproximación matricial en álgebra lineal . En su forma clásica, se dan dos matrices y y se pide encontrar una matriz ortogonal que se asigne más estrechamente a . ^{[2] [3]} Específicamente, el problema ortogonal de Procrustes es un problema de optimización dado por ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle \Omega }$ ${\displaystyle A}$ ${\displaystyle B}$

$${\displaystyle {\begin{aligned}{\underset {\Omega }{\text{minimize}}}\quad &\|\Omega A-B\|_{F}\\{\text{subject to}}\quad &\Omega ^{T}\Omega =I,\end{aligned}}}$$

donde denota la norma de Frobenius . Este es un caso especial del problema de Wahba (con pesos idénticos; en lugar de considerar dos matrices, en el problema de Wahba las columnas de las matrices se consideran como vectores individuales). Otra diferencia es que el problema de Wahba intenta encontrar una matriz de rotación propia en lugar de solo una ortogonal. ${\displaystyle \|\cdot \|_{F}}$

El nombre Procusto hace referencia a un bandido de la mitología griega que obligaba a sus víctimas a caber en su cama, ya sea estirando sus extremidades o cortándolas.

Solución

Este problema fue resuelto originalmente por Peter Schönemann en una tesis de 1964, y poco después apareció en la revista Psychometrika. ^[4]

Este problema es equivalente a encontrar la matriz ortogonal más cercana a una matriz dada , es decir, resolver el problema de aproximación ortogonal más cercano. ${\displaystyle M=BA^{T}}$

${\displaystyle \min _{R}\|R-M\|_{F}\quad \mathrm {subject\ to} \quad R^{T}R=I}$.

Para encontrar la matriz , se utiliza la descomposición en valores singulares (para la cual las entradas de no son negativas) ${\displaystyle R}$ ${\displaystyle \Sigma }$

${\displaystyle M=U\Sigma V^{T}\,\!}$

escribir

${\displaystyle R=UV^{T}.\,\!}$

Prueba de solución

Una prueba depende de las propiedades básicas del producto interno de Frobenius que induce la norma de Frobenius :

${\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}}}$

Esta cantidad es una matriz ortogonal (ya que es un producto de matrices ortogonales) y por lo tanto la expresión se maximiza cuando es igual a la matriz identidad . Por lo tanto ${\displaystyle S}$ ${\displaystyle S}$ ${\displaystyle I}$

${\displaystyle {\begin{aligned}I&=U^{T}RV\\R&=UV^{T}\\\end{aligned}}}$

donde es la solución para el valor óptimo de que minimiza la norma al cuadrado . ${\displaystyle R}$ ${\displaystyle \Omega }$ ${\displaystyle ||\Omega A-B\|_{F}^{2}}$

Problemas de Procrustes generalizados/restringidos

Existen varios problemas relacionados con el problema ortogonal clásico de Procrustes. Se podría generalizar buscando la matriz más cercana en la que las columnas sean ortogonales , pero no necesariamente ortonormales . ^[5]

Alternativamente, se podría restringir permitiendo únicamente matrices de rotación (es decir, matrices ortogonales con determinante 1, también conocidas como matrices ortogonales especiales ). En este caso, se puede escribir (usando la descomposición anterior ) ${\displaystyle M=U\Sigma V^{T}}$

${\displaystyle R=U\Sigma 'V^{T},\,\!}$

donde es un modificado , con el valor singular más pequeño reemplazado por (+1 o -1), y los otros valores singulares reemplazados por 1, de modo que se garantiza que el determinante de R sea positivo. ^[6] Para obtener más información, consulte el algoritmo de Kabsch . ${\displaystyle \Sigma '\,\!}$ ${\displaystyle \Sigma \,\!}$ ${\displaystyle \det(UV^{T})}$

El problema de Procrustes no balanceado se ocupa de minimizar la norma de , donde , y , con , o alternativamente con matrices de valores complejos. Este es un problema sobre la variedad de Stiefel , y no tiene una forma cerrada conocida actualmente. Para distinguirlo, el problema de Procrustes estándar ( ) se denomina en estos contextos el problema balanceado . ${\displaystyle AU-B}$ ${\displaystyle A\in \mathbb {R} ^{m\times \ell },U\in \mathbb {R} ^{\ell \times n}}$ ${\displaystyle B\in \mathbb {R} ^{m\times n}}$ ${\displaystyle m>\ell \geq n}$ ${\displaystyle U\in U(m,\ell )}$ ${\displaystyle A\in \mathbb {R} ^{m\times m}}$

Véase también

• Análisis de Procusto
• Transformación de Procusto
• El problema de Wahba
• Algoritmo de Kabsch
• Registro de conjunto de puntos

Referencias

1. Gower, JC; Dijksterhuis, GB (2004), Problemas de Procrustes , Oxford University Press
2. Hurley, JR; Cattell, RB (1962), "Producción de rotación directa para probar una estructura factorial hipotética", Behavioral Science , 7 (2): 258–262, doi :10.1002/bs.3830070216
3. Golub, GH; Préstamo Van, C. (2013). Cálculos matriciales (4 ed.). Prensa JHU. pag. 327.ISBN​ 978-1421407944.
4. Schönemann, PH (1966), "Una solución generalizada del problema ortogonal de Procrustes" (PDF) , Psychometrika , 31 : 1–10, doi :10.1007/BF02289451, S2CID  121676935.
5. Everson, R (1997), Problemas de Procrustes ortogonales, pero no ortonormales (PDF)
6. Eggert, DW; Lorusso, A; Fisher, RB (1997), "Estimación de transformaciones de cuerpos rígidos en 3-D: una comparación de cuatro algoritmos principales", Machine Vision and Applications , 9 (5): 272–290, doi :10.1007/s001380050048, S2CID  1611749