特異値分解をふんわりと理解する

www.youtube.com

本記事は上記YouTube動画からの完全パクリである．
上記動画で特異値分解の"気持ち"が分かって感動したため，シェアしたくこの記事を書いた次第である．

さて，特異値分解の前に，まずは固有値分解について説明する．
正方行列 $A$ の固有値分解は以下で表される．

$A=V \Lambda V^{-1}$

$V$ は固有ベクトルを並べたもの， $\Lambda$ は固有値を対角成分に持つ行列である．

$\begin{eqnarray} \Lambda &=& \begin{pmatrix} \lambda _1 & 0 & \cdots & 0\\ 0 & \lambda _2 & \cdots & 0\\ \vdots & \vdots & \ddots & \vdots\\ 0 & 0 & \ldots & \lambda _M \\ \end{pmatrix} \end{eqnarray}$

このように分解できると何が嬉しいのかと言うと， $n$ 乗の計算が容易になる点が挙げられる．

$A^n=V \Lambda V^{-1} V \Lambda V^{-1} \cdots V \Lambda V^{-1}=V \Lambda ^n V^{-1}=V\begin{pmatrix} \lambda _1 ^n& 0 & \cdots & 0\\ 0 & \lambda _2 ^n & \cdots & 0\\ \vdots & \vdots & \ddots & \vdots\\ 0 & 0 & \ldots & \lambda _M ^n\\ \end{pmatrix}V^{-1}$

さて，固有値分解が行えるのは行列 $A$ が正方行列の時のみである．
行列 $A$ が正方行列じゃない場合にもこのような分解をしたい場合に行いたいのが特異値分解だ．

行列 $B(M \times N)$ の特異値分解は以下で表される．

$B=U \Sigma V^T$

$U(M \times M)$ は左特異ベクトルを並べたもの， $V(N \times N)$ は右特異ベクトルを並べたもので，これらは正規直交基底である．

$\boldsymbol{u}^T \boldsymbol{u}=1$ ， $\boldsymbol{v}^T\boldsymbol{v}=1$ ， $\boldsymbol{u}_1^T \boldsymbol{u}_2=0$ ， $\boldsymbol{v}_1^T\boldsymbol{v}_2=0$

$\Sigma(M \times N)$ は対角成分に特異値 $\sigma _m$ を大きい順に並べた行列である．

$\begin{eqnarray} \Sigma &=& \begin{pmatrix} \sigma _1 & 0 & \cdots & 0 & \cdots & 0\\ 0 & \sigma _2 & \cdots & 0 & \cdots & 0\\ \vdots & \vdots & \ddots & \vdots & \cdots & \vdots\\ 0 & 0 & \ldots & \sigma _M & \cdots & 0\\ \end{pmatrix} \end{eqnarray}$ where $\sigma _1 > \sigma _2 \cdots > \sigma _M$

$\Sigma$ はサイズが $M \times N$ であり， $M \times M$ の対角行列の右側(もしくは下側)に $0$ 成分が増えたような形となっている．

ここで突然 $B ^{}{B^{T}}$ を計算してみる．

$B^{}B^T=(U \Sigma V^T)(U \Sigma V^T)^T = (U \Sigma V^T)(V \Sigma ^T U^T)=U \Sigma^{} \Sigma ^T U^T$

最初のイコールは $B=U \Sigma V^T$ を代入しただけ，次のイコールは転置の基本ルール $(ABC)^T=C^T B^T A^T$ を適用，最後のイコールは $V$ が正規直交基底のため $V^TV=V^{-1}V=I$ となることを利用している．

さて， $B^{}B^T$ のサイズは $M \times M$ なので固有値分解が行えるはずだ．固有値分解の式を再掲しよう．

$A=V \Lambda V^{-1}$

これと $B^{}B^T=U \Sigma^{} \Sigma ^T U^T$ を見比べると，以下のように対応していることが分かる．

$B^{}B^T=A$ ， $U=V$ ， $\Sigma^{} \Sigma ^T=\Lambda$ ， $U^T=U^{-1}=V^{-1}$

（ $U^T=U^{-1}$ は $U$ が直交基底であることを利用している）

よって， $B$ の特異値分解を行うには， $B^{}B^T$ の固有値分解をすれば良いことが分かる．
$B^{}B^T$ の固有値分解を行って求まった $\Lambda$ が

$\begin{eqnarray} \Sigma \Sigma ^T&=& \begin{pmatrix} \sigma _1 & 0 & \cdots & 0 & \cdots & 0\\ 0 & \sigma _2 & \cdots & 0 & \cdots & 0\\ \vdots & \vdots & \ddots & \vdots & \cdots & \vdots\\ 0 & 0 & \ldots & \sigma _M & \cdots & 0\\ \end{pmatrix} \begin{pmatrix} \sigma _1 & 0 & \cdots & 0\\ 0 & \sigma _2 & \cdots & 0\\ \vdots & \vdots & \ddots & \vdots\\ 0 & 0 & \ldots & \sigma _M\\ \vdots & \vdots & \vdots & \vdots\\ 0 & 0 & \cdots & 0\\ \end{pmatrix}\\ &=&\begin{pmatrix} \sigma _1 ^2 & 0 & \cdots & 0\\ 0 & \sigma _2 ^2& \cdots & 0\\ \vdots & \vdots & \ddots & \vdots\\ 0 & 0 & \ldots & \sigma _M ^2\\ \end{pmatrix} \end{eqnarray}$

なので， $\sigma_m = \sqrt {\lambda_m}$ と対応づけられる．

ここから固有ベクトルを求めて，その大きさが $1$ となるように調整すれば左特異ベクトル $U$ が求められる．

次は $B ^{T}{B^{}}$ を計算してみる．

$B^{T}B^{}=(U \Sigma V^T)^T(U \Sigma V^T) = (V \Sigma ^T U^T)(U \Sigma V^T)=V \Sigma^{T} \Sigma ^{} V^T$

$B ^{T}{B^{}}$ のサイズは $N \times N$ であり，同様に固有値分解を行う．なお，

$\begin{eqnarray} \Sigma ^T \Sigma &=& \begin{pmatrix} \sigma _1 & 0 & \cdots & 0\\ 0 & \sigma _2 & \cdots & 0\\ \vdots & \vdots & \ddots & \vdots\\ 0 & 0 & \ldots & \sigma _M\\ \vdots & \vdots & \vdots & \vdots\\ 0 & 0 & \cdots & 0\\ \end{pmatrix} \begin{pmatrix} \sigma _1 & 0 & \cdots & 0 & \cdots & 0\\ 0 & \sigma _2 & \cdots & 0 & \cdots & 0\\ \vdots & \vdots & \ddots & \vdots & \cdots & \vdots\\ 0 & 0 & \ldots & \sigma _M & \cdots & 0\\ \end{pmatrix} \\ &=&\begin{pmatrix} \sigma _1 ^2 & 0 & \cdots & 0 & \cdots & 0\\ 0 & \sigma _2 ^2& \cdots & 0 & \cdots & 0\\ \vdots & \vdots & \ddots & \vdots & \cdots & 0\\ 0 & 0 & \ldots & \sigma _M ^2 & \cdots & 0\\ \vdots & \vdots & \vdots & \vdots & \ddots & \vdots\\ 0 & 0 & \ldots & 0 & \cdots & 0\\ \end{pmatrix} \end{eqnarray}$

であるので， $\lambda _{M+1}= \cdots = \lambda _{N}=0$ となる．

ここから固有ベクトルを求めて，その大きさが $1$ となるように調整すれば右特異ベクトル $V$ が求められる．

このようにして， $B^{}B^{T}$ 及び $B^{T} B^{}$ をそれぞれ固有値分解することで特異ベクトル及び特異値が求められる．

最後に，特異値分解をすると何が嬉しいのか述べる．

$\begin{eqnarray} B&=&U \Sigma V^T\\ &=&U \begin{pmatrix} \sigma _1 & 0 & \cdots & 0 & \cdots & 0\\ 0 & \sigma _2 & \cdots & 0 & \cdots & 0\\ \vdots & \vdots & \ddots & \vdots & \cdots & \vdots\\ 0 & 0 & \ldots & \sigma _M & \cdots & 0\\ \end{pmatrix} V^T\\ &=& \Biggl( \boldsymbol{u}_1 \ \ \boldsymbol{u}_2 \ \ \cdots \ \ \boldsymbol{u}_M \Biggr) \ \ \begin{pmatrix} \sigma _1 & 0 & \cdots & 0 & \cdots & 0\\ 0 & \sigma _2 & \cdots & 0 & \cdots & 0\\ \vdots & \vdots & \ddots & \vdots & \cdots & \vdots\\ 0 & 0 & \ldots & \sigma _M & \cdots & 0\\ \end{pmatrix} \Biggl( \boldsymbol{v}_1 \ \ \boldsymbol{v}_2 \ \ \cdots \ \ \boldsymbol{v}_N \Biggr)^T\\ &=& \boldsymbol{u}_1 \sigma _1 \boldsymbol{v}_1 ^T + \boldsymbol{u}_2 \sigma _2 \boldsymbol{v}_2 ^T + \cdots + \boldsymbol{u}_M \sigma _M \boldsymbol{v}_M ^T \end{eqnarray}$

式を見てみると $\boldsymbol{u}\boldsymbol{v}^T$ に重み $\sigma$ を掛けて足し合わせた形であり， $\sigma _1 > \sigma _2 \cdots > \sigma _M$ を考慮するとその重みはどんどん小さくなっていく（後ろに行くほど微小量になっていく）．
微小量を足し合わせなくても結果はほぼ変わらないので，以下のように近似出来る．

$\begin{eqnarray} B&=& \boldsymbol{u}_1 \sigma _1 \boldsymbol{v}_1 ^T + \boldsymbol{u}_2 \sigma _2 \boldsymbol{v}_2 ^T + \cdots + \boldsymbol{u}_k \sigma _k \boldsymbol{v}_k ^T + \boldsymbol{u}_{k+1} \sigma _{k+1} \boldsymbol{v}_{k+1} ^T + \cdots + \boldsymbol{u}_M \sigma _M \boldsymbol{v}_M ^T\\ &\approx&\boldsymbol{u}_1 \sigma _1 \boldsymbol{v}_1 ^T + \boldsymbol{u}_2 \sigma _2 \boldsymbol{v}_2 ^T + \cdots + \boldsymbol{u}_k \sigma _k \boldsymbol{v}_k ^T \end{eqnarray}$

このように近似することで， $M$ 次元だったものが $k$ 次元に圧縮された．
次元削減は特徴量を取り出したり計算量を減らしたりすることが出来て嬉しいため，機械学習に応用されている．

yProcessingClub

すみません、許してください

特異値分解をふんわりと理解する