東京大学 新領域創成科学研究科 メディカル情報生命専攻 2024年8月実施 問題8

标签：

• Tokyo-University
• Singular-Value-Decomposition
• Low-Rank-Approximation
• Moore-Penrose-Pseudoinverse
• Matrix-Trace

Author

KardeniaPoyu

Description

以下で $\mathbb{R}^{n \times m}$ は $n$ 行 $m$ 列实数値行列の集合を表すものとする。 正則行列 $A \in \mathbb{R}^{n \times n}$ の特異値分解は以下で与えられる ($n \ge 2$)。

$$A = U \Sigma V^T$$

ここで、$U \in \mathbb{R}^{n \times n}, V \in \mathbb{R}^{n \times n}$ は $U^T U = I_n, V^T V = I_n$ をみたし、$\Sigma = \text{diag}(\sigma_1, \dots, \sigma_n) \in \mathbb{R}^{n \times n}$ は対角行列でその対角成分は $\sigma_1 \ge \dots \ge \sigma_n > 0$ を満たす。ただし、$M^T$ は行列 $M$ の転置を表し、$I_m \in \mathbb{R}^{m \times m}$ は単位行列である。

$A$ のランク $r$ 近似 $\hat{A}$ を以下で定義する ($1 \le r < n$)。

$$\hat{A} = \hat{U} \hat{\Sigma} \hat{V}^T$$

ここで、$\hat{U} \in \mathbb{R}^{n \times r}, \hat{V} \in \mathbb{R}^{n \times r}$ は $U, V$ の最初の $r$ 列からなる行列であり、$\hat{\Sigma} = \text{diag}(\sigma_1, \dots, \sigma_r) \in \mathbb{R}^{r \times r}$ である。$\hat{A}$ は以下の最適化问题の一つの解 $X$ を与えることが知られている。

$$\min_{X} \|A - X\|^2 \quad \text{subject to } X \in \mathbb{R}^{n \times n}, \text{rank}(X) = r$$

ただし、$\|M\|^2 = \text{trace}(M^T M) = \sum_{i,j} (M_{ij})^2$ である。 以下の問いに導出も含めて答えよ。

(1) $\hat{A}^T \hat{A}, \hat{A} \hat{A}^T$ の特異値分解を求めよ。

(2) $\hat{A}^+ = \hat{V} \hat{\Sigma}^{-1} \hat{U}^T$ とするとき、$A \hat{A}^+ A = \hat{A}$ を示せ。

(3) 次の最適化問題の解を求めよ。

$$\min_{X} \|A - XX^T A\|^2 \quad \text{subject to } X \in \mathbb{R}^{n \times r}, X^T X = I_r$$

(4) 次の最適化問題の解を求めよ。

$$\max_{X} \text{trace}(X^T A A^T X) \quad \text{subject to } X \in \mathbb{R}^{n \times r}, X^T X = I_r$$

(5) $B \in \mathbb{R}^{n \times n}, C \in \mathbb{R}^{n \times n}$ を用いて $A = BC$ と書けるとする。次の最適化問題の解を求めよ。

$$\min_{X} \|BC - BXC\|^2 \quad \text{subject to } X \in \mathbb{R}^{n \times n}, \text{rank}(X) = r$$

Kai

(1)

定義より、$\hat{A} = \hat{U}\hat{\Sigma}\hat{V}^T$ であり、$\hat{U}^T\hat{U} = I_r$、$\hat{V}^T\hat{V} = I_r$ を満たす。

まず、$\hat{A}^T\hat{A}$ について計算する。

$$\hat{A}^T\hat{A} = (\hat{U}\hat{\Sigma}\hat{V}^T)^T (\hat{U}\hat{\Sigma}\hat{V}^T) = \hat{V}\hat{\Sigma}^T\hat{U}^T \hat{U}\hat{\Sigma}\hat{V}^T$$

$\hat{\Sigma}$ は対角行列であるため $\hat{\Sigma}^T = \hat{\Sigma}$ であり、$\hat{U}^T\hat{U} = I_r$ より、

$$\hat{A}^T\hat{A} = \hat{V}\hat{\Sigma} I_r \hat{\Sigma}\hat{V}^T = \hat{V}\hat{\Sigma}^2\hat{V}^T$$

これが $\hat{A}^T\hat{A}$ のコンパクト特異値分解（あるいは固有値分解）の形である。$n \times n$ 行列としての完全な特異値分解で表すと、直交行列 $V$ を用いて以下のようになる。

$$\hat{A}^T\hat{A} = V \begin{pmatrix} \hat{\Sigma}^2 & 0 \\ 0 & 0 \end{pmatrix} V^T$$

同様に、$\hat{A}\hat{A}^T$ について計算する。

$$\hat{A}\hat{A}^T = (\hat{U}\hat{\Sigma}\hat{V}^T) (\hat{U}\hat{\Sigma}\hat{V}^T)^T = \hat{U}\hat{\Sigma}\hat{V}^T \hat{V}\hat{\Sigma}\hat{U}^T$$

$\hat{V}^T\hat{V} = I_r$ より、

$$\hat{A}\hat{A}^T = \hat{U}\hat{\Sigma} I_r \hat{\Sigma}\hat{U}^T = \hat{U}\hat{\Sigma}^2\hat{U}^T$$

完全な特異値分解で表すと、直交行列 $U$ を用いて以下のようになる。

$$\hat{A}\hat{A}^T = U \begin{pmatrix} \hat{\Sigma}^2 & 0 \\ 0 & 0 \end{pmatrix} U^T$$

English: By definition, $\hat{A} = \hat{U}\hat{\Sigma}\hat{V}^T$, satisfying $\hat{U}^T\hat{U} = I_r$ and $\hat{V}^T\hat{V} = I_r$.

First, we calculate $\hat{A}^T\hat{A}$:

$$\hat{A}^T\hat{A} = (\hat{U}\hat{\Sigma}\hat{V}^T)^T (\hat{U}\hat{\Sigma}\hat{V}^T) = \hat{V}\hat{\Sigma}^T\hat{U}^T \hat{U}\hat{\Sigma}\hat{V}^T$$

Since $\hat{\Sigma}$ is a diagonal matrix, $\hat{\Sigma}^T = \hat{\Sigma}$. Using $\hat{U}^T\hat{U} = I_r$, we have:

$$\hat{A}^T\hat{A} = \hat{V}\hat{\Sigma} I_r \hat{\Sigma}\hat{V}^T = \hat{V}\hat{\Sigma}^2\hat{V}^T$$

This is the compact SVD (or eigenvalue decomposition) of $\hat{A}^T\hat{A}$. As a full SVD for an $n \times n$ matrix using the orthogonal matrix $V$, it is written as:

$$\hat{A}^T\hat{A} = V \begin{pmatrix} \hat{\Sigma}^2 & 0 \\ 0 & 0 \end{pmatrix} V^T$$

Similarly, calculating $\hat{A}\hat{A}^T$:

$$\hat{A}\hat{A}^T = (\hat{U}\hat{\Sigma}\hat{V}^T) (\hat{U}\hat{\Sigma}\hat{V}^T)^T = \hat{U}\hat{\Sigma}\hat{V}^T \hat{V}\hat{\Sigma}\hat{U}^T$$

Using $\hat{V}^T\hat{V} = I_r$, we have:

$$\hat{A}\hat{A}^T = \hat{U}\hat{\Sigma} I_r \hat{\Sigma}\hat{U}^T = \hat{U}\hat{\Sigma}^2\hat{U}^T$$

As a full SVD using the orthogonal matrix $U$, it is written as:

$$\hat{A}\hat{A}^T = U \begin{pmatrix} \hat{\Sigma}^2 & 0 \\ 0 & 0 \end{pmatrix} U^T$$

(2)

$\hat{A} = \hat{U}\hat{\Sigma}\hat{V}^T$ および $\hat{A}^+ = \hat{V}\hat{\Sigma}^{-1}\hat{U}^T$ を左辺に代入して計算する。

$$\begin{aligned} \hat{A}\hat{A}^+\hat{A} &= (\hat{U}\hat{\Sigma}\hat{V}^T) (\hat{V}\hat{\Sigma}^{-1}\hat{U}^T) (\hat{U}\hat{\Sigma}\hat{V}^T) \\ &= \hat{U}\hat{\Sigma} (\hat{V}^T\hat{V}) \hat{\Sigma}^{-1} (\hat{U}^T\hat{U}) \hat{\Sigma}\hat{V}^T \end{aligned}$$

$\hat{V}^T\hat{V} = I_r$ および $\hat{U}^T\hat{U} = I_r$ であるため、

$$\begin{aligned} \hat{A}\hat{A}^+\hat{A} &= \hat{U}\hat{\Sigma} I_r \hat{\Sigma}^{-1} I_r \hat{\Sigma}\hat{V}^T \\ &= \hat{U} (\hat{\Sigma}\hat{\Sigma}^{-1}\hat{\Sigma}) \hat{V}^T \\ &= \hat{U}\hat{\Sigma}\hat{V}^T \\ &= \hat{A} \end{aligned}$$

以上より、$\hat{A}\hat{A}^+\hat{A} = \hat{A}$ が示された。

English: Substitute $\hat{A} = \hat{U}\hat{\Sigma}\hat{V}^T$ and $\hat{A}^+ = \hat{V}\hat{\Sigma}^{-1}\hat{U}^T$ into the left side:

$$\begin{aligned} \hat{A}\hat{A}^+\hat{A} &= (\hat{U}\hat{\Sigma}\hat{V}^T) (\hat{V}\hat{\Sigma}^{-1}\hat{U}^T) (\hat{U}\hat{\Sigma}\hat{V}^T) \\ &= \hat{U}\hat{\Sigma} (\hat{V}^T\hat{V}) \hat{\Sigma}^{-1} (\hat{U}^T\hat{U}) \hat{\Sigma}\hat{V}^T \end{aligned}$$

Since $\hat{V}^T\hat{V} = I_r$ and $\hat{U}^T\hat{U} = I_r$:

$$\begin{aligned} \hat{A}\hat{A}^+\hat{A} &= \hat{U}\hat{\Sigma} I_r \hat{\Sigma}^{-1} I_r \hat{\Sigma}\hat{V}^T \\ &= \hat{U} (\hat{\Sigma}\hat{\Sigma}^{-1}\hat{\Sigma}) \hat{V}^T \\ &= \hat{U}\hat{\Sigma}\hat{V}^T \\ &= \hat{A} \end{aligned}$$

Thus, $\hat{A}\hat{A}^+\hat{A} = \hat{A}$ is proven.

(3)

$P = XX^T$ とおくと、$X^TX = I_r$ であるため $P$ は階数 $r$ の直交射影行列である。 目標は $\|A - PA\|^2$ を最小化することである。$PA$ は行列 $A$ の列空間を $X$ が張る $r$ 次元部分空間に射影したものであり、$\text{rank}(PA) \le r$ である。

エッカート・ヤング・ミルスキーの定理（Eckart-Young-Mirsky Theorem）より、$\text{rank}(Y) \le r$ を満たす行列 $Y$ の中で $\|A - Y\|^2$ を最小化するものは $Y = \hat{A} = \hat{U}\hat{\Sigma}\hat{V}^T$ である。 したがって、$XX^TA = \hat{A}$ を満たす $X$ を見つければよい。

行列 $A = U\Sigma V^T$ に対して $\hat{U}\hat{U}^T A$ を計算すると、

$$\hat{U}\hat{U}^T A = \hat{U}\hat{U}^T (\hat{U}\hat{\Sigma}\hat{V}^T + \tilde{U}\tilde{\Sigma}\tilde{V}^T) = \hat{U}\hat{\Sigma}\hat{V}^T = \hat{A}$$

となる（$\tilde{U}$ は $U$ の $r+1$ から $n$ 列目）。 よって、$X$ の列ベクトルが $\hat{U}$ の列ベクトルと同じ空間を張ればよい。 解は、任意の直交行列 $Q \in \mathbb{R}^{r \times r}$（$Q^TQ = I_r$）を用いて以下のように表される。 解: $X = \hat{U}Q$ （最も基本的な解は $X = \hat{U}$）

English: Let $P = XX^T$. Since $X^TX = I_r$, $P$ is an orthogonal projection matrix of rank $r$. The objective is to minimize $\|A - PA\|^2$. $PA$ is the projection of the column space of $A$ onto the $r$-dimensional subspace spanned by $X$, ensuring $\text{rank}(PA) \le r$.

By the Eckart-Young-Mirsky Theorem, the matrix $Y$ that minimizes $\|A - Y\|^2$ subject to $\text{rank}(Y) \le r$ is $Y = \hat{A} = \hat{U}\hat{\Sigma}\hat{V}^T$. Thus, we need to find $X$ such that $XX^TA = \hat{A}$.

Calculating $\hat{U}\hat{U}^T A$ for $A = U\Sigma V^T$, we get:

$$\hat{U}\hat{U}^T A = \hat{U}\hat{U}^T (\hat{U}\hat{\Sigma}\hat{V}^T + \tilde{U}\tilde{\Sigma}\tilde{V}^T) = \hat{U}\hat{\Sigma}\hat{V}^T = \hat{A}$$

(where $\tilde{U}$ represents columns $r+1$ to $n$ of $U$). Therefore, the column space of $X$ must span the same space as the columns of $\hat{U}$. The solution, using any orthogonal matrix $Q \in \mathbb{R}^{r \times r}$ ($Q^TQ = I_r$), is expressed as: Solution: $X = \hat{U}Q$ (The most basic solution is $X = \hat{U}$)

(4)

$AA^T = (U\Sigma V^T)(V\Sigma U^T) = U\Sigma^2 U^T$ であり、これは固有値 $\sigma_1^2 \ge \sigma_2^2 \ge \dots \ge \sigma_n^2$ を持つ対称行列である。 最適化問題は $\max_X \text{trace}(X^T AA^T X)$ subject to $X^TX = I_r$ となる。

Ky Fanの定理（またはRayleigh-Ritzの定理の拡張）より、正規直交系を列に持つ行列 $X$ に対する $\text{trace}(X^T M X)$ の最大値は、対称行列 $M$ の上位 $r$ 個の固有値の和（この場合は $\sum_{i=1}^r \sigma_i^2$）に等しい。 この最大値は、$X$ の列ベクトルが $M$ の上位 $r$ 個の固有値に対応する固有空間（主部分空間）を張るときに達成される。

$AA^T$ の上位 $r$ 個の固有値に対応する固有ベクトルは、行列 $U$ の最初の $r$ 列、すなわち $\hat{U}$ である。 したがって、$X$ は $\hat{U}$ と同じ空間を張る正規直交行列であればよい。 解: $X = \hat{U}Q$ （$Q \in \mathbb{R}^{r \times r}$ は任意の直交行列）

English: $AA^T = (U\Sigma V^T)(V\Sigma U^T) = U\Sigma^2 U^T$, which is a symmetric matrix with eigenvalues $\sigma_1^2 \ge \sigma_2^2 \ge \dots \ge \sigma_n^2$. The optimization problem is $\max_X \text{trace}(X^T AA^T X)$ subject to $X^TX = I_r$.

By Ky Fan's Theorem (or the extended Rayleigh-Ritz theorem), the maximum of $\text{trace}(X^T M X)$ for an orthonormal matrix $X$ is the sum of the $r$ largest eigenvalues of the symmetric matrix $M$ (in this case, $\sum_{i=1}^r \sigma_i^2$). This maximum is achieved when the column vectors of $X$ span the eigenspace (principal subspace) corresponding to the $r$ largest eigenvalues of $M$.

The eigenvectors corresponding to the $r$ largest eigenvalues of $AA^T$ are the first $r$ columns of $U$, which is $\hat{U}$. Therefore, $X$ must be an orthonormal matrix spanning the same space as $\hat{U}$. Solution: $X = \hat{U}Q$ (where $Q \in \mathbb{R}^{r \times r}$ is an arbitrary orthogonal matrix)

(5)

正則行列 $A$ が $A = BC$ と表されるため、$B \in \mathbb{R}^{n \times n}$ および $C \in \mathbb{R}^{n \times n}$ も正則行列（逆行列を持つ）である。 最適化する目的関数は $\|A - BXC\|^2$ である。

$Y = BXC$ と定義する。$B, C$ が正則であるため、任意の行列 $X$ に対して $\text{rank}(Y) = \text{rank}(X)$ が成り立つ。 したがって、条件 $\text{rank}(X) = r$ は $\text{rank}(Y) = r$ と同値になる。 問題は以下のように書き換えられる。

$$\min_Y \|A - Y\|^2 \quad \text{subject to} \quad \text{rank}(Y) = r$$

エッカート・ヤング・ミルスキーの定理より、この最適化問題の解は $Y = \hat{A}$ である。 元の変数 $X$ に戻すと、$BXC = \hat{A}$ を満たす $X$ が求める解となる。 $B, C$ は正則であるため、両辺に左から $B^{-1}$、右から $C^{-1}$ を掛ける。 解: $X = B^{-1}\hat{A}C^{-1}$

English: Since the regular (invertible) matrix $A$ is written as $A = BC$, the matrices $B \in \mathbb{R}^{n \times n}$ and $C \in \mathbb{R}^{n \times n}$ must also be regular (invertible). The objective function to be optimized is $\|A - BXC\|^2$.

Let $Y = BXC$. Because $B$ and $C$ are invertible, $\text{rank}(Y) = \text{rank}(X)$ holds for any matrix $X$. Therefore, the condition $\text{rank}(X) = r$ is completely equivalent to $\text{rank}(Y) = r$. The problem can be rewritten as:

$$\min_Y \|A - Y\|^2 \quad \text{subject to} \quad \text{rank}(Y) = r$$

By the Eckart-Young-Mirsky Theorem, the solution to this optimization problem is $Y = \hat{A}$. Reverting to the original variable $X$, the desired solution satisfies $BXC = \hat{A}$. Since $B$ and $C$ are invertible, we multiply by $B^{-1}$ on the left and $C^{-1}$ on the right. Solution: $X = B^{-1}\hat{A}C^{-1}$