logo

行列の特異値分解 📂行列代数

行列の特異値分解

概要

行列を常に固有値対角化を通じて分解できたらいいと思うが、残念ながら提供される行列が正方行列でなければならないという制限がある。非正方行列である行列の分解を拡張しようとする。

ビルドアップ

二つの自然数 m>nm > nについて、行列 A∈Cm×nA \in \mathbb{C}^{ m \times n}の係数がrankA=n\text{rank} A = nで与えられるとする。それならば、dim⁡C(A)=dim⁡C(AT)=n\dim C(A) = \dim C(A^{T}) = n の正規直交ベクトルv1,⋯ ,vn∈C(A)\mathbf{v}_{1} , \cdots , \mathbf{v}_{n} \in C(A)とu1,⋯ ,un∈C(AT)\mathbf{u}_{1} , \cdots , \mathbf{u}_{n} \in C(A^{T})を考えることができる。

固有値の幾何学的意味を考えるときと同様に Avi=σiui A \mathbf{v}_{i} = \sigma_{i} \mathbf{u}_{i} を満たすσi>0\sigma_{i}>0が存在すると仮定する。するとAAはvi\mathbf{v}_{i}の方向をui\mathbf{u}_{i}と一致させる線形変換であり、σi>0\sigma_{i}>0はその大きさを合わせるものと見ることができる。このようなσi\sigma_{i}は固有値ではなく、AAの特異値と定義されるが、残念ながらその意味は特異値分解とは全く関係がない。ここで固有値の議論と異なるのはA∈Cm×nA \in \mathbb{C}^{ m \times n}、つまりvi∈Cn\mathbf{v}_{i} \in \mathbb{C}^{n}であり、ui∈Cm\mathbf{u}_{i} \in \mathbb{C}^{m}であるため、AAがベクトルの次元も変えるということである。行列AAについて整理して、A=σiuivi∗A = \sigma_{i} \mathbf{u}_{i} \mathbf{v}_{i}^{\ast}であり、両辺の次元がm×n=(m×1)×(1×n)m \times n = ( m \times 1 ) \times (1 \times n )になることを確認してみよう。一方、固有ベクトルとは異なり、左右が区別されるため、ui\mathbf{u}_{i}は左特異ベクトル、vi\mathbf{v}_{i}は右特異ベクトルと定義されることに注意しよう。今Avi=σiuiA \mathbf{v}_{i} = \sigma_{i} \mathbf{u}_{i}を1≤i≤n1 \le i \le nに対して展開して書くと A[v1v2⋯vn]=[u1u2⋯un][σ10⋯00σ2⋱⋮⋮⋱⋱00⋯0σm] A \begin{bmatrix} \mathbf{v}_{1} & \mathbf{v}_{2} & \cdots & \mathbf{v}_{n} \end{bmatrix} = \begin{bmatrix} \mathbf{u}_{1} & \mathbf{u}_{2} & \cdots & \mathbf{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:=[v1v2⋯vn]∈Cn×nU^:=[u1u2⋯un]∈Cm×nΣ^:=diag(σ1,σ2,⋯ ,σn) V := \begin{bmatrix} \mathbf{v}_{1} & \mathbf{v}_{2} & \cdots & \mathbf{v}_{n} \end{bmatrix} \in \mathbb{C}^{n \times n} \\ \widehat{U} := \begin{bmatrix} \mathbf{u}_{1} & \mathbf{u}_{2} & \cdots & \mathbf{u}_{n} \end{bmatrix} \in \mathbb{C}^{m \times n} \\ \widehat{\Sigma} := \text{diag} ( \sigma_1 , \sigma_2 , \cdots , \sigma_n) 便宜上、σi≥σj>0\sigma_{i} \ge \sigma_{j} > 0としよう。整理すると AV=U^Σ^ AV = \widehat{U} \widehat{\Sigma} であり、VV∗=V∗V=IV V^{\ast} = V^{\ast} V = Iであるため A=U^Σ^V∗ A = \widehat{U} \widehat{\Sigma} V^{\ast} もちろんU^∈ Cm×n\widehat{U} \in \ \mathbb{C}^{m \times n}であり、U^\widehat{U}がユニタリ行列ではないが、正規直交性を持つため、U^∗U^=In\widehat{U}^{\ast} \widehat{U} = I_{n}であり、 A∗A=(U^Σ^V∗)∗(U^Σ^V∗)=VΣ^U^∗U^Σ^V∗=VΣ^2V∗=VΣ^2V−1 \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[λ10⋯00λ2⋱⋮⋮⋱⋱00⋯0λm]S−1 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∗A∈Cm×mA^{\ast} A \in \mathbb{C}^{m \times m}に対して固有値対角化を完了した結果と見ることができる。σi2\sigma^{2}_{i}はA∗AA^{\ast}Aの固有値であり、vi\mathbf{v}_{i}がσi2\sigma^{2}_{i}に対応する固有ベクトルになる。これで数値計算のために、このプロセスを逆にたどってみよう。

アルゴリズム

行列 A∈Cm×n(m≥n)A \in \mathbb{C}^{m \times n} (m \ge n)について、rankA=n\text{rank} A = nであるとする。

ステップ 1.

A∗AA^{\ast} Aの固有値σ1≥σ2≥⋯≥σn>0\sigma_{1} \ge \sigma_{2} \ge \cdots \ge \sigma_{n}>0を見つける。任意のx≠0\mathbf{x} \ne \mathbb{0}に対して x∗A∗Ax=∣∣Ax∣∣2>0 \mathbf{x}^{\ast} A^{\ast} A \mathbf{x} = || A \mathbf{x} ||^2 > 0 つまりA∗AA^{\ast} Aが正定値であるため、σi>0\sigma_{i} >0が保証される。

ステップ 2.

見つかった固有値に対応する固有ベクトルとして正規直交ベクトルV=[v1v2⋯vn]V = \begin{bmatrix} v_{1} & v_{2} & \cdots & v_{n} \end{bmatrix}を見つける。

ステップ 3.

ui=1σiAvi\displaystyle \mathbf{u}_{i} = {{1} \over { \sigma_{i} }} A \mathbf{v}_{i}を通じてU^=[u1u2⋯un]\widehat{U} = \begin{bmatrix} u_{1} & u_{2} & \cdots & u_{n} \end{bmatrix}を見つける。

縮小特異値分解と全特異値分解

A=U^Σ^V∗A = \widehat{U} \widehat{\Sigma} V^{\ast}を満たす3つの行列にAAを分割することを縮小reduced特異値分解(rSVD)と呼ぶ。

これを全体full特異値分解(fSVD)と区別するために、U^\widehat{U}やΣ^\widehat{\Sigma}のような表記が使われた。全特異値分解のアイデアは、単に縮小特異値分解を少し拡張したものに過ぎない。行列 U:=[U^un+1⋯um]∈Cm×m U := \begin{bmatrix} \widehat{U} & \mathbf{u}_{n+1} & \cdots & \mathbf{u}_{m} \end{bmatrix} \in \mathbb{C}^{m \times m} がユニタリ行列になるようなun+1,⋯ ,um\mathbf{u}_{n+1} , \cdots , \mathbf{u}_{m}を見つけて、Σ^\widehat{\Sigma}の下部に00を追加する形で行列Σ:=[Σ^O]\Sigma := \begin{bmatrix} \widehat{\Sigma} \\ O \end{bmatrix} を構成し、A=UΣV∗A = U \Sigma V^{\ast}の形で分解することである。

fSVDは理論的により堅牢であり、rSVDは実際の計算により有利であるだろう。fSVDであれrSVDであれ、SVDを行うということは、UUまたはU^\widehat{U}、Σ\SigmaまたはΣ^\widehat{\Sigma}、VVを求めるということだ。

参照