東京大学 情報理工学研究科 数理情報学 2023年8月実施 第1問

标签：

• Tokyo-University
• Orthogonal-Procrustes-via-Singular-Value-Decomposition
• Singular-Value-Decomposition

Author

Kurosu9991

Description

行列 $A\in\mathbb{R}^{d \times m}$ の第 $(i,j)$ 成分を $a_{i,j}$ 、転置を $A^\top$ と書き、 $\|A\|_\text{F} = \sqrt{\sum_{i=1}^d \sum_{j=1}^m a_{i,j}^2}$ とする。 正方行列 $A\in\mathbb{R}^{d \times d}$ のトレースは $\text{tr}A = \sum_{i=1}^d a_{i,i}$ である。また $I$ を $d \times d$ 単位行列とする。

以下では $d<m$ とし、行列 $X,Y\in\mathbb{R}^{d \times m}$ によって与えられる最適化問題

$$\begin{align} \min_{P\in\mathbb{R}^{d \times d}} \|PX-Y\|_\text{F}^2 \quad \text{subject to} \quad P^\top P=I \tag{*} \end{align}$$

の最適解 $P$ の集合を $\text{OPT}(X,Y)$ と書く。以下の設問に答えよ。

(1) 行列 $A,B\in\mathbb{R}^{d \times m}$ の第 $j$ 列ベクトルをそれぞれ $a_j, b_j$ とし、 $a_j$ のユークリッドノルムを $\|a_j\|_2$ と書く。 行列 $A,B\in\mathbb{R}^{d \times m}$ と正の実数 $w_1, \dots, w_m$ によって与えられる最適化問題

$$\min_{P\in\mathbb{R}^{d \times d}} \sum_{j=1}^m w_j \|Pa_j-b_j\|_2^2 \quad \text{subject to} \quad P^\top P=I$$

の最適解 $P$ の集合が $\text{OPT}(X,Y)$ となるような行列 $X,Y\in\mathbb{R}^{d \times m}$ を一組求めよ。

(2) 行列 $X,Y\in\mathbb{R}^{d \times m}$ によって与えられる最適化問題

$$\max_{P\in\mathbb{R}^{d \times d}} \text{tr}(PXY^\top) \quad \text{subject to} \quad P^\top P=I$$

の最適解 $P$ の集合が $\text{OPT}(X,Y)$ であることを示せ。

(3) 行列 $X,Y\in\mathbb{R}^{d \times m}$ に対して、行列 $XY^\top$ の特異値分解を $XY^\top = U \Sigma V^\top$ と書く。 最適化問題 (*) の最適解の１つ $P\in\text{OPT}(X,Y)$ を行列 $X,Y,U,\Sigma,V$ のうちのいくつかを用いて表せ。

题目描述

对矩阵 $A\in\mathbb{R}^{d\times m}$，以 $a_{i,j}$ 表示其第 $(i,j)$ 个元素，以 $A^\top$ 表示其转置，并定义 Frobenius 范数

$$\|A\|_{\mathrm F} =\sqrt{\sum_{i=1}^d\sum_{j=1}^m a_{i,j}^2}.$$

对方阵 $A\in\mathbb{R}^{d\times d}$，定义

$$\operatorname{tr}A=\sum_{i=1}^d a_{i,i}.$$

此外，以 $I$ 表示 $d\times d$ 单位矩阵。

以下设 $d<m$。对给定的矩阵 $X,Y\in\mathbb{R}^{d\times m}$，考虑优化问题

$$\min_{P\in\mathbb{R}^{d\times d}}\|PX-Y\|_{\mathrm F}^2 \quad\text{subject to}\quad P^\top P=I. \tag{*}$$

将问题 $(*)$ 的所有最优解 $P$ 组成的集合记为 $\operatorname{OPT}(X,Y)$。回答下列问题。

(1) 设矩阵 $A,B\in\mathbb{R}^{d\times m}$ 的第 $j$ 列分别为 $a_j,b_j$，并以 $\|a_j\|_2$ 表示 $a_j$ 的欧几里得范数。给定 $A,B$ 和正实数 $w_1,\ldots,w_m$，考虑

$$\min_{P\in\mathbb{R}^{d\times d}} \sum_{j=1}^m w_j\|Pa_j-b_j\|_2^2 \quad\text{subject to}\quad P^\top P=I.$$

求一组矩阵 $X,Y\in\mathbb{R}^{d\times m}$，使该问题的最优解集合 恰为 $\operatorname{OPT}(X,Y)$。

(2) 证明下列优化问题的最优解集合为 $\operatorname{OPT}(X,Y)$：

$$\max_{P\in\mathbb{R}^{d\times d}} \operatorname{tr}(PXY^\top) \quad\text{subject to}\quad P^\top P=I.$$

(3) 对 $X,Y\in\mathbb{R}^{d\times m}$，设

$$XY^\top=U\Sigma V^\top$$

是 $XY^\top$ 的奇异值分解。使用 $X,Y,U,\Sigma,V$ 中的若干矩阵，表示问题 $(*)$ 的一个最优解 $P\in\operatorname{OPT}(X,Y)$。

考点

• 加权最小二乘的矩阵化：把 $\sqrt{w_j}$ 吸收到 $A,B$ 的各列中，将加权目标统一写成 Frobenius 范数。
• Frobenius 范数与迹：展开 $\|PX-Y\|_{\mathrm F}^2$，利用 $P^\top P=I$ 和迹的循环性把最小化化为迹最大化。
• 正交 Procrustes 与奇异值分解：对 $XY^\top$ 作 SVD，并通过正交变量替换求出达到奇异值之和上界的一个最优 $P$。

Kai

(1)

$$\begin{aligned} \sum_{j=1}^m w_j \|Pa_j-b_j\|_2^2 & = \sum_{j=1}^m \|P\sqrt{w_j}a_j-\sqrt{w_j}b_j\|_2^2 \\ & = \sum_{j=1}^m \|(PAW-BW)_j\|_2^2 \\ & = \|PAW-BW\|_\text{F}^2 \end{aligned}$$

ただし、 $W = \text{diag}\{\sqrt{w_1},\dots,\sqrt{w_m}\}$ であり、 $(PAW-BW)_j$ は行列 $PAW-BW$ の第 $j$ 列ベクトルである。

したがって、 $X=AW, Y=BW$ とすればよい。

(2)

$$\begin{aligned} \|PX-Y\|_\text{F}^2 & = \sum_{j=1}^m \|(PX-Y)_j\|_2^2 \\ & = \sum_{j=1}^m (PX-Y)_j^\top (PX-Y)_j \\ & = \text{tr}\left((PX-Y)^\top (PX-Y)\right) \\ & = \text{tr}(X^\top X+Y^\top Y) - 2\text{tr}(PXY^\top) \end{aligned}$$

ここで、 $\text{tr}(A^\top)=\text{tr}(A)$ と $\text{tr}(AB)=\text{tr}(BA)$ を使用しました。

以上より、最適解 $P$ の集合が $\text{OPT}(X,Y)$ であることを示された。

(3)

与えられた式より、

$$\text{tr}(PXY^\top)=\text{tr}(PU\Sigma V^\top)=\text{tr}(V^\top PU\Sigma)$$

$Q=V^\top PU$ とおくと、 $Q^\top Q=I$ が明らか。

故に、 $\|q_j\|_2^2=1, \quad j=1,2,\dots,d$ 。

よって、

$$\text{tr}(PXY^\top) = \text{tr}(Q\Sigma) = \sum_{j=1}^d \sigma_{j}q_{j,j} \leq \sum_{j=1}^d \sigma_{j} \sqrt{\|q_j\|_2^2} = \sum_{j=1}^d \sigma_{j}$$

さらに、 $P=VU^\top$ とすると $Q=I$ であり、 $\text{tr}(PXY^\top)=\sum_{j=1}^d \sigma_{j}$ である。

したがって、 $P=VU^\top\in\text{OPT}(X,Y)$ がわかる。