正交普鲁克问题¶
OrthogonalProcrustesProblem
min||A\Omega - B||^2_F \
s.t. \Omega^T\Omega=I
其中，A,B\in R^{m \times n}已知，待求的\Omega \in R^{n \times n} 正交矩阵。
||X||F 为Frobenius范数，是矩阵范数的一种：
||X||_F= \sqrt{trace(X^TX)}=\sqrt{\sum{i,j}x_{ij}^2}
即所有元素的平方和。
\begin{split}
||A\Omega-B ||F^2=trace((A\Omega-B)^T(A\Omega-B))
&=trace(\Omega^TA^TA\Omega-B^TA\Omega-\Omega^TA^TB+B^TB)\
&=trace(\Omega^TA^TA\Omega)-trace(B^TA\Omega)-trace(\Omega^TA^TB)+trace(B^TB)\
&=trace(\Omega^TA^TA\Omega)-2trace(B^TA\Omega)+trace(B^TB)\
&=trace(\Omega\Omega^T A^TA)-2trace(B^TA\Omega)+trace(B^TB)\
&=trace(A^TA)-2trace(B^TA\Omega)+trace(B^TB)
\end{split}
所以最小化||A\Omega-B||_F 价于最大化trace(B^TA\Omega)，即正交普鲁克问题等价于：
max\quad trace(C\Omega)\
s.t.\quad \Omega^T\Omega=I
对C 异值分解：U\sum V^T=C,则上述问题等价于最大化：
\begin{split}
trace(C\Omega)
&=trace(U\sum V^T\Omega)\
&=trace(\sum V^T\Omega U)\
&=trace(\sum Z) \quad (Z是三个单位正交阵的乘积，元素\leq 1) \
&=\sum {i,j}\sigma_{i,j}z_{i,j}\
&=\sum {i}\sigma{i,i}z_{i,i}\
&\le \sum {i}\sigma{i,i}
\end{split}
取等号的条件为：Z 对角元为1.
不妨令Z=I=V^T\Omega U,解得：\Omega = VU^T
评论