特異値分解のステップ

特異値分解の復習。
特異値分解は、m×n行列Aに対して、下記のように分解する。
$A=U\sum V^T$
・A:m×n
・U:m×nの直行行列
・Σ：m×n
・ $V^T$ ：n×nの直行行列
単位ベクトル（左特異ベクトル） $\vec u$ 、Ａの特異値σ、単位ベクトル（右特異ベクトル) $\vec v$ を用いると、下記のようにあらわせる。
$A=(\vec u_1 \vec u_2 ...)\begin{bmatrix}σ_1 & 0 ... \\ 0 & σ_2 & ... \\ ... & 0 & .. \end{bmatrix} ( \vec v_1 \vec v_2 ..)^T$

Aを分解するために必要な情報は $U, Σ, V^T$ の3つである。これは、 $AA^T$ および $A^TA$ をそれぞれ固有分解することで求められる。

1. Vを求める

$A^TA=VΣ^TU^TUΣV^T$
Uは直行行列なので、 $U^T=U^{-1}$ となり、打ち消せる。
$A^TA=VΣ^TΣV^T$
これは、固有値分解の公式 $A=VΛV^{-1}$ で、Aが $A^TA$ に、Λが $Σ^TΣ$ に変わったものとみなすことが出来るので、固有方程式から以下が成立する。
$|A^TA-λE|=0$
これを解いて、 $λ=λ_1,λ_2$ を得る。
Σの特異値を $σ_1, σ_2$ とすると、
$Σ^TΣ=\begin{bmatrix} σ_1& 0 &0 \\ 0 & σ_2 & 0\end{bmatrix}\begin{bmatrix} σ_1& 0 \\0 & σ_2\\ 0 & 0\end{bmatrix}=\begin{bmatrix} σ_1^2 & 0 \\ 0 & σ_2^2\end{bmatrix}=\begin{bmatrix} λ_1 & 0 \\ 0 & λ_2 \end{bmatrix}$
となるので、 $σ=\sqrt λ$ が成立する。
よって、Aの特異値は、 $σ=\sqrt λ_1, \sqrt λ_2$
Aの右特異ベクトルVは、 $A^TA$ の固有ベクトルを単位ベクトルに変換すればよい。
$V=(v_1, v_2)$

2. U,∑を求める

右特異ベクトルは冒頭の定義式より
$A=U∑ZV^T$
より、Uは下記のようにあらわせる。
$U=AV/∑$ あるいは、 $U=AVΣ^{-1}$
よって、 $U=(\vec u_1, \vec u_2)$
$\vec u_1=\frac{1}{σ_1}A\vec v_1$
$\vec u_2=\frac{1}{σ_2}A\vec v_2$

3.計算例

例として、 $A= \begin{bmatrix}3 & 2 & 2 \\2 & 3 & -2 \end{bmatrix}$ を分解する。
$AA^T=\begin{bmatrix} 17& 8 \\ 8 & 17 \end{bmatrix}$
と計算できる。行列式は下記になる。
$det(AA^T- \lambda I)= \lambda^2-34\lambda +225=0$
よって、 $AA^T$ の固有値は下記になる。
$\lambda = 25,9$
ここで、 $A^TA$ の固有値は $\lambda = 25,9,0$ となるので、右特異ベクトルは、 $A^TA-λI$ を計算し、
$v_1=\begin{bmatrix} 1/\sqrt{2} \\ 1/\sqrt{2} \\ 0 \end{bmatrix}$
$v_2=\begin{bmatrix} 1/\sqrt{18} \\ -1/\sqrt{18} \\ 4/\sqrt{18} \end{bmatrix}$
$v_3$ に関しては、他の固有ベクトルと直交しているという条件から求める。
$v_1^Tv_3=0, v_2^Tv_3=0$
$||v_3||=1$
$v_3=\begin{bmatrix} 2/3 \\ -2/3 \\ -1/3 \end{bmatrix}$
すなわち、
$A=UΣV^T=U\begin{bmatrix} 5 & 0 & 0 \\ 0 & 3 & 0 \end{bmatrix}\begin{bmatrix} 1/\sqrt{2} & 1/\sqrt{2} & 0 \\ 1/\sqrt{18} & -1/\sqrt{18} & 4/\sqrt{18} \\ 2/3 & -2/3 & -1/3 \end{bmatrix}$
左特異ベクトルを求め、下記に分解できる。
$A=UΣV^T=\begin{bmatrix} 1/\sqrt{2} & 1/\sqrt{2} \\ 1/\sqrt{2} & -1/\sqrt{2} \end{bmatrix}\begin{bmatrix} 5 & 0 & 0 \\ 0 & 3 & 0 \end{bmatrix}\begin{bmatrix} 1/\sqrt{2} & 1/\sqrt{2} & 0 \\ 1/\sqrt{18} & -1/\sqrt{18} & 4/\sqrt{18} \\ 2/3 & -2/3 & -1/3 \end{bmatrix}$