東京大学 情報理工学研究科 数理情報学 2024年度 第1問

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\) のうちのいくつかを用いて表せ。

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)\) がわかる。