特異値分解

特異値分解（Singular Value Decomposition, SVD）はとても役に立つ行列の分解法である．

しかし線形代数の講義などでは扱われることが少なく，とても残念なことである．

行列$A$：$(m \times n)$は，$A = UWV^T$の形に分解できる．これを特異値分解という．

ここで， $U$：$(m \times r)$，$V$：$(n \times r)$，$U$，$V$は列直交行列， $r$は行列$A$のランク．

また， $ W = \mathrm{diag}(\sigma_1,\sigma_2,\cdots,\sigma_r) \; (\sigma_1 \ge \sigma_2 \ge \cdots \ge \sigma_r \gt 0) $ であり，この$\sigma_i$を特異値と呼ぶ．

$U$が列直交行列とは，$U=(\boldsymbol{e}_1,\boldsymbol{e}_2,\cdots,\boldsymbol{e}_r)$としたとき， $$ \boldsymbol{e}_i \cdot \boldsymbol{e}_j = \left\{ \begin{array}{c} 1 \; (i=j) \\ 0 \; (i \ne j) \end{array} \right. $$ つまり，$U^TU = I$，$I$は$r\times r$の単位行列．また同様に$V^TV=I$である．

$A$が正則な場合，つまり$m=n=r$の場合，$A$の逆行列は特異値分解を使って以下のように表せる． $$ A^{-1} = VW^{-1}U^T,\;\; W^{-1}=\mathrm{diag}(1/\sigma_1,1/\sigma_2,\cdots,1/\sigma_r) $$ $A^{-1}A$を計算してみると $$ A^{-1}A=VW^{-1}U^TUWV^T = VW^{-1}WV^T = VV^T=I $$ となることが確認できる ¹⁾.

$m = n = r$でない場合，$A$の擬似逆行列は逆行列と形式的に同じで以下のように表せる． $$ A^{+} = VW^{-1}U^T,\;\; W^{-1}=\mathrm{diag}(1/\sigma_1,1/\sigma_2,\cdots,1/\sigma_r) $$ $AA^{+}A$を計算してみると $$ AA^{+}A=UWV^TVW^{-1}U^TUWV^T = UWW^{-1}WV^T = UWV^T=A $$ となり擬似逆行列の条件を満たしていることが確認できる．

$m>n$の場合の擬似逆行列の求め方として以下がよく見受けられる． $$ A^+ = (A^TA)^{-1}A^T $$ これもまた以下を満たし擬似逆行列であることが分かる． $$ AA^+A = A(A^TA)^{-1}A^TA = A $$ しかしこの求め方の問題点は，

• $A^TA$が正則とは限らない．つまり$(A^TA)^{-1}$が求められないことがある
• また正則であったとしても”きわどい”場合がある

ということである．

特異値分解を使うと，特異値を吟味することで問題 を明らかにし，それを回避することができる．

ということで，擬似逆行列の計算には特異値分解を利用する方が良い．

線形連立方程式を擬似逆行列を用いて得ということがどういう意味を持っているのかを 特異値分解をベースに考えてみる．

以下の線形連立方程式を考える． $$ \boldsymbol{b}=A\boldsymbol{x} \tag{1} $$ $\boldsymbol{b}$は$m$次元ベクトル，$\boldsymbol{x}$は$n$次元ベクトル， $A$は$m \times n$の行列でそのランクは$r$とする．

$m=m=r$の場合，これは簡単に， $$ \boldsymbol{x} = A^{-1}\boldsymbol{x} $$ と解くことができる．

その他の場合は， $$ \boldsymbol{x} = A^{+}\boldsymbol{b} \tag{2} $$ と解くことができ，以下のように場合分けされる．

• $m \gt n \ge r$の場合，条件が過剰であり，最小二乗解を得る．
• $n \gt m \ge r$の場合，条件が不足しいる冗長自由度問題であり，条件を満たす最小ノルム解を得る．またそれは最小二乗解にもなっている．

式(1)を$A$の特異値分解を使って表すと， $$ \boldsymbol{b} = UWV^T \boldsymbol{x} $$ この両辺に$U^T$をかけると， $$ U^T\boldsymbol{b} = WV^T \boldsymbol{x} $$ $U$，$V$を直交補空間の基底ベクトルを加えてそれぞれ$m \times m$，$n \times n$に拡大すると， $$ \left( \begin{array}{c} U^T \\ U^\perp \end{array} \right)\boldsymbol{b} = \left( \begin{array}{cc} W & 0 \\ 0 & 0 \end{array} \right) \left( \begin{array}{c} V^T \\ V^{\perp} \end{array} \right)\boldsymbol{x} $$ このとき $$ \left( \begin{array}{c}\boldsymbol{b}' \\ \boldsymbol{b}^\perp \end{array} \right) = \left( \begin{array}{c} U^T \\ U^\perp \end{array} \right)\boldsymbol{b} $$ $$ \left( \begin{array}{c}\boldsymbol{x}' \\ \boldsymbol{x}^\perp \end{array} \right) = \left( \begin{array}{c} V^T \\ V^{\perp} \end{array} \right)\boldsymbol{x} $$ とすると，それぞれ直交行列をかけているので，大きさ（ノルム）は変わらない．

これを用いて以下のように書き直して眺めてみる． $$ \left( \begin{array}{c}\boldsymbol{b}' \\ \boldsymbol{b}^\perp \end{array} \right) = \left( \begin{array}{cc} W & 0 \\ 0 & 0 \end{array} \right) \left( \begin{array}{c}\boldsymbol{x}' \\ \boldsymbol{x}^\perp \end{array} \right) $$

• $\boldsymbol{x}$の一部$\boldsymbol{x}'$（$r$次元）が$\boldsymbol{b}$の一部$\boldsymbol{b}'$（同じく$r$次元）にしか影響を与えない
  • $\boldsymbol{x}^\perp$をいくら変更しても$\boldsymbol{b}$は変わらない
  • $\boldsymbol{x}$をどう変更しても$\boldsymbol{b}^\perp$は$0$意外は満たせない．
• 互いに影響を与える部分（$r$次元の部分）に関しては，軸方向に特異値$\sigma_i$倍に伸縮した関係になっている

これを擬似逆行列をつかって式(2)のようにとくということは， $$ \boldsymbol{x}'=V^T\boldsymbol{x}=W^{-1}U^T\boldsymbol{b}=W^{-1}\boldsymbol{b}' $$ つまり $$ \left( \begin{array}{c}\boldsymbol{x}' \\ \boldsymbol{0} \end{array} \right) = \left( \begin{array}{cc} W^{-1} & 0 \\ 0 & 0 \end{array} \right) \left( \begin{array}{c}\boldsymbol{b}' \\ \boldsymbol{0} \end{array} \right) $$ ここで$\boldsymbol{b}$の残差を考えると，直交行列による変換はノルムを変化させないので， $$ \| \boldsymbol{b}-A\boldsymbol{x} \| = \| \left( \begin{array}{c}\boldsymbol{0} \\ \boldsymbol{b}^\perp \end{array} \right) \| $$ $\boldsymbol{b}$の内どうやっても$\boldsymbol{x}$で消すことができない成分だけ残っている． つまり「最小二乗」になっている．

また$\boldsymbol{x}$に関しても， $$ \| \boldsymbol{x} \| = \| \left( \begin{array}{c}\boldsymbol{x}' \\ \boldsymbol{0} \end{array} \right) \| $$ つまり$\boldsymbol{b}$に対して最小二乗解を与えるもののうち最小の$\boldsymbol{x}$となっていることが確認できる．