特異値分解

特異値分解#

特異値分解（Singular Value Decomposition, SVD） は、任意の行列を3つの行列に分解する手法。

特異値分解

任意の \(m \times n\) 行列 \(A\) に対して、SVDは次のように表現される

\[ A=U \Sigma V^{\top} \]

  • \(A:\) 元の \(m \times n\) 行列

  • \(U: m \times m\) の直交行列（左特異ベクトル）

  • \(\Sigma: m \times n\) の対角行列（特異値が対角に並ぶ）

    • \(\Sigma\) の対角要素（特異値）は非負で、通常は大きい順に並べる

  • \(V^{\top}: n \times n\) の直交行列（右特異ベクトルの転置）

応用例#

固有値・固有ベクトルを求めたいとき、次元削減して計算量を抑えるテクニックとして使われる。

ある行列\(N\in\mathbb{R}^{n \times n}\)が行列\(A\in\mathbb{R}^{n\times m}\)により\(N = A A^\top\)として表現できるとき、別の行列\(M = A^\top A \in\mathbb{R}^{m \times m}\)

import numpy as np

A = np.array([[3, 1],
       [1, 3],
       [2, 1]])

A.T @ A

array([[14,  8],
       [ 8, 11]])

A @ A.T

array([[10,  6,  7],
       [ 6, 10,  5],
       [ 7,  5,  5]])

A.T

array([[3, 1, 2],
       [1, 3, 1]])

SVDのアルゴリズム#

1. \(A^\top A\)の固有値分解#

行列 \(A^{\top} A \in \mathbb{R}^{n \times n}\) は対称かつ半正定値（symmetric & positive semi-definite）であるため、固有値分解ができる。

\[ A^{\top} A=V \Lambda V^{\top} \]

  • \(V\) ：直交行列（列は固有ペクトル）

  • \(\Lambda=\operatorname{diag}\left(\lambda_1, \ldots, \lambda_n\right)\) ：非負の固有値

この固有値 \(\lambda_i \geq 0\) の平方根

\[ \sigma_i=\sqrt{\lambda_i} \]

を 特異値 とよぶ

2. 右特異ベクトルから左特異ベクトルを作る#

特異値 \(\sigma_i>0\) のとき、

\[ A v_i=\sigma_i u_i \quad \Rightarrow \quad u_i=\frac{1}{\sigma_i} A v_i \]

ここで \(v_i\) は \(A^{\top} A\) の固有ベクトル、 \(u_i\) は \(A A^{\top}\) の固有ベクトルになります。

3. 行列にまとめる#

  • \(V=\left[v_1, \ldots, v_n\right] \in \mathbb{R}^{n \times n}\)

  • \(U=\left[u_1, \ldots, u_m\right] \in \mathbb{R}^{m \times m}\)

  • \(\Sigma \in \mathbb{R}^{m \times n}\) の対角に \(\sigma_1, \ldots, \sigma_r\) を配置（残りはゼロ）

とすると、

\[ A=U \Sigma V^{\top} \]

となる。

実装#

numpy.linalg.svd()を使う場合#

import numpy as np

A = np.array([[3, 1],
              [1, 3],
              [2, 1]])
U, S, VT = np.linalg.svd(A)

U

array([[-0.64871739,  0.54898814, -0.52704628],
       [-0.59110282, -0.7996789 , -0.10540926],
       [-0.47933622,  0.24315772,  0.84327404]])

S

array([4.54306178, 2.08820251])

VT

array([[-0.76950911, -0.63863584],
       [ 0.63863584, -0.76950911]])

# 対角行列に変換
Sigma = np.zeros_like(A, dtype=float)
np.fill_diagonal(Sigma, S)

# 検証：A ≈ U @ Sigma @ VT
reconstructed = U @ Sigma @ VT
reconstructed

array([[3., 1.],
       [1., 3.],
       [2., 1.]])

import numpy as np

A = np.array([[3, 1, 2],
              [1, 3, 1]])

A.T @ A

array([[10,  6,  7],
       [ 6, 10,  5],
       [ 7,  5,  5]])

A @ A.T

array([[14,  8],
       [ 8, 11]])
Contents