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

标签：

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

Author

KardeniaPoyu, 祭音Myyura

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$$

题目描述

记 $\mathbb R^{n\times m}$ 为 $n$ 行 $m$ 列实矩阵集合。对 $n\ge2$ 的可逆矩阵 $A\in\mathbb R^{n\times n}$，给定奇异值分解

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

其中 $U,V$ 为正交矩阵，

$$U^TU=V^TV=I_n,$$

且

$$\Sigma=\operatorname{diag}(\sigma_1,\ldots,\sigma_n), \qquad \sigma_1\ge\cdots\ge\sigma_n>0.$$

对 $1\le r<n$，取 $U,V$ 的前 $r$ 列组成 $\hat U,\hat V$，并令

$$\hat\Sigma=\operatorname{diag}(\sigma_1,\ldots,\sigma_r), \qquad \hat A=\hat U\hat\Sigma\hat V^T.$$

已知 $\hat A$ 是秩恰为 $r$ 的最佳 Frobenius 范数近似之一：

$$\min_{\substack{X\in\mathbb R^{n\times n}\\\operatorname{rank}(X)=r}} \|A-X\|^2, \qquad \|M\|^2=\operatorname{trace}(M^TM)=\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_{\substack{X\in\mathbb R^{n\times r}\\X^TX=I_r}} \|A-XX^TA\|^2$$

   的解。

4. 求优化问题

   $$\max_{\substack{X\in\mathbb R^{n\times r}\\X^TX=I_r}} \operatorname{trace}(X^TAA^TX)$$

   的解。

5. 若 $B,C\in\mathbb R^{n\times n}$ 且 $A=BC$，求

   $$\min_{\substack{X\in\mathbb R^{n\times n}\\\operatorname{rank}(X)=r}} \|BC-BXC\|^2$$

   的解。

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)

$A = U\Sigma V^T$ であり、$\hat{U}$、$\hat{V}$ はそれぞれ $U$、$V$ の最初の $r$ 列からなる行列である。まず $A\hat{V}$ と $\hat{U}^T A$ を計算する。

$V^TV = I_n$ より $V^T\hat{V} = \begin{pmatrix} I_r \\ O \end{pmatrix} \in \mathbb{R}^{n \times r}$ であるから、

$$A\hat{V} = U\Sigma V^T\hat{V} = U\Sigma \begin{pmatrix} I_r \\ O \end{pmatrix} = U \begin{pmatrix} \hat{\Sigma} \\ O \end{pmatrix} = \hat{U}\hat{\Sigma}$$

同様に $U^TU = I_n$ より $\hat{U}^TU = \begin{pmatrix} I_r & O \end{pmatrix} \in \mathbb{R}^{r \times n}$ であるから、

$$\hat{U}^TA = \hat{U}^TU\Sigma V^T = \begin{pmatrix} I_r & O \end{pmatrix}\Sigma V^T = \begin{pmatrix} \hat{\Sigma} & O \end{pmatrix} V^T = \hat{\Sigma}\hat{V}^T$$

これらを用いると、

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

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

English: We have $A = U\Sigma V^T$, where $\hat{U}$ and $\hat{V}$ consist of the first $r$ columns of $U$ and $V$ respectively. We first compute $A\hat{V}$ and $\hat{U}^T A$.

Since $V^TV = I_n$, we have $V^T\hat{V} = \begin{pmatrix} I_r \\ O \end{pmatrix} \in \mathbb{R}^{n \times r}$, hence

$$A\hat{V} = U\Sigma V^T\hat{V} = U\Sigma \begin{pmatrix} I_r \\ O \end{pmatrix} = U \begin{pmatrix} \hat{\Sigma} \\ O \end{pmatrix} = \hat{U}\hat{\Sigma}$$

Similarly, $U^TU = I_n$ gives $\hat{U}^TU = \begin{pmatrix} I_r & O \end{pmatrix} \in \mathbb{R}^{r \times n}$, hence

$$\hat{U}^TA = \hat{U}^TU\Sigma V^T = \begin{pmatrix} I_r & O \end{pmatrix}\Sigma V^T = \begin{pmatrix} \hat{\Sigma} & O \end{pmatrix} V^T = \hat{\Sigma}\hat{V}^T$$

Using these,

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

Thus, $A\hat{A}^+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 UQ$（$Q^TQ=I_r$）は解である。$\sigma_r>\sigma_{r+1}$ ならこれが全解である。$\sigma_r=\sigma_{r+1}$ の場合は、$\sigma_r$ より大きい特異値の左特異ベクトルを全て含み、$\sigma_r$ の左特異空間から残りの次元を任意に選んだ $r$ 次元部分空間の正規直交基も解となる。

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$). Thus $X=\hat UQ$, where $Q^TQ=I_r$, is a solution. If $\sigma_r>\sigma_{r+1}$, these are all solutions. If $\sigma_r=\sigma_{r+1}$, any orthonormal basis of an $r$-dimensional subspace containing all left singular spaces with singular value greater than $\sigma_r$ and choosing the remaining dimensions inside the $\sigma_r$ singular space is also optimal.

(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 UQ$（$Q$ は任意の直交行列）は解であり、最大値は $\sum_{i=1}^r\sigma_i^2$ である。$\sigma_r>\sigma_{r+1}$ ならこれが全解であり、境界で重複する場合の全解は (3) と同じ主部分空間の任意性を持つ。

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=\hat UQ$, with arbitrary orthogonal $Q$, is optimal and the maximum is $\sum_{i=1}^r\sigma_i^2$. If $\sigma_r>\sigma_{r+1}$ these are all solutions; with a tie at the boundary, the full solution set has the same freedom inside the tied principal subspace as in (3).

(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, one 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}$