特異値分解(SVD: singular value decomposition)
任意の $m \times n$ 行列 $M$ について、
$$M = U \Sigma V^\dagger$$
となる分解が存在する。ここで、$U$は $m \times m$ のユニタリ行列、$V$は $n \times n$ のユニタリ行列、 $\Sigma$ は、対角成分が非負で、非対角成分が0の $m \times n$ の実数行列である。
特異値分解は、実用的には、データの次元削減や圧縮、主成分分析に用いることができる。特異値分解を使って画像の次元削減・圧縮である「低ランク近似」をした記事としては特異値分解による画像の低ランク近似が面白い。
本記事では、行列やベクトルは、特に明記されていなければ複素行列、複素ベクトルを考えるが、「エルミート行列」を「対称行列」、「ユニタリ行列」を「回転行列」と読み替えることで、実数行列に対する議論として読み替えることもできる。
また、本記事では、具体的に行列を特異値分解する方法を示すことで分解の存在を証明しているので、本記事の手法にのっとって、実際に特異値分解を実装することも可能である。しかし、教育的な求め方ではあるものの、精度・速度の面で実用的な求め方ではない。より実用的なものについては、たとえば特異値分解アルゴリズムの最近の発展 (2014, 山本)やLAPACKのzgesvdの参考実装、Eigenの実装などを参照するとよい。
記法と基礎知識
本記事に使う記法とその基礎知識を以下で振り返る。
零ベクトルと単位行列の記法
全ての要素が$0$のベクトルを$\mathbf{0}$と書く。単位行列を$I$と書く。
内積
同じ次元のベクトル$\mathbf{u}, \mathbf{v}$の内積は $\mathbf{u}^\dagger \mathbf{v} = \mathbf{v}^\dagger \mathbf{u}$で書き表せる。特に、同じベクトル同士の内積 $\mathbf{v}^\dagger \mathbf{v}$ は、$\mathbf{v}$ の長さ(L2ノルム)の2乗 $|\mathbf{v}|^2$ となる。 $|\mathbf{v}|^2 \geq 0$であり、$|\mathbf{v}|^2 = 0$となるのは$\mathbf{v} = \mathbf{0}$のとき、また、そのときに限る。
エルミート共役、複素共役、転置の記法
行列やベクトルのエルミート共役(転複素共役)を ${}^\dagger$ で表記し、また、スカラー値の複素共役を $^*$ で表記する。行列の転置は ${}^t$ で表記する。
エルミート行列とユニタリ行列
正方行列 $H$ が $H = H^\dagger$ であるとき、 $H$ をエルミート行列という。正方行列 $U$ が $U U^\dagger = U^\dagger U = I$ であるとき、$U$ をユニタリ行列という。
$n \times n$ 次元エルミート行列 $H$ は、$H = U \Lambda U^\dagger$のように分解できる。ここで、$U$ は $n \times n$ 次元ユニタリ行列、 $\Lambda$ は $n \times n$ 実対角行列である。この分解を対角化という。
このとき、 $U$ の $i$ 列目 ($i = 1, \cdots n$) の縦ベクトル $\mathbf{u} _ i$ は、 $|\mathbf{u} _ i| = 1$となる$H$の固有ベクトルとなり、その固有値は$\Lambda_{ii}$である。
また、固有値、固有ベクトルの組を並べる順番は任意であるが、本記事では、エルミート行列の対角化において、固有値は大きい順に並べることとする。すなわち、 $i < j$ のとき、 $\Lambda_{ii} \geq \Lambda_{jj}$ が成り立つ。
実行列の場合についての補足
実正方行列においては、エルミート共役は単なる転置に対応する。
$H = H^t$ である行列を $H$ を対称行列という。また、$U^t = U^t U = I$となる行列 $U$ を回転行列という。
実対称行列においても、実回転行列と実対角行列によって対角化ができる。
半正定値行列
$n \times n$ エルミート行列 $H$ が、以下の性質をもつとき、 $H$ が半正定値(PSD: positive-semidefinite)行列であるとは、以下の性質を満たすことである:
任意の$\mathbf{0}$でない$n$次元複素ベクトル$\mathbf{v}$について、$\mathbf{v}^\dagger H \mathbf{v} \geq 0$となる。
系: 半正定値行列の固有値はすべて非負
$H$を半正定値行列とする。$H$はエルミート行列でもあるので、$H$の各固有値 $\lambda _ i$ と(L2ノルムが1となる)固有ベクトルの組 $\mathbf{u} _ i$について、
$$\begin{align*}0 \leq \mathbf{v}_i^\dagger H \mathbf{v}_i &= \mathbf{v}_i^\dagger \lambda_i \mathbf{v}_i \\
&= \lambda_i \mathbf{v}_i^\dagger \mathbf{v}_i \\
&= \lambda_i\end{align*}$$
が成り立つ。
階数 (rank)
行列 $M$ の階数または rank とは、行列を縦ベクトルとして見たときに、線形独立なものの最大の個数をいう。すなわち、各縦ベクトルを基底とするベクトル空間の次元の数をいう。
行列 $M$ の rank を $\mathrm{rank}(M)$ と書き表す。
また、行列 $M$ のサイズが $m \times n$ のとき、 $\mathrm{rank}(M) \leq \min(m, n)$ となる。
グラム行列
行列 $M$ が与えられたとき、 $M^\dagger M$ を $M$ のグラム行列という。
なお、$M$ が $m \times n$ 行列のとき、 $M^\dagger M$ は $n \times n$ 行列である。
系: グラム行列はエルミート行列である
任意の行列 $M$ について、そのグラム行列 $M^\dagger M$ のエルミート共役は $(M^\dagger M)^\dagger = M^\dagger M$ である。よって、エルミート行列である。
系: グラム行列は半正定値行列である
任意の行列 $M$ とベクトル $\mathbf{v}$ について、
$$\begin{align*}
\mathbf{v}^\dagger M^\dagger M \mathbf{v} &= (M \mathbf{v})^\dagger (M \mathbf{v})\\
&= |M\mathbf{v}|^2\\
&\geq 0
\end{align*}$$
が成り立つので、任意の行列について、そのグラム行列は半正定値行列である。
系: 行列 M の rank と、 M のグラム行列の rank は等しい
$\mathrm{rank}(M) = \mathrm{rank}(M^\dagger M)$ を示す。
これを示すには、連立一次方程式 $M\mathbf{x} = \mathbf{0}$ と $M^\dagger M\mathbf{x} = \mathbf{0}$ が同じ解を持つことを示せば十分である。なぜならば、連立一次方程式の解が同じであるならば、解の自由度が同じであることになり、行列の rank は $\mathbf{x}$ の次元 $n$ から解の自由度を引いた値で定まるからである。
(⇒) $M\mathbf{x} = \mathbf{0}$ ならば $M^\dagger M\mathbf{x} = \mathbf{0}$ を示す。
$M\mathbf{x} = \mathbf{0}$ を仮定すると、$M^\dagger M \mathbf{x} = M^\dagger \mathbf{0} = \mathbf{0}$ なので従う。
(⇐) $M^\dagger M\mathbf{x} = \mathbf{0}$ ならば $M\mathbf{x} = \mathbf{0}$ を示す。
$M^\dagger M\mathbf{x} = \mathbf{0}$ を仮定すると、$|M \mathbf{x}|^2 = \mathbf{x}^\dagger M^\dagger M\mathbf{x} = \mathbf{x}^\dagger\mathbf{0} = 0$ が成り立つ。$|M \mathbf{x}|^2 = 0$ より $M \mathbf{x} = 0$ が従う。
SVDの存在証明
まず、SVDの主張を再掲する。続いて、証明をする。
定理
任意の $m \times n$ 行列 $M$ について、
$$M = U \Sigma V^\dagger$$
となる分解が存在する。
ここで、$U$は $m \times m$ のユニタリ行列、$V$は $n \times n$ のユニタリ行列、 $\Sigma$ は、対角成分が非負で、非対角成分が0の $m \times n$ の実数行列である。
証明
$m \times n$ 行列 $M$ について、そのグラム行列 $M^\dagger M$ を考える。 $M^\dagger M$ はエルミート行列なので、以下のように対角化ができる。
$$M^\dagger M = V^\dagger \Lambda V$$
ここで、$V$はユニタリ行列、$\Lambda$は実対角行列である。
また、グラム行列は半正定値行列であるので、すべての固有値、すなわち実対角行列 $\Lambda$ の各成分は非負である。よって、非負の実数 $\sigma_i = \sqrt{\Lambda_{ii}}$ を取ることができる。
ここで、 $r = \mathrm{rank}(M)$ とおく。このとき、$r = \mathrm{rank}(M^\dagger M)$ でもあるので、 $\sigma_1, \cdots, \sigma_r > 0$ である(本記事では、エルミート行列の対角化において、固有値は大きい順に並べていることに注意する)。
すなわち、$\mathbf{v} _ i$ を $V$ の $i$ 列目を縦ベクトルとして見たものとすると、 $i = 1, \cdots, r$について、
$$\mathbf{u}_i = \frac{M}{\sigma_i}\mathbf{v}_i$$
をとることができる。なお、 $M$ が $m \times n$ 行列で、 $\mathbf{v}_i$ が $n$ 次元ベクトルであるので、 $\mathbf{u}_i$ は $m$ 次元ベクトルである。
補題: $i = 1, \cdots, r$ において、 $\mathbf{u}_i$ は $M M^\dagger$の固有ベクトルで、それに対応する固有値は $\sigma_i^2$ である。
証明: 以下より従う。
$$\begin{align*}M M^\dagger \mathbf{u}_i
&= M M^\dagger \frac{M}{\sigma_i}\mathbf{v}_i \\
&= \frac{M}{\sigma_i} (M^\dagger M)\mathbf{v}_i \\
&= \frac{M}{\sigma_i} \Lambda _ {ii} \mathbf{v} _ i \\
&= \sigma_i^2 \mathbf{u}_i
\end{align*}$$
補題: $\{\mathbf{u} _ 1, \cdots, \mathbf{u} _ r\}$ は正規直交系をなす。
証明: 任意の$i, j \in \{1, \cdots, r\}$について、
$$\begin{align*}\mathbf{u} _ i^\dagger \mathbf{u}
&= \mathbf{v} _ i ^\dagger \frac{M^\dagger}{\sigma _ i} \frac{M}{\sigma _ j} \mathbf{v} _j \\
&= \frac{1}{\sigma _ i \sigma _ j} \mathbf{v} _ i^\dagger (M^\dagger M \mathbf{v} _ j) \\
&= \frac{\sigma _ j^2}{\sigma _ i \sigma _ j}\mathbf{v}^\dagger _ i \mathbf{v} _ j \\
&= \begin{cases}
1 & (i = j) \\
0 & (i \ne j)
\end{cases} \\
&= \delta _ {ij}
\end{align*}$$
が成り立つ。ここで、 $\delta _ {ij}$ はクロネッカーのデルタである。よって、これらは正規直交系をなす。
行列の rank による場合分け
$m \times n$ 行列 $M$ の rank $r$ は、 $r \leq \min(m, n)$ である。$r = m$ の場合は簡単であるが、 $r < m$ の場合は、追加で考慮すべきことがある。まずは $r = m$の場合について証明を行う。
r の rank が m に等しい場合
$r = m$ のとき、縦ベクトルを並べた $U = (\mathbf{u}_1 \cdots \mathbf{u}_m)$ が $m \times m$ のユニタリ行列となることが、 $\{\mathbf{u}_i\}$ が $m$ 次元の正規直交系であることからわかる。
$i$ 番目の対角成分が $\sigma_i$ となる $m \times m$ 対角行列を $\Sigma$ とおく。このとき、 $\Sigma$ の逆行列 $\Sigma^{-1}$ は、 $i$ 番目の対角成分が $\frac{1}{\sigma_i}$ となる対角行列である。
$\mathbf{u}_i = M \mathbf{v}_i \frac{1}{\sigma_i}$ に注意すると、
$$\begin{align*}
U &= MV\Sigma^{-1} \\
U\Sigma &= MV \\
M &= U\Sigma V^\dagger
\end{align*}$$
が示せた。これはSVDに他ならない。
r の rank が m より小さい場合
上のように行列 $U$ を作りたいが、ベクトルの本数が足りていない。$U \Sigma$ の形を見てみる。まだベクトルが決まっていない部分を$\mathbf{?}$で記述すると、以下のようになる。
$$U \Sigma =
\begin{pmatrix}
\mathbf{u}_1 & \cdots & \mathbf{u}_r & \mathbf{?} & \cdots & \mathbf{?}
\end{pmatrix}
\begin{pmatrix}
\sigma_1 & \cdots & 0 & 0 & \cdots & 0 \\
\vdots & \ddots & \vdots & \vdots & \ddots & \vdots \\
0 & \cdots & \sigma_r & 0 & \cdots & 0 \\
0 & \cdots & 0 & 0 & \cdots & 0 \\
\vdots & \ddots & \vdots & \vdots & \ddots & \vdots \\
0 & \cdots & 0 & 0 & \cdots & 0
\end{pmatrix}$$
この形を見れば分かる通り、$\mathbf{?}$の箇所は何であってもこの積は変わらない。唯一気をつけることは、$U$をユニタリ行列にすることである。
そのためには、すべての$\mathbf{u}_1, \cdots, $\mathbf{u}_r$と直交するような正規直交ベクトルを探してくればいいので、連立方程式
$$\begin{pmatrix}\mathbf{u}_1 & \cdots & \mathbf{u}_r\end{pmatrix}^T\mathbf{x} = \mathbf{0}$$
の解空間を求めて、シュミットの直行化法により直交ベクトルにしたものを$\mathbf{u}_{r + 1} \cdots \mathbf{u}_m$とし、$U = (\mathbf{u}_1 \cdots \mathbf{u}_m)$とすれば、
$$\begin{align*}
U\Sigma &= MV \\
M &= U\Sigma V^\dagger
\end{align*}$$
が示せる。よって、SVDが示せた。