特異値分解について

# はじめに
今年の内容としましては、特異値分解（SVD）について簡単に勉強したことを共有したいと思います。
だいぶ前に公開したつもりになっていたのですが、全然記事も書いていないしその記憶自体が嘘だったのでびっくりして今これを書いています。

# 番宣
[Supership](https://supership.jp/)ではプロダクト開発やサービス開発に関わる人を絶賛募集しております。
ご興味がある方は以下リンクよりご確認ください。
[Supership株式会社 採用サイト](https://supership.jp/recruit/)
是非ともよろしくお願いいたします。


# 特異値分解について
まず、特異値分解というのは行列を積に分解する手法の一つです。
行列を積に分解する方法として固有値分解なんかは線形代数を学ぶ上で最初に通るものとして出てきますが、それっぽいやつです。

定理:
任意の$n$行$m$列の行列$A$に対して$A$は次のように分解できる。
```math
A = USV^T
```
ここで、 $U$, $V$ は直行行列で、 $V^T$は $V$ の転置行列を表す。
また、
```math
S = 
\begin{pmatrix}
\sigma_1 & 0        &  \dots & 0 \\
0        & \sigma_2 &        &   \\
\vdots   &          & \ddots & \vdots \\
0        & 0        & \dots  & \sigma_k \\
\end{pmatrix}
```
と $S$ は対角成分以外が$0$になる対角行列で表すことができる。


ちなみに、 $U$ が直行行列というのは、$E$を単位行列とする時、 $U U^T = E$ を満たす行列のことです。


実際に例を見てみます。

```math
A = 
\begin{pmatrix}
2 & 2 & 2 & 2 \\
1 & -1 & 1 & -1 \\
-1 & 1 & -1 & 1 \\
\end{pmatrix}
```
として、分解を計算してみると

```math
\begin{eqnarray}
A &=& 
\begin{pmatrix}
1 & 0 & 0 \\
0 & \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}} \\
0 & -\frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}} \\
\end{pmatrix}

\begin{pmatrix}
4 & 0 & 0 & 0 \\
0 & 2\sqrt{2} & 0 & 0 \\
0 & 0 & 0 & 0 \\
\end{pmatrix}

\begin{pmatrix}
\frac{1}{2} & \frac{1}{2}  & \frac{1}{2}  & \frac{1}{2}  \\
\frac{1}{2} & -\frac{1}{2}  & \frac{1}{2}  & -\frac{1}{2}  \\
\frac{1}{2} & \frac{1}{2}  & -\frac{1}{2}  & -\frac{1}{2}  \\
\frac{1}{2} & -\frac{1}{2}  & -\frac{1}{2}  & \frac{1}{2}  \\
\end{pmatrix} \\

&=& USV^T
\end{eqnarray}
```
と分解できます。
この計算はこちらの記事を参考にさせていただきました。
[特異値分解による低ランク近似](https://qiita.com/Takayoshi_Makabe/items/148e4de221176a6eac50)

ここで$S$という行列のサイズは好きに変更することができますが、$U$と$V$は$A$ の行列のサイズに由来する正方行列になります。
今回は $A$ が 3行4列の行列だったので、$U$が$3\times 3$の正方行列、 $V$ が$4\times 4$の正方行列となっています。


この$S$を特異値行列といい、対角成分に出ている $4$ とか $2\sqrt{2}$ が特異値です。
普通は特異値分解では特異値が大きい順番で上から並べていきます。
（基底を適当に変換することで可能ですが、）


# これ何が嬉しいの？
活用方法は様々ですが、よく言われている例が次元圧縮です。
いろんなデータに対して次元圧縮を行っている記事が世の中にたくさんあるのですが、画像とかレコメンドで見かけることが多い印象です。

次元圧縮をどうやって行うのかをみていきます。

```math
\begin{eqnarray}
A &=& USV^T \\
 &=& U 
\begin{pmatrix}
\sigma_1 & 0        &  \dots & 0 \\
0        & \sigma_2 &        &   \\
\vdots   &          & \ddots & \vdots \\
0        & 0        & \dots  & \sigma_k \\
\end{pmatrix} 
V^T \\
 &=& U 
\begin{pmatrix}
\sigma_1 & 0        &  \dots & 0 \\
0        & 0 &        &   \\
\vdots   &          & \ddots & \vdots \\
0        & 0        & \dots  & 0 \\
\end{pmatrix}V^T + 
U
\begin{pmatrix}
0 & 0        &  \dots & 0 \\
0        & \sigma_2 &        &   \\
\vdots   &         & \ddots & \vdots \\
0        & 0        & \dots  & 0 \\
\end{pmatrix} 
V^T  + \ldots  \\

&=& 
\sigma_1
\begin{pmatrix}
u_{11} & 0        &  \dots & 0 \\
u_{21}        & 0 &        &   \\
\vdots   &         & \ddots & \vdots \\
u_{n1}        & 0        & \dots  & 0 \\
\end{pmatrix} V^T
+
\sigma_2 
\begin{pmatrix}
0 & u_{12}        &  \dots & 0 \\
0        & u_{22} &        &   \\
\vdots   &         & \ddots & \vdots \\
0        & u_{n2}        & \dots  & 0 \\
\end{pmatrix} 
V^T  + \ldots 
\end{eqnarray}
```

と特異値のところを展開して和の形にすることができます。
これをテイラー展開みたいな感じで、途中で打ち切っちゃうと、Aの近似行列が得られて、次元が圧縮されるという感じです。

# 最後に
こういう数学の定理によくあるのが、応用方法がよく分からないという点があると思います。
僕の場合ですが、数学なんかを学習していて、これなんに使うの？と思った途端にモチベーションが下がることが結構あります。
上手くモチベーションを保てるように先に応用を見てやる気のある内に済ませたいものですね（それはなかなか上手くいかないのですが）