ここでは随伴行列や転置行列は対象の行列の左上にマークをつけて表す。
特異値分解とは？
ある程度線形代数に真面目に取り組んだ人は固有値や対角化というものを扱ったと思う。
対角化も固有値も正方行列に定義されているもので非正方行列には定義されているわけではない。
また任意の正方行列は対角化可能ではない。
※固有空間の次元が元の正方行列のサイズと一致する必要がある。さらにいえばジョルダン標準形といって対角化行列より緩い行列を許容することで「拡張」ができる。(つまり計算しやすい材料をピックアップするためにルールを緩めて新しい概念を導入している)
任意の正方行列は三角化できる.
ジョルダン標準形まで拡張すればとりあえず正方行列に対しては「対角化っぽい」操作の定義は得られる。
↑もっとシンプルに言えば任意の正方行列は下三角部分もしくは上三角部分(対角部分は除く)を可逆な操作で成分が0となるようにできる。
非正方行列の場合
※非正方行列とは
左の項の因数のようなもの
これの対角化の「拡張」の「拡張」が特異値分解である。
ちなみに「固有値=特異値」ではない
特異値分解の定義
定理
任意の行列$M$は以下の通りに「分解」できる
$$M = U \Sigma {}^* V$$
ただし$V$は出力の空間の正規直交基底を並べた行列の随伴行列(複素共役をとって転置をとった行列)であり$U$は入力の空間の正規直交基底を並べた行列である。
また$\Sigma$は対角化行列っぽいもので$i$行$j$列の$i$,$j$を用いると$i = j$である成分のみが非負の値を持ちそれ以外が$0$の行列である。
※対角化行列:diagonal matrix
$M {}^*M$の固有値の正の平方根のことで特異値と呼ばれる。
$M {}^M \boldsymbol {x_i} = \lambda_i \boldsymbol x_i$
特異値$\sigma_i$は$\sigma_i= \sqrt{\lambda_i}$とできる.
あらかじめ縦ベクトルを原則とする、と約束しておくと
$$M {}^* M = U \Sigma^2 {}^* U$$となり
$U$は回転変換である。
また、${}^* M M = {}^* V \Sigma^2 V$となり
$V$は回転変換である. $V$も$U$も随伴行列であり,
${}^* U U=U^*U=E$である。
$M$が$m\times n$の行列とすると、$M{}^*M $を$m \times n$ ,$n \times m$なわけだから$m \times m$で、${}^*M M$は$n \times m$ ,$m \times n$なわけだから$n \times n$となる。
特異ベクトルを求めるには、$M{}^*M/(\dim \rm{inputspace})$を共分散行列といい,$\Phi$と名付けると,
$$\Phi= V\Sigma^2 {}^*V $$
$$\Phi V= V\Sigma^2$$
ここまでくれば固有ベクトルを求めることに帰着する。
後は、正規直交化すればよい。3つ並べて、
$$V = \begin{pmatrix} \boldsymbol v_1 & \boldsymbol v_2 & \boldsymbol v_3 \end{pmatrix}$$と設定すると
$$\Phi V= \begin{pmatrix} \lambda_1 \boldsymbol v_1 & \lambda_2 \boldsymbol v_2 & \lambda_3 \boldsymbol v_3 \end{pmatrix}$$
$${}^* M M = {}^* \Phi = {}^* U \Sigma^2 U$$
$$ \Phi {}^* U = {}^* U \Sigma^2$$
正規直交化すればよい。3つ並べて、
$$^* U = \begin{pmatrix} \boldsymbol u_1 & \boldsymbol u_2 & \boldsymbol u_3 \end{pmatrix}$$と設定すると
$$\Phi {}^* U= \begin{pmatrix} \lambda_1 \boldsymbol u_1 & \lambda_2 \boldsymbol u_2 & \lambda_3 \boldsymbol u_3 \end{pmatrix}$$
$u_i$を左特異ベクトル、$v_j$を右特異ベクトルという。
$U$を左特異行列、$V$を右特異行列とする。
随伴行列${}^* U$が実数成分の場合は、転置行列${}^t U$と同一視できる。
この辺を詳しくやろうと思ったら大学1、2年生の
ベクトル空間$V→W$に対してそれぞれ基底の入れ替えをする行列を$P$, $Q$とすると元のベクトル空間での線形写像$f$の表現行列$A$が入れ替え後は$Q^{-1}AP$になる云々や固有値の話を学習しなければならない。
低ランク近似
小さい特異値を0に換算して計算しなおす($U^* $, $V$をかける)と計算量が減ることになる。
Pythonによるコード
自然言語処理などに応用されているらしい。
I drive my car.
I read this document.
I read this paper.
行は単語(上から"I", "drive", "car", "read", "document", "paper")、列は文書で、値は単語の出現頻度にそれぞれ対応しています。
（one-hot表現）
※eigenvalue 固有値、diagonal 対角の
これを特異値分解($M=UΣ^t V$ )するとこうなります。
import numpy as np
import pandas as pd
np.set_printoptions(precision=3, suppress=True)
# 分解する行列
c = np.array([[1,1,1],[1,0,0,],[1,0,0],[0,1,1],[0,1,0],[0,0,1]])
# 特異値行列Σ(sigma) → 右特異行列V(v) → 左特異行列U(u) の順に求める
# C^TCの固有値と固有ベクトルの計算
ctc = np.dot(c.T, c)
eigen_values, eigen_vectors = np.linalg.eig(ctc)
# 特異値の計算
singular_values = np.sqrt(eigen_values)
singular_index = np.argsort(singular_values)[::-1]
# 特異値行列の計算
sigma = np.diag(singular_values[singular_index])
# 右特異行列の計算
v = eigen_vectors[:,singular_index]
# 左特異行列の計算
u = np.array([np.dot(c, v[:,i]) / sigma.diagonal()[i] for i in range(len(sigma.diagonal()))]).T
$Σ$は対角行列のため、対角要素$σ$が大きければ、$M$ に与える影響(寄与率)も大きくなります(逆に言いますと、$σ$が小さくなれば影響も小さくなります)。
そこで、上位$k(<n)$個の$σ$を残し、それ以外は0とした$M_k=U_kΣ_kVT_k$で近似することで、次元を削減します。 低ランク近似と呼ばれており、小さな特異値から削減することで、$M−M_k$の各要素の2乗誤差が最小になることが知られています。
上の例で$k=2$として$M_k=U_kΣ_kV^T_k$を求めると、以下の形になり、概ね行列$M$と$M_k$の値が近いことがわかります。
またこの近似によって、$M_k$の5行目("document")と6行目("paper")の値はいずれも(0, 0.5, 0.5)となっています。 同一の文書に現れるわけではない"document"と"paper"が、SVDによって類似した単語と判定できるようになった、と言うことができる
SVDを使ってレコメンドなど欠測値が多いデータの補完に用いられているケースもあります