Ortogonala procrustes problem

Det ortogonala Procrustes-problemet är ett matrisapproximationsproblem i linjär algebra . I sin klassiska form får man två matriser $A$ och $B$ och ombeds hitta en ortogonal matris $\Omega$ som närmast mappar $A$ till ${ \displaystyle B}$ . Specifikt,

$R=\arg \min _{\Omega }\|\Omega AB\|_ {F}\quad \mathrm {subject\ to} \quad \Omega ^{T}\Omega =I,$

där $\|\cdot \|_{F}$ betecknar Frobenius-normen . Detta är ett specialfall av Wahbas problem (med identiska vikter; istället för att betrakta två matriser, betraktas i Wahbas problem matrisernas kolumner som individuella vektorer). En annan skillnad är att Wahbas problem försöker hitta en riktig rotationsmatris, istället för bara en ortogonal.

Namnet Procrustes syftar på en bandit från den grekiska mytologin som fick sina offer att passa sin säng genom att antingen sträcka ut deras lemmar eller skära av dem.

Lösning

Detta problem löstes ursprungligen av Peter Schönemann i en avhandling från 1964 och dök upp kort efter i tidskriften Psychometrika.

Detta problem är ekvivalent med att hitta den ortogonala matrisen som ligger närmast en given matris ${\displaystyle M=BA^{T}} ,$ dvs lösa det närmaste ortogonala approximationsproblemet

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

För att hitta matrisen $R$ använder man singularvärdesuppdelningen (för vilken inmatningarna av $\Sigma$ är icke-negativa)

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

att skriva

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

Bevis

Ett bevis beror på grundläggande egenskaper hos Frobenius inre produkt som inducerar Frobenius-normen :

${\begin{aligned}R&=\arg \min _ {\Omega }||\Omega AB\|_{F}^{2}\\&=\arg \min _{\Omega }\langle \Omega AB,\Omega AB\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 ,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{där }}S=U^{T}\Omega V\\\end {aligned}}$

Denna kvantitet $S$ är en ortogonal matris (eftersom den är en produkt av ortogonala matriser) och således maximeras uttrycket när $S$ är lika med identitetsmatrisen $I$ . Således

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

där $R$ är lösningen för det optimala värdet av $\Omega$ som minimerar normen i kvadrat $||\Omega AB\|_{F}^{2}$ .

Generaliserade/begränsade Procrustes-problem

Det finns ett antal relaterade problem till det klassiska ortogonala Procrustes-problemet. Man kan generalisera det genom att söka den närmaste matrisen där kolumnerna är ortogonala , men inte nödvändigtvis ortonormala .

Alternativt kan man begränsa det genom att endast tillåta rotationsmatriser (dvs. ortogonala matriser med determinant 1, även känd som speciella ortogonala matriser ). I det här fallet kan man skriva (med ovanstående nedbrytning $M=U\Sigma V^{T}$ )

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

där $\Sigma '\,\!$ är en modifierad $\Sigma \,\!$ , med det minsta singularvärdet ersatt av $\det(UV^ {T})$ (+1 eller -1), och de andra singularvärdena ersatta med 1, så att determinanten för R garanteras vara positiv. För mer information, se Kabsch-algoritmen .

Se även

• Procrustes analys
• Procrustes förvandling
• Wahbas problem
• Kabsch algoritm
• Poänguppsättningsregistrering