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

基本

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

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

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

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

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

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

以下では、

$$\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)$$

$$\lambda_1 \ge \lambda_2 \ge ... \ge \lambda_r >0$$

とする。

$U, V, \Sigma$ の関係

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

$$\begin{aligned} U &= (\boldsymbol{u}_1, \boldsymbol{u}_2, ..., \boldsymbol{u}_m)\\ V &= (\boldsymbol{v}_1, \boldsymbol{v}_2, ..., \boldsymbol{v}_n). \end{aligned}$$

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

$$\left(\boldsymbol{X}\boldsymbol{X}^\top\right) \boldsymbol{u}_i = \lambda_i \boldsymbol{u}_i.$$

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

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

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

$$\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$$

別表現

ベクトルによる表現

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

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

compact SVD

$U, V$ を構成するベクトル$\{\boldsymbol{u}_i\}, \{\boldsymbol{v}_i\}$ のうち、$\boldsymbol{X}\boldsymbol{X}^\top$ ないし $\boldsymbol{X}^\top\boldsymbol{X}$ の固有ベクトルとなっている $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}$$

$$\tilde{\Sigma} = {\rm diag}\left(\sqrt{\lambda_1}, \sqrt{\lambda_2}, ..., \sqrt{\lambda_r}\right) \in \mathbb{R}^{r \times r}$$

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

具体例

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

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

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

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

$$\boldsymbol{X}\boldsymbol{X}^\top = \begin{pmatrix} 2 & 4 & 0\\ 4 & 8 & 0\\ 0 & 0 & 2 \end{pmatrix}.$$

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

$$\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 \times 4$ 行列 $\boldsymbol{X}^\top \boldsymbol{X}$ も固有値として $\{10, 2\}$を持つはずであり、それぞれに対応する固有ベクトルは、

$$\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であり、対応する固有ベクトルとしては上記と直交するように以下を取る：

$$\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 = \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}$$

$$\Sigma = \begin{pmatrix} \sqrt{10} & 0 & 0 & 0\\ 0 & \sqrt{2} & 0 & 0\\ 0 & 0 & 0 & 0 \end{pmatrix}$$

のよう対応するため、

$$\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