特異値分解
特異値分解(とくいちぶんかい、singular value decomposition; SVD)とは線形代数学における複素数あるいは実数を成分とする行列に対する行列分解の一手法であり、Autonneによって導入された。悪条件方程式の数値解法で重宝するほか、信号処理や統計学の分野で用いられる。特異値分解は、行列に対するスペクトル定理の一般化とも考えられ、正方行列に限らず任意の形の行列を分解できる。
M を階数 r の m 行 n 列の行列とする。ただし、行列の要素は体 K の元であり、K は実数体 R または複素数体 C のいずれかであるとする。このとき、
M = U\Sigma V^*
という M の分解が存在する。
ここで U は m 行 m 列のユニタリ行列、V* は n 行 n 列のユニタリ行列 V の随伴行列(複素共役かつ転置行列)。さらに半正定値行列 MM*(あるいは M*M)の正の固有値の平方根 σ1 ≥ … ≥ σr > 0 が存在して、q = min(m, n), σr+1 = … = σq = 0 とおけば、m 行 n 列の行列 Σ は以下の形になる。
\Sigma =
\begin{cases}
\begin{bmatrix}
\Delta & O
\end{bmatrix}
& (m < n) \\
\Delta
& (m = n) \\
\begin{bmatrix}
\Delta \\
\end{bmatrix}
& (m > n)
\end{cases}
\quad
\text{where } \Delta = \operatorname{diag}(\sigma_1, \sigma_2, \dotsc, \sigma_q)
ここで Δ は σ1, ..., σq を対角成分とする q 行 q 列の対角行列、部分行列 O は零行列である。
この分解を特異値分解、σ1, ..., σq を行列 M の特異値と呼ぶ。
入力情報を n 成分の列ベクトル v として表し、出力として Mv が得られるようなモデルを考えると、行列 M の特異値分解によって得られるユニタリ行列と特異値について以下のような解釈を与えることができる。
行列 V の各列は、M の入力空間の正規直交基底を表す。
行列 U の各列は、M の出力空間の正規直交基底を表す。
特異値は増幅率を表し、入力成分がそれぞれ何倍されて出力されるかを表す。
Σ の対角成分の並びは自由だが、応用上は取り扱いを簡単にするため降順に並べることが多い。こうすると、U と V は一意には定まらないが、Σ は一意に定まる。
M を Km×n 上の行列とする。ある非負の実数 σ に対し、
\begin{align}
Mv   &= \sigma u \\
M^*u &= \sigma v
\end{align}
という条件を満たす Km 上の単位ベクトル u と Kn 上の単位ベクトル v の組が存在するとき、実数 σ を(ベクトル u, v に対応する)行列 M の特異値 (singular value) と呼ぶ。またベクトル u, v を、それぞれ σ の左特異ベクトル (left-singular vector) と右特異ベクトル (right-singular vector) と呼ぶ。
M = U\Sigma V^{*}
において、Σ の対角成分は M の特異値に等しく、ユニタリ行列 U, V の列ベクトルは、それぞれ左特異ベクトル、右特異ベクトルを並べたものである。すなわち、
m × n 行列 M は、少なくともひとつ、多くとも q = min(m, n) 個の異なる特異値を持つ。
常に Km 上のユニタリ基底が存在して、それは M の左特異ベクトルから成る。
常に Kn 上のユニタリ基底が存在して、それは M の右特異ベクトルから成る。
1つの特異値に対し、2つ以上の線形独立な右(あるいは左)特異ベクトルが存在する場合、その特異値は縮退 (degenerate) しているという。縮退のない特異値に対しては常に、左右の特異ベクトルがそれぞれ(位相 eiθ の違いを除いて)唯一つ存在する。結果として、もし行列 M のすべての特異値が正であり縮退のない場合、特異値分解は(ユニタリ行列 U, V の各列にかかる位相 eiθk の違いを除いて)唯一つに定まる。
縮退のある特異値 σdeg に対して、左特異ベクトル u1, u2 の正規化された線型結合 uc = αu1 + βu2 を考えると、左特異ベクトルの線型結合 uc もまた特異値 σdeg の左特異ベクトルとなっている。同様のことが右特異ベクトルについても成り立つ。特異値分解のユニタリ行列 V, U の特異値 σdeg に対応する列ベクトルは、特異ベクトルの線型結合の中から自由に選ぶことができるため、結果として行列 M の分解は一意ではなくなる。
固有値分解が正方行列に対してのみ適用できるのに対し、特異値分解は任意の矩形行列に対して適用が可能である。また、行列 M が正定値のエルミート行列(したがって正方行列)である場合、M の固有値は実数かつ非負であり、このとき M の特異値と特異ベクトルはそれぞれ M の固有値と固有ベクトルに一致する。
行列 U と V はユニタリ行列だから、U の列ベクトル u1,...,um は、体 Km 上の正規直交基底を成し、V の列ベクトル v1,...,vn は、体 Kn 上の正規直交基底を成す。
ベクトル x を Mx に写す線形変換(線型写像) T: K^{n} \rightarrow K^{m} は、これらの正規直交基底を用いて簡単な形に表される。すなわち、 T(v_{i}) = \sigma_{i} u_{i}, ここで i = 1,...,min(m,n) に対しては σi は Σ の i 番目の対角成分、i > min(m,n) に対し T(vi) = 0。
このことから、特異値分解定理の幾何的な意味は以下のように説明できる。線型写像 T: K^{n} \rightarrow K^{m} に対し、次のような性質を持つ正規直交基底 Km と Kn が存在する。ここに、T は Kn の i 番目の基底ベクトルを Km の i 番目の基底ベクトルについて σi 倍したものに写す。σi は負でない数。つまり、これらの基底を用いて、写像 T は、負でない数を成分に持つ対角行列で表される。
特異値分解を用いて、擬似逆行列を計算することができる。行列 M の擬似逆行列は、その特異値分解  M = U\Sigma V^* を用いて
と表せる。ここに Σ+ は、Σ の零でない成分の逆数を成分とする行列の転置である。この擬似逆行列を用いて、線形最小二乗法を行うことができる。
特異値分解を用いて、行列 M の値域、零空間を表現することができる。M の特異値の中で零になるものに対応する右特異ベクトルが零空間の基底となる。M の特異値の中で零でないものに対応する左特異ベクトルが値域の基底となる。すなわち M の行列の階数は、零でない特異値の数と一致する。さらに、M と M^*M と M M^* の階数は一致し、 M^*M と M M^* の固有値は一致する。
数値計算上では、特異値を用いて行列の実質的な階数を求めることができる。数値計算上では丸め誤差の影響で、階数が退化した行列に対し、非常に小さいが零ではない特異値が得られてしまう場合に有効である。
行列 M を、ある特定の階数 r を持つ別の行列 \tilde{M} で近似すると便利な場合がある。この場合の近似を\mbox{rank}(\tilde{M}) = r という条件のもとで M と \tilde{M} の差(フロベニウスノルム)が最小なものという意味であるとすると、行列 M の特異値分解によって、\tilde{M} を求めることができる。すなわち、
U \tilde{\Sigma} V^*
ここに、 \tilde{\Sigma} は、\Sigma から大きい方から数えて r 個の特異値を残して、それ以外の特異値を零とおいたもの。