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

Author

KardeniaPoyu

Description

以下で は 行 列实数値行列の集合を表すものとする。 正則行列 の特異値分解は以下で与えられる ()。

ここで、 は をみたし、 は対角行列でその対角成分は を満たす。ただし、 は行列 の転置を表し、 は単位行列である。

のランク 近似 を以下で定義する ()。

ここで、 は の最初の 列からなる行列であり、 である。 は以下の最適化问题の一つの解 を与えることが知られている。

ただし、 である。 以下の問いに導出も含めて答えよ。

(1) の特異値分解を求めよ。

(2) とするとき、 を示せ。

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

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

(5) を用いて と書けるとする。次の最適化問題の解を求めよ。

Kai

(1)

定義より、 であり、、 を満たす。

まず、 について計算する。

は対角行列であるため であり、 より、

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

同様に、 について計算する。

より、

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

English: By definition, , satisfying and .

First, we calculate :

Since is a diagonal matrix, . Using , we have:

This is the compact SVD (or eigenvalue decomposition) of . As a full SVD for an matrix using the orthogonal matrix , it is written as:

Similarly, calculating :

Using , we have:

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

(2)

および を左辺に代入して計算する。

および であるため、

以上より、 が示された。

English: Substitute and into the left side:

Since and :

Thus, is proven.

(3)

とおくと、 であるため は階数 の直交射影行列である。 目標は を最小化することである。 は行列 の列空間を が張る 次元部分空間に射影したものであり、 である。

エッカート・ヤング・ミルスキーの定理（Eckart-Young-Mirsky Theorem）より、 を満たす行列 の中で を最小化するものは である。 したがって、 を満たす を見つければよい。

行列 に対して を計算すると、

となる（ は の から 列目）。 よって、 の列ベクトルが の列ベクトルと同じ空間を張ればよい。 解は、任意の直交行列 （）を用いて以下のように表される。 解: （最も基本的な解は ）

English: Let . Since , is an orthogonal projection matrix of rank . The objective is to minimize . is the projection of the column space of onto the -dimensional subspace spanned by , ensuring .

By the Eckart-Young-Mirsky Theorem, the matrix that minimizes subject to is . Thus, we need to find such that .

Calculating for , we get:

(where represents columns to of ). Therefore, the column space of must span the same space as the columns of . The solution, using any orthogonal matrix (), is expressed as: Solution: (The most basic solution is )

(4)

であり、これは固有値 を持つ対称行列である。 最適化問題は subject to となる。

Ky Fanの定理（またはRayleigh-Ritzの定理の拡張）より、正規直交系を列に持つ行列 に対する の最大値は、対称行列 の上位 個の固有値の和（この場合は ）に等しい。 この最大値は、 の列ベクトルが の上位 個の固有値に対応する固有空間（主部分空間）を張るときに達成される。

の上位 個の固有値に対応する固有ベクトルは、行列 の最初の 列、すなわち である。 したがって、 は と同じ空間を張る正規直交行列であればよい。 解: （ は任意の直交行列）

English: , which is a symmetric matrix with eigenvalues . The optimization problem is subject to .

By Ky Fan's Theorem (or the extended Rayleigh-Ritz theorem), the maximum of for an orthonormal matrix is the sum of the largest eigenvalues of the symmetric matrix (in this case, ). This maximum is achieved when the column vectors of span the eigenspace (principal subspace) corresponding to the largest eigenvalues of .

The eigenvectors corresponding to the largest eigenvalues of are the first columns of , which is . Therefore, must be an orthonormal matrix spanning the same space as . Solution: (where is an arbitrary orthogonal matrix)

(5)

正則行列 が と表されるため、 および も正則行列（逆行列を持つ）である。 最適化する目的関数は である。

と定義する。 が正則であるため、任意の行列 に対して が成り立つ。 したがって、条件 は と同値になる。 問題は以下のように書き換えられる。

エッカート・ヤング・ミルスキーの定理より、この最適化問題の解は である。 元の変数 に戻すと、 を満たす が求める解となる。 は正則であるため、両辺に左から 、右から を掛ける。 解:

English: Since the regular (invertible) matrix is written as , the matrices and must also be regular (invertible). The objective function to be optimized is .

Let . Because and are invertible, holds for any matrix . Therefore, the condition is completely equivalent to . The problem can be rewritten as:

By the Eckart-Young-Mirsky Theorem, the solution to this optimization problem is . Reverting to the original variable , the desired solution satisfies . Since and are invertible, we multiply by on the left and on the right. Solution: