正交 Procrustes 問題

Procrustes 和他的客人(點圖看動畫) From http://www.mythweb.com/today/media/procrustes07.gif

$\displaystyle \Vert A\Vert_{F}=\sqrt{\mathrm{trace}(A^TA)}=\sqrt{\sum_{i=1}^m\sum_{j=1}^n a_{ij}^2}$

\displaystyle\begin{aligned} \Vert B-AQ\Vert_F^2&=\hbox{trace}\left((B-AQ)^T(B-AQ)\right)\\ &=\hbox{trace}(B^TB-B^TAQ-Q^TA^TB+Q^TA^TAQ)\\ &=\hbox{trace}(B^TB)-\hbox{trace}(B^TAQ)-\hbox{trace}(Q^TA^TB)+\hbox{trace}(Q^TA^TAQ)\\ &=\hbox{trace}(B^TB)-\hbox{trace}(QB^TA)-\hbox{trace}(A^TBQ^T)+\hbox{trace}(A^TAQQ^T)\\ &=\hbox{trace}(B^TB)-\hbox{trace}(QB^TA)^T-\hbox{trace}(A^TBQ^T)+\hbox{trace}(A^TA)\\ &=\Vert B\Vert_F^2-2\hbox{trace}(A^TBQ^T)+\Vert A\Vert_F^2. \end{aligned}

$\displaystyle \max_{QQ^T=I}\hbox{trace}(A^TBQ^T)$

$\displaystyle L=\hbox{trace}(A^TBQ^T)-\hbox{trace}(\Lambda(QQ^T-I))$

\displaystyle\begin{aligned} \frac{\partial L}{\partial Q}&=\frac{\partial\hbox{trace}(A^TBQ^T)}{\partial Q}-\frac{\partial\hbox{trace}(Q^T\Lambda Q)}{\partial Q}+\frac{\partial\hbox{trace}(\Lambda)}{\partial Q}\\ &=A^TB-(\Lambda+\Lambda^T)Q. \end{aligned}

$\displaystyle U\Sigma V^TQ^T=QV\Sigma^TU^T=QV\Sigma U^T$

\displaystyle\begin{aligned} \hbox{trace}(A^TBQ^T)&=\hbox{trace}(U\Sigma V^TVU^T)=\hbox{trace}(U\Sigma U^T)\\ &=\hbox{trace}(\Sigma UU^T)=\hbox{trace}\Sigma=\sum_{i=1}^n\sigma_i(A^TB).\end{aligned}

$\displaystyle \Vert B-AQ\Vert_F=\Vert B-AUV^T\Vert_F=\sqrt{\Vert A\Vert_F^2+\Vert B\Vert_F^2-2\sum_{i=1}^n\sigma_i(A^TB)}$

\displaystyle\begin{aligned} \Vert B-PAQ\Vert_F^2&=\hbox{trace}\left((B-PAQ)^T(B-PAQ)\right)\\ &=\hbox{trace}(B^TB-B^TPAQ-Q^TA^TP^TB+Q^TA^TP^TPAQ)\\ &=\hbox{trace}(B^TB)-\hbox{trace}(B^TPAQ)-\hbox{trace}(Q^TA^TP^TB)+\hbox{trace}(Q^TA^TAQ)\\ &=\hbox{trace}(B^TB)-\hbox{trace}(QB^TPA)-\hbox{trace}(A^TP^TBQ^T)+\hbox{trace}(A^TAQQ^T)\\ &=\hbox{trace}(B^TB)-\hbox{trace}(QB^TPA)^T-\hbox{trace}(A^TP^TBQ^T)+\hbox{trace}(A^TA)\\ &=\Vert B\Vert_F^2-2\hbox{trace}(A^TP^TBQ^T)+\Vert A\Vert_F^2, \end{aligned}

$A$$B$ 的奇異值分解為 $A=U_1\Sigma_1V_1^T$$B=U_2\Sigma_2V_2^T$，其中 $U_1$$U_2$$m\times m$ 階正交矩陣，$V_1$$V_2$$n\times n$ 階正交矩陣，$\Sigma_1=\begin{bmatrix} S_1&0\\ 0&0 \end{bmatrix}$$\Sigma_2=\begin{bmatrix} S_2&0\\ 0&0 \end{bmatrix}$$m\times n$ 階奇異值矩陣 (零列和零行必須隨 $m$$n$ 的大小調整)，$S_1=\hbox{diag}(\sigma_1(A),\ldots,\sigma_s(A))$$S_2=\hbox{diag}(\sigma_1(B),\ldots,\sigma_s(B))$$s=\min\{m,n\}$。代入奇異值分解，使用跡數循環不變性，

\displaystyle\begin{aligned} \hbox{trace}(A^TP^TBQ^T)&=\hbox{trace}(V_1\Sigma_1^TU_1^TP^TU_2\Sigma_2V_2^TQ^T)\\ &=\hbox{trace}(\Sigma_1^TU_1^TP^TU_2\Sigma_2V_2^TQ^TV_1)\\ &=\hbox{trace}(\Sigma_1^TX^T\Sigma_2Y^T), \end{aligned}

$\displaystyle \max_{XX^T=I\atop{YY^T=I}}\hbox{trace}(\Sigma_1^TX^T\Sigma_2Y^T)$

$\displaystyle L=\hbox{trace}(\Sigma_1^TX^T\Sigma_2Y^T)-\hbox{trace}(\Lambda(XX^T-I))-\hbox{trace}(M(YY^T-I))$

\displaystyle\begin{aligned} \frac{\partial L}{\partial X}&=\frac{\partial\hbox{trace}(X^T\Sigma_2Y^T\Sigma_1^T)}{\partial X}-\frac{\partial\hbox{trace}(X^T\Lambda X-\Lambda)}{\partial X}-\frac{\partial\hbox{trace}(Y^TMY-M)}{\partial X}\\ &=\Sigma_2Y^T\Sigma_1^T-(\Lambda+\Lambda^T)X, \end{aligned}

\displaystyle\begin{aligned} \frac{\partial L}{\partial Y}&=\frac{\partial\hbox{trace}(\Sigma_1^TX^T\Sigma_2Y^T)}{\partial Y}-\frac{\partial\hbox{trace}(X^T\Lambda X-\Lambda)}{\partial Y}-\frac{\partial\hbox{trace}(Y^TMY-M)}{\partial Y}\\ &=\Sigma_1^TX^T\Sigma_2-(M+M^T)Y. \end{aligned}

\displaystyle\begin{aligned} \Sigma_2Y^T\Sigma_1^TX^T&=\Lambda+\Lambda^T\\ \Sigma_1^TX^T\Sigma_2Y^T&=M+M^T. \end{aligned}

\displaystyle\begin{aligned} \Sigma_2Y^T\Sigma_1^TX^T&=X\Sigma_1Y\Sigma_2^T\\ \Sigma_1^TX^T\Sigma_2Y^T&=Y\Sigma_2^TX\Sigma_1 .\end{aligned}

$\displaystyle \Sigma_1^TX^T\Sigma_2Y^T\Sigma_1^TX^T=Y\Sigma_2^TX\Sigma_1\Sigma_1^TX^T$

$\displaystyle \Sigma_1^TX^T\Sigma_2Y^T\Sigma_1^TX^T=\Sigma_1^TX^TX\Sigma_1Y\Sigma_2^T=\Sigma_1^T\Sigma_1Y\Sigma_2^T$

$\displaystyle (Y\Sigma_2^TX)(\Sigma_1\Sigma_1^T)=(\Sigma_1^T\Sigma_1)(Y\Sigma_2^TX)$

$\displaystyle (Y\Sigma_2^TX)_{ij}\sigma_j^2(A)=\sigma_i^2(A)(Y\Sigma_2^TX)_{ij}$

$\displaystyle \hbox{trace}(A^TP^TBQ^T)=\hbox{trace}(\Sigma_1^T\Sigma_2)=\sum_{i=1}^s\sigma_i(A)\sigma_i(B)$

$\displaystyle PAQ=U_2U_1^TU_1\Sigma_1V_1^TV_1V_2^T=U_2\Sigma_1V_2^T$

\displaystyle\begin{aligned} \Vert B-PAQ\Vert_F&=\Vert B-U_2\Sigma_1V_2^T\Vert_F=\sqrt{\Vert A\Vert_F^2+\Vert B\Vert_F^2-2\sum_{i=1}^s\sigma_i(A)\sigma_i(B)}\\ &=\sqrt{\sum_{i=1}^s\sigma_i^2(A)+\sum_{i=1}^s\sigma_i^2(B)-2\sum_{i=1}^s\sigma_i(A)\sigma_i(B)}\\ &=\sqrt{\sum_{i=1}^s\left(\sigma_i(A)-\sigma_i(B)\right)^2}, \end{aligned}

$\displaystyle \Vert A\Vert_F=\sqrt{\sum_{i=1}^s\sigma_i^2(A)}$

$\displaystyle \sum_{i=1}^n\sigma_i(A^TB)\le\sum_{i=1}^{\min\{m,n\}}\sigma_i(A)\sigma_i(B)$

[1] 維基百科：Procrustes
[2] 維基百科：排序不等式

This entry was posted in 線性代數專欄, 二次型 and tagged , , , , , , . Bookmark the permalink.

2 則回應給 正交 Procrustes 問題

1. 張盛東 說：

老師，這種矩陣近似一般在什麼場合下使用呢？