行列の特異値分解
概要
行列を常に固有値対角化を通じて分解できたらいいと思うが、残念ながら提供される行列が正方行列でなければならないという制限がある。非正方行列である行列の分解を拡張しようとする。
ビルドアップ
二つの自然数 $m > n$について、行列 $A \in \mathbb{C}^{ m \times n}$の係数が$\text{rank} A = n$で与えられるとする。それならば、$\dim C(A) = \dim C(A^{T}) = n $の正規直交ベクトル$\mathbb{v}_{1} , \cdots , \mathbb{v}_{n} \in C(A)$と$\mathbb{u}_{1} , \cdots , \mathbb{u}_{n} \in C(A^{T})$を考えることができる。
固有値の幾何学的意味を考えるときと同様に $$ A \mathbb{v}_{i} = \sigma_{i} \mathbb{u}_{i} $$ を満たす$\sigma_{i}>0$が存在すると仮定する。すると$A$は$\mathbb{v}_{i}$の方向を$\mathbb{u}_{i}$と一致させる線形変換であり、$\sigma_{i}>0$はその大きさを合わせるものと見ることができる。このような$\sigma_{i}$は固有値ではなく、$A$の特異値と定義されるが、残念ながらその意味は特異値分解とは全く関係がない。ここで固有値の議論と異なるのは$A \in \mathbb{C}^{ m \times n}$、つまり$\mathbb{v}_{i} \in \mathbb{C}^{n}$であり、$\mathbb{u}_{i} \in \mathbb{C}^{m}$であるため、$A$がベクトルの次元も変えるということである。行列$A$について整理して、$A = \sigma_{i} \mathbb{u}_{i} \mathbb{v}_{i}^{\ast}$であり、両辺の次元が$m \times n = ( m \times 1 ) \times (1 \times n )$になることを確認してみよう。一方、固有ベクトルとは異なり、左右が区別されるため、$\mathbb{u}_{i}$は左特異ベクトル、$\mathbb{v}_{i}$は右特異ベクトルと定義されることに注意しよう。今$A \mathbb{v}_{i} = \sigma_{i} \mathbb{u}_{i}$を$1 \le i \le n$に対して展開して書くと $$ A \begin{bmatrix} \mathbb{v}_{1} & \mathbb{v}_{2} & \cdots & \mathbb{v}_{n} \end{bmatrix} = \begin{bmatrix} \mathbb{u}_{1} & \mathbb{u}_{2} & \cdots & \mathbb{u}_{n} \end{bmatrix} \begin{bmatrix} \sigma_{1} & 0 & \cdots & 0 \\ 0 & \sigma_2 & \ddots & \vdots \\ \vdots & \ddots & \ddots & 0 \\ 0 & \cdots & 0 & \sigma_{m} \end{bmatrix} $$ 簡潔に表現するため、以下のように表すことにしよう。 $$ V := \begin{bmatrix} \mathbb{v}_{1} & \mathbb{v}_{2} & \cdots & \mathbb{v}_{n} \end{bmatrix} \in \mathbb{C}^{n \times n} \\ \widehat{U} := \begin{bmatrix} \mathbb{u}_{1} & \mathbb{u}_{2} & \cdots & \mathbb{u}_{n} \end{bmatrix} \in \mathbb{C}^{m \times n} \\ \widehat{\Sigma} := \text{diag} ( \sigma_1 , \sigma_2 , \cdots , \sigma_n) $$ 便宜上、$\sigma_{i} \ge \sigma_{j} > 0$としよう。整理すると $$ AV = \widehat{U} \widehat{\Sigma} $$ であり、$V V^{\ast} = V^{\ast} V = I$であるため $$ A = \widehat{U} \widehat{\Sigma} V^{\ast} $$ もちろん$\widehat{U} \in \ \mathbb{C}^{m \times n}$であり、$\widehat{U}$がユニタリ行列ではないが、正規直交性を持つため、$\widehat{U}^{\ast} \widehat{U} = I_{n}$であり、 $$ \begin{align*} A^{\ast}A =& (\widehat{U} \widehat{\Sigma} V^{\ast})^{\ast} (\widehat{U} \widehat{\Sigma} V^{\ast}) \\ =& V \widehat{\Sigma} \widehat{U}^{\ast} \widehat{U} \widehat{\Sigma} V^{\ast} \\ =& V \widehat{\Sigma}^{2} V^{\ast} \\ =& V \widehat{\Sigma}^{2} V^{-1} \end{align*} $$
$$ A = S \begin{bmatrix} \lambda_{1} & 0 & \cdots & 0 \\ 0 & \lambda_2 & \ddots & \vdots \\ \vdots & \ddots & \ddots & 0 \\ 0 & \cdots & 0 & \lambda_{m} \end{bmatrix} S^{-1} $$
これは正方行列 $A^{\ast} A \in \mathbb{C}^{m \times m}$に対して固有値対角化を完了した結果と見ることができる。$\sigma^{2}_{i}$は$A^{\ast}A$の固有値であり、$\mathbb{v}_{i}$が$\sigma^{2}_{i}$に対応する固有ベクトルになる。これで数値計算のために、このプロセスを逆にたどってみよう。
アルゴリズム
行列 $A \in \mathbb{C}^{m \times n} (m \ge n)$について、$\text{rank} A = n$であるとする。
ステップ 1.
$A^{\ast} A$の固有値$\sigma_{1} \ge \sigma_{2} \ge \cdots \ge \sigma_{n}>0$を見つける。任意の$\mathbb{x} \ne \mathbb{0}$に対して $$ \mathbb{x}^{\ast} A^{\ast} A \mathbb{x} = || A \mathbb{x} ||^2 > 0 $$ つまり$A^{\ast} A$が正定値であるため、$\sigma_{i} >0$が保証される。
ステップ 2.
見つかった固有値に対応する固有ベクトルとして正規直交ベクトル$V = \begin{bmatrix} v_{1} & v_{2} & \cdots & v_{n} \end{bmatrix}$を見つける。
ステップ 3.
$\displaystyle \mathbb{u}_{i} = {{1} \over { \sigma_{i} }} A \mathbb{v}_{i}$を通じて$\widehat{U} = \begin{bmatrix} u_{1} & u_{2} & \cdots & u_{n} \end{bmatrix}$を見つける。
縮小特異値分解と全特異値分解
$A = \widehat{U} \widehat{\Sigma} V^{\ast}$を満たす3つの行列に$A$を分割することを縮小reduced特異値分解(rSVD)と呼ぶ。
これを全体full特異値分解(fSVD)と区別するために、$\widehat{U}$や$\widehat{\Sigma}$のような表記が使われた。全特異値分解のアイデアは、単に縮小特異値分解を少し拡張したものに過ぎない。行列 $$ U := \begin{bmatrix} \widehat{U} & \mathbb{u}_{n+1} & \cdots & \mathbb{u}_{m} \end{bmatrix} \in \mathbb{C}^{m \times m} $$ がユニタリ行列になるような$\mathbb{u}_{n+1} , \cdots , \mathbb{u}_{m}$を見つけて、$\widehat{\Sigma}$の下部に$0$を追加する形で行列$\Sigma := \begin{bmatrix} \widehat{\Sigma} \\ O \end{bmatrix}$ を構成し、$A = U \Sigma V^{\ast}$の形で分解することである。
fSVDは理論的により堅牢であり、rSVDは実際の計算により有利であるだろう。fSVDであれrSVDであれ、SVDを行うということは、$U$または$\widehat{U}$、$\Sigma$または$\widehat{\Sigma}$、$V$を求めるということだ。