特異値分解ってなんだっけ？

基本

$X\boldsymbol{X}$ を $m×nm \times n$ の実行列とする（$X∈Rm×n\boldsymbol{X} \in \mathbb{R}^{m\times n}$）。

$X\boldsymbol{X}$ の rank を $rr$とおく（$rankX=r≤min⁡(m,n){\rm rank} \boldsymbol{X} = r \le \min(m, n)$）。

このとき、直交行列 $U∈Rm×m, V∈Rn×nU \in \mathbb{R}^{m\times m}, \, V \in \mathbb{R}^{n\times n}$ と対角行列 $Σ∈Rm×n\Sigma \in \mathbb{R}^{m\times n}$を用いて、以下のように表すことができる：

$$X=UΣV⊤ \boldsymbol{X} = U \Sigma V^\top$$

これを、行列 $X\boldsymbol{X}$ の特異値分解 (Singular Value Decomposition, SVD) と呼ぶ。

ただし、$Σ\Sigma$ の$min⁡(m,n)\min(m, n)$ 個の対角成分のうち $rr$ 個は正の値で残りは0である。

以下では、

$$Σ=(Σ~000),Σ~=diag(λ1,λ2,...,λr) \Sigma = \begin{pmatrix} \tilde{\Sigma} & \boldsymbol{0}\\ \boldsymbol{0} & \boldsymbol{0} \end{pmatrix}, \quad \tilde{\Sigma} = {\rm diag}\left(\sqrt{\lambda_1}, \sqrt{\lambda_2}, ..., \sqrt{\lambda_r} \right)$$

$$λ1≥λ2≥...≥λr>0 \lambda_1 \ge \lambda_2 \ge ... \ge \lambda_r >0$$

とする。

$U,V,ΣU, V, \Sigma$ の関係

$mm$次元ベクトル $ui∈Rm\boldsymbol{u}_i \in \mathbb{R}^m$ と $nn$次元ベクトル $vi∈Rn\boldsymbol{v}_i \in \mathbb{R}^n$ を用いて、直交行列$U,VU, V$を以下のように表す：

$$U=(u1,u2,...,um)V=(v1,v2,...,vn). \begin{aligned} U &= (\boldsymbol{u}_1, \boldsymbol{u}_2, ..., \boldsymbol{u}_m)\\ V &= (\boldsymbol{v}_1, \boldsymbol{v}_2, ..., \boldsymbol{v}_n). \end{aligned}$$

このとき、ベクトル $ui, i=1,2,...,r\boldsymbol{u}_i, \, i=1,2, ..., r$ は、$m×mm \times m$ 正方行列 $XX⊤\boldsymbol{X}\boldsymbol{X}^\top$ の固有値$λi\lambda_i$に対応する固有ベクトルになっている：

$$(XX⊤)ui=λiui. \left(\boldsymbol{X}\boldsymbol{X}^\top\right) \boldsymbol{u}_i = \lambda_i \boldsymbol{u}_i.$$

同様にして、ベクトル $vi, i=1,2,...,r\boldsymbol{v}_i, \, i=1,2, ..., r$ は、$n×nn \times n$ 正方行列 $X⊤X\boldsymbol{X}^\top\boldsymbol{X}$ の固有値$λi\lambda_i$に対応する固有ベクトルになっている：

$$(X⊤X)vi=λivi. \left(\boldsymbol{X}^\top\boldsymbol{X}\right) \boldsymbol{v}_i = \lambda_i \boldsymbol{v}_i.$$

また、ベクトル $ui\boldsymbol{u}_i$ と $vi\boldsymbol{v}_i$ の間には以下の関係が成り立つ：

$$ui=1λiXvi,vi=1λiX⊤ui \boldsymbol{u}_i = \frac{1}{\sqrt{\lambda_i}} \boldsymbol{X} \boldsymbol{v}_i, \quad \boldsymbol{v}_i = \frac{1}{\sqrt{\lambda_i}} \boldsymbol{X}^\top \boldsymbol{u}_i$$

別表現

ベクトルによる表現

上記の分解をベクトルを用いて以下のように表すこともできる：

$$X=∑i=1rλiuivi⊤ \boldsymbol{X} = \sum_{i=1}^r \sqrt{\lambda_i} \boldsymbol{u}_i \boldsymbol{v}_i^\top$$

compact SVD

$U,VU, V$ を構成するベクトル${ui},{vi}\{\boldsymbol{u}_i\}, \{\boldsymbol{v}_i\}$ のうち、$XX⊤\boldsymbol{X}\boldsymbol{X}^\top$ ないし $X⊤X\boldsymbol{X}^\top\boldsymbol{X}$ の固有ベクトルとなっている $rr$ 番目までのものを用いて、以下のように表すこともできる：

$$U~=(u1,u2,...,ur)∈Rm×r,V~=(v1,v2,...,vr)∈Rn×r \tilde{U} = (\boldsymbol{u}_1, \boldsymbol{u}_2, ..., \boldsymbol{u}_r) \in \mathbb{R}^{m\times r}, \quad \tilde{V} = (\boldsymbol{v}_1, \boldsymbol{v}_2, ..., \boldsymbol{v}_r) \in \mathbb{R}^{n\times r}$$

$$Σ~=diag(λ1,λ2,...,λr)∈Rr×r \tilde{\Sigma} = {\rm diag}\left(\sqrt{\lambda_1}, \sqrt{\lambda_2}, ..., \sqrt{\lambda_r}\right) \in \mathbb{R}^{r \times r}$$

$$X=U~Σ~V~⊤ \boldsymbol{X} = \tilde{U} \tilde{\Sigma} \tilde{V}^\top$$

具体例

ここでは具体的に、以下の行列を特異値分解してみる：

$$X=(010102021010). \boldsymbol{X}= \begin{pmatrix} 0 & 1 & 0 & 1\\ 0 & 2 & 0 & 2\\ 1 & 0 & 1 & 0 \end{pmatrix}.$$

この行列は、2行目が1行目の2倍になっていることから分かるように、$rank X=2{\rm rank}\, \boldsymbol{X} = 2$ である。

まず、 $3×33 \times 3$ 行列 $XX⊤\boldsymbol{X}\boldsymbol{X}^\top$ について考える：

$$XX⊤=(240480002). \boldsymbol{X}\boldsymbol{X}^\top = \begin{pmatrix} 2 & 4 & 0\\ 4 & 8 & 0\\ 0 & 0 & 2 \end{pmatrix}.$$

この行列の固有値は ${10,2,0}\{10, 2, 0\}$ であり、それぞれに対応する固有ベクトルは、

$$15(120),(001),15(−210) \frac{1}{\sqrt{5}} \begin{pmatrix} 1\\ 2\\ 0 \end{pmatrix}, \quad \begin{pmatrix} 0\\ 0\\ 1 \end{pmatrix}, \quad \frac{1}{\sqrt{5}} \begin{pmatrix} -2\\ 1\\ 0 \end{pmatrix}$$

となる。

このとき、$4×44 \times 4$ 行列 $X⊤X\boldsymbol{X}^\top \boldsymbol{X}$ も固有値として ${10,2}\{10, 2\}$を持つはずであり、それぞれに対応する固有ベクトルは、

$$110X⊤15(120)=12(0101)12X⊤(001)=12(1010) \begin{aligned} \frac{1}{\sqrt{10}} \boldsymbol{X}^\top \frac{1}{\sqrt{5}} \begin{pmatrix} 1\\ 2\\ 0 \end{pmatrix} &= \frac{1}{\sqrt{2}} \begin{pmatrix} 0\\ 1\\ 0\\ 1 \end{pmatrix}\\ \frac{1}{\sqrt{2}} \boldsymbol{X}^\top \begin{pmatrix} 0\\ 0\\ 1 \end{pmatrix} &= \frac{1}{\sqrt{2}} \begin{pmatrix} 1\\ 0\\ 1\\ 0 \end{pmatrix} \end{aligned}$$

である。
なお、残りの固有値は2つとも0であり、対応する固有ベクトルとしては上記と直交するように以下を取る：

$$12(010−1),12(10−10). \frac{1}{\sqrt{2}} \begin{pmatrix} 0\\ 1\\ 0\\ -1 \end{pmatrix}, \qquad \frac{1}{\sqrt{2}} \begin{pmatrix} 1\\ 0\\ -1\\ 0 \end{pmatrix}.$$

以上から、

$$U=(1/50−2/52/501/5010),V=(01/201/21/201/2001/20−1/21/20−1/20) U = \begin{pmatrix} 1/\sqrt{5} & 0 & -2/\sqrt{5}\\ 2/\sqrt{5} & 0 & 1/\sqrt{5}\\ 0 & 1 & 0 \end{pmatrix}, \qquad V = \begin{pmatrix} 0 & 1/\sqrt{2} & 0 & 1/\sqrt{2}\\ 1/\sqrt{2} & 0 & 1/\sqrt{2} & 0\\ 0 & 1/\sqrt{2} & 0 & -1/\sqrt{2}\\ 1/\sqrt{2} & 0 & -1/\sqrt{2} & 0 \end{pmatrix}$$

$$Σ=(1000002000000) \Sigma = \begin{pmatrix} \sqrt{10} & 0 & 0 & 0\\ 0 & \sqrt{2} & 0 & 0\\ 0 & 0 & 0 & 0 \end{pmatrix}$$

のよう対応するため、

$$X=UΣV⊤=(1/50−2/52/501/5010)(1000002000000)(01/201/21/201/2001/20−1/21/20−1/20)=(1/502/5001)(10002)(01/201/21/201/20) \begin{aligned} \boldsymbol{X} &= U \Sigma V^\top\\ &= \begin{pmatrix} 1/\sqrt{5} & 0 & -2/\sqrt{5}\\ 2/\sqrt{5} & 0 & 1/\sqrt{5}\\ 0 & 1 & 0 \end{pmatrix} \begin{pmatrix} \sqrt{10} & 0 & 0 & 0\\ 0 & \sqrt{2} & 0 & 0\\ 0 & 0 & 0 & 0 \end{pmatrix} \begin{pmatrix} 0 & 1/\sqrt{2} & 0 & 1/\sqrt{2}\\ 1/\sqrt{2} & 0 & 1/\sqrt{2} & 0\\ 0 & 1/\sqrt{2} & 0 & -1/\sqrt{2}\\ 1/\sqrt{2} & 0 & -1/\sqrt{2} & 0 \end{pmatrix}\\ &= \begin{pmatrix} 1/\sqrt{5} & 0\\ 2/\sqrt{5} & 0\\ 0 & 1 \end{pmatrix} \begin{pmatrix} \sqrt{10} & 0\\ 0 & \sqrt{2}\\ \end{pmatrix} \begin{pmatrix} 0 & 1/\sqrt{2} & 0 & 1/\sqrt{2}\\ 1/\sqrt{2} & 0 & 1/\sqrt{2} & 0 \end{pmatrix} \end{aligned}$$

が特異値分解の結果である。

参考

• 井出剛、入門 機械学習による異常検知―Rによる実践ガイド（2015、コロナ社）

https://amzn.asia/d/4uQ3D19

• Singular value decomposition (in Wikipedia)

https://en.wikipedia.org/wiki/Singular_value_decomposition

• D. A. Harville, Matrix Algebra From a Statistician's Perspective (2006, Springer)
  • 日本語訳： D. A. ハーヴィル（伊理正夫監訳）、統計のための行列代数 上・下（丸善、2012）

https://amzn.asia/d/eFLLrNg
https://amzn.asia/d/h5awcqR
https://amzn.asia/d/fRgKunk