特異値分解

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

応用例¶

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

ある行列 $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]])

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

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

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

\sigma_i=\sqrt{\lambda_i}

を 特異値 とよぶ

特異値 $\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}$ の固有ベクトルになります。

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

となる。

import numpy as np

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

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

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]])