正交普鲁克问题

OrthogonalProcrustesProblem

m i n | | A Ω - B | |_{F}^{2} s . t . Ω^{T} Ω = I

其中， $A, B \in R^{m \times n}$ 已知，待求的 $Ω \in R^{n \times n}$ 正交矩阵。

$| | X | |_{F}$ 为Frobenius范数，是矩阵范数的一种：

| | X | |_{F} = \sqrt{t r a c e (X^{T} X)} = \sqrt{\sum_{i, j} x_{i j}^{2}}

即所有元素的平方和。

\begin{aligned} | | A Ω - B | |_{F}^{2} = t r a c e ((A Ω - B)^{T} (A Ω - B)) & = t r a c e (Ω^{T} A^{T} A Ω - B^{T} A Ω - Ω^{T} A^{T} B + B^{T} B) \\ = t r a c e (Ω^{T} A^{T} A Ω) - t r a c e (B^{T} A Ω) - t r a c e (Ω^{T} A^{T} B) + t r a c e (B^{T} B) \\ = t r a c e (Ω^{T} A^{T} A Ω) - 2 t r a c e (B^{T} A Ω) + t r a c e (B^{T} B) \\ = t r a c e (Ω Ω^{T} A^{T} A) - 2 t r a c e (B^{T} A Ω) + t r a c e (B^{T} B) \\ = t r a c e (A^{T} A) - 2 t r a c e (B^{T} A Ω) + t r a c e (B^{T} B) \end{aligned}

所以最小化 $| | A Ω - B | |_{F}$ 价于最大化 $t r a c e (B^{T} A Ω)$ ，即正交普鲁克问题等价于：

m a x t r a c e (C Ω) s . t . Ω^{T} Ω = I

对 $C$ 异值分解： $U \sum V^{T} = C$ ,则上述问题等价于最大化：

\begin{aligned} t r a c e (C Ω) & = t r a c e (U \sum V^{T} Ω) \\ = t r a c e (\sum V^{T} Ω U) \\ = t r a c e (\sum Z) (Z 是 三 个 单 位 正 交 阵 的 乘 积 ， 元 素 \leq 1) \\ = \sum_{i, j} σ_{i, j} z_{i, j} \\ = \sum_{i} σ_{i, i} z_{i, i} \\ \leq \sum_{i} σ_{i, i} \end{aligned}

取等号的条件为： $Z$ 对角元为1.

不妨令 $Z = I = V^{T} Ω U$ ,解得： $Ω = V U^{T}$

References

上次更新: 2025/06/25, 11:25:50