正交普鲁克问题

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$

References