宇宙一分かりやすい特異値分解

はじめに

昨今，様々な分野で特異値分解という手法を耳にします．私が初めて目にしたのは自然言語処理の本を読んでいるときでした．

この記事では，特異値分解について天下り的ではなく導出的に解説したいと思います．行列の対角化は既知とします．

モチベーション

一般に正方行列 $B\in\mathbb R^{n\times n}$ が対角化可能とは，ある正則行列 $P$ と対角行列 $\Lambda$ が存在して，

$$
B=P\Lambda P^{-1}
$$

とかけることでした．特に対角化可能なとき，$\Lambda$ は $B$ の固有値を並べたものでした．

対角化することは相似な行列の中で最も簡単な表現を求めることと言えるでしょう．すなわち，行列の本質情報を取得しています．

さて，次に正方行列とは限らない $A\in\mathbb R^{m\times n}$ を考えます．簡単のため $n\le m$ とします．このとき，ある正則行列 $P,Q$ と本質情報である “対角行列” $\Sigma$ が存在して，

$$
A=P\Sigma Q
$$

と表せるでしょうか？$A$ の形から $\Sigma$ は次のような対角行列であることが期待されます：

\Sigma=\begin{pmatrix}
\sigma_1 & &\\
&\ddots&\\
&&\sigma_n\\
&&\\
&\huge O&
\end{pmatrix}\in\mathbb R^{m\times n}.

では対角化のときと同様に，対角成分は $A$ の “固有値” とできるでしょうか？もちろん，固有値は正方行列に対してのみ定義されていたので新たな特徴量を考えないといけませんね．

固有値から特異値へ

固有値と固有ベクトルについて

例えば，$B\in\mathbb R^{2\times 2}$ が固有値 $\lambda_1,\lambda_2$ とその固有ベクトル $v_1,v_2$ をもつとします．ここで $v_1,v_2$ は正規直交化されているとします．

固有値の定義から，$\mathbb R^2$ 上の単位円は $B$ を作用することにより，$\mathbb R^2$ 上の楕円となります．この長軸と短軸の長さが固有値ですね．

固有値の一般化

では，上の議論を参考にして $A\in\mathbb R^{m\times n}$ の “固有値” について考えてみましょう¹．

$\mathbb R^n$ 上の単位超球面 $S$ は $A$ を作用することで $\mathbb R^m$ 上の超楕円となります．その楕円の軸を $\sigma_1u_1,\ldots,\sigma_nu_n$ としましょう．但し，$u_1,\ldots,u_n$ は正規直交になるようにとります．

そして，元の $S$ 上のベクトル $v_1,\ldots,v_n$ を $Av_i=\sigma_i u_i$ となるようなものと定義します．

このとき，簡単に $A^\top u_i=\sigma_i v_i$ となることが分かり，

$$
A^\top A v_i=\sigma_i^2v_i,\quad AA^\top u_i=\sigma^2_iu_i
$$

が成り立ちます (check)²．つまり，正方行列での固有値の性質を満たすように一般の行列 $A$ の "固有値" $\sigma_i$ を定めた結果，$\sigma_i$ は $A^\top A$ の固有値の平方根となることが分かりました．

（Trefethen, Numerical Linear Algebra より引用）

特異値の定義

以上の議論から得られた性質を用いて，$A\in\mathbb R^{m\times n}$ の "固有値" として考えうる量を定義します：

Definition
$\sigma\ge 0$ が $A$ の特異値であるとは，$\sigma^2$ が $A^\top A$ の固有値であることをいう．すなわち，ある 0 でない $v\in\mathbb R^n$ が存在して，

A^\top Av=\sigma^2 v

を満たすことをいう．

Remark

• 特異値分解（後述）したあとの対角行列の成分を特異値と定義することもある．相似な行列が同じ固有値をもつことから，対角化したあとの対角成分を固有値としてもよいことが分かるだろう．それのアナロジーである．
• $A^\top A$ はグラム行列と呼ばれ，非負実数の固有値を重複度を込めて $n$ 個もつ（確認は容易）
• 一般に，実対称行列は直交行列で対角化できることから，以降可能なときは，固有ベクトルは正規直交基底になるようにとる
• ランクとの関係として，$A^\top A$ の非ゼロ固有値は $\text{rank } A$ 個であることが次元定理より確認できる（固有空間の次元と固有値の重複度が一致することは対角化可能からしか分からない？）

特異値の定義として $AA^\top$ を考えてもよいでしょう．先の議論では固有値の重複度については何も言えていないので厳密な説明をしておきます．いま，$A^\top A$ の固有値を $\sigma_1^2,\ldots,\sigma_n^2$，各固有値に対する正規直交化された固有ベクトルを $v_i$ とかきます．

$$
u_i:=\dfrac1{\sigma_i} Av_i
$$

とおけば，

$$
AA^\top u_i=AA^\top Av_i/\sigma_i=\sigma_i Av_i=\sigma_i^2 u_i
$$

が成り立ちます．つまり，$\sigma_i^2$ は $AA^\top$ の固有値であり，$u_i$ は正規直交化された (check) 固有ベクトルとなります³．また，重複度については，$A^\top A$ の非負固有値に属する線形独立な固有ベクトル $v_1,~v_2$ がとれたとき，$u$ の定義から $u_1,~u_2$ は線形独立であるので，非負固有値は重複度を込めて一致します（線形写像の行き先で線形独立ならもとの元も線形独立でした）．

以上より，正の特異値については $A^\top A,~AA^\top$ のどちらを考えてもよいことが分かります．従って，特異値を

$$
\sigma_1\ge\cdots\ge\sigma_n\ge\cdots\ge\sigma_m
$$

と昇順にして統一的に扱えます⁴．

特異値分解

以上の議論から，対角化のときの対角行列に相当する行列を作ることができます．そして，この行列を用いると，私たちの期待通りの結果が得られます！

Theorem

いま，

V=[v_1,\ldots,v_n]\in\mathbb R^{n\times n},\quad U=[u_1,\ldots,u_m]\in\mathbb R^{m\times m},\quad
\Sigma=\begin{pmatrix}
\sigma_1 & &\\
&\ddots&\\
&&\sigma_n\\
&&\\
&\huge O&
\end{pmatrix}\in\mathbb R^{m\times n}

とおくと，

$$
A=U\Sigma V^\top
$$

が成り立つ．

(Proof.)

$\sigma_i, u_i,v_i$ の関係を使えば実は自明です：

    \begin{align*}
    U\Sigma V^\top &=\sum_{i=1}^n\sigma_iu_iv_i^\top\\
    &=\sum_{i=1}^ n Av_iv_i^\top\\
    &=A.
    
    \end{align*}

最後に

特異値分解はやっていることのシンプルさとは裏腹に，難解なイメージをもたれることが多いように思います．この記事を通して，取っ付きにくさを克服できた方がいれば幸いです！

1. 説明のため暗にフルランクを仮定しています ↩

2. $\set{v_i},\set{u_i}$ が正規直交系であるので，$(Av_j)^\top u_i=\sigma_i\delta_{ij}$ が成り立ちます．従って，$A^\top u_i$ は $v_i$ 方向にしか大きさをもたないことが分かります． ↩

3. 前の節では $\set{v_i},\set{u_i}$ が正規直交系であることを仮定することで $v_i$ と $u_i$ の関係が導出されました．一方で，この節ではその関係式を用いて $v_i$ から $u_i$ を定義しているので，新たに定まった $u_i$ が正規直交系であることを示す必要があります． ↩

4. $i>\text{rank }A(=\text{rank }A^\top A)$ のとき $\sigma_i=0$ より，$\sigma_1,\ldots,\sigma_{\text{rank }A}$ を特異値ということがあります． ↩