固有値分解と特異値分解

## 目標
固有値分解と特異値分解を比較しながら理解する．
必要な前提知識についてもまとめる．

## 固有値と固有ベクトル
$A$を$n$次正方行列，$\lambda$をスカラー，$\boldsymbol{x}$をゼロベクトルではない$n$次元ベクトルとする．このとき，

```math
A\boldsymbol{x}=\lambda\boldsymbol{x}\quad\cdots(1)
```

を満たす$\lambda$を行列$A$の固有値，$\boldsymbol{x}$を$\lambda$に対応した固有ベクトルという．

## 固有値と固有ベクトルの求め方
(1)式を変形すると，

```math
(A-\lambda I_n)\boldsymbol{x}=\boldsymbol{0}\quad\cdots(2)
```
という式が得られる．
行列$(A-\lambda I_n)$が逆行列を持つ場合は，(2)式の両辺に左から$(A-\lambda I_n)^{-1}$をかけて，$\boldsymbol{x}=\boldsymbol{0}$となってしまう．
よって固有ベクトル$\boldsymbol{x}\,\neq\boldsymbol{0}$が存在するためには，行列$(A-\lambda I_n)$が逆行列を持たない，すなわち

```math
|A-\lambda I_n|=0\quad\cdots(3)
```

である必要がある．(3)式を行列$A$の固有方程式という．
(3)式を詳しく見ると，

```math
\left|\begin{matrix}
a_{11}-\lambda&\cdots&a_{1n}\\
\vdots&\ddots&\vdots\\
a_{n1}&\cdots&a_{nn}-\lambda\\
\end{matrix}\right|
=0
```

となり，左辺の行列式は$\lambda$の$n$次式となる．
(3)の固有方程式を$\lambda$について解くことで，重解を含めて$n$個の固有値$\lambda_1,\cdots,\lambda_n$を得ることができる．

続いて，$\lambda_i$を(2)式に代入すると，

```math
\left(\begin{matrix}
a_{11}-\lambda_i&\cdots&a_{1n}\\
\vdots&\ddots&\vdots\\
a_{n1}&\cdots&a_{nn}-\lambda_i\\
\end{matrix}\right)
\left(\begin{matrix}
x_{1i}\\
\vdots\\
x_{ni}\\
\end{matrix}\right)
=0
```

となる．
(固有値$\lambda_i$に対応した固有ベクトルの成分の意味で$x$の添え字に$i$を付けた．)
これは$x_{1i}, \cdots, x_{ni}$の連立方程式

```math
\begin{cases}
\begin{alignat}{3}
&(a_{11}-\lambda_i)x_{1i} &+a_{12}x_{2i} &+\cdots &+a_{1n}x_{ni} &= 0\\
& & &\vdots & & \\
&a_{n1}x_{1i} &+a_{n2}x_{2i} &+\cdots &+(a_{nn}-\lambda_i)x_{ni} &= 0\\
\end{alignat}
\end{cases}
```
と見ることができる．
これを解いて$x_{1i}, \cdots, x_{ni}$を求めることで，行列$A$の固有値$\lambda_i$に対応する固有ベクトル$\boldsymbol{x_i}=(x_{1i}, \cdots, x_{ni})^T$を得られる．
実際には行列の形のまま掃き出し法を使うと便利．
$\lambda_1,\cdots,\lambda_n$に渡って同じ操作を繰り返せば，各固有値に対応する固有ベクトル$\boldsymbol{x_1},\cdots,\boldsymbol{x_n}$を得ることができる．

## 行列の対角化
$n$次正方行列$A$に，$n$本の線形独立な固有ベクトル$\boldsymbol{x_1},\cdots,\boldsymbol{x_n}$がある場合を考える．
なお，異なる固有値に対応する固有ベクトルは線形独立であるため，$A$の固有値が全て異なれば$n$本の線形独立な固有ベクトルを得ることができる．
（固有ベクトルの本数は，1以上，対応する固有値の重複度以下の範囲で得られるため，固有値に重解があっても対角化可能な場合はある．）

この条件下で，$n$組の固有値と固有ベクトルについて行列とベクトルを使って(1)式をまとめて表してみると，

```math
A(\boldsymbol{x_1},\cdots,\boldsymbol{x_n})=(\boldsymbol{x_1},\cdots,\boldsymbol{x_n})
\left(\begin{matrix}
\lambda_1& &0\\
 &\ddots& \\
0& &\lambda_n
\end{matrix}\right)\,\cdots(4)
```

と表現できる．
ここで$P=(\boldsymbol{x_1},\cdots,\boldsymbol{x_n})$とおくと($P$は$n\times n$行列)，$P$の列ベクトル$\boldsymbol{x_1},\cdots,\boldsymbol{x_n}$は線形独立であるから，$P$は正則行列である．
よって，$P$は逆行列$P^{-1}$を持ち，(4)式の両辺に左から$P^{-1}$をかけると，

```math
P^{-1}AP=
\left(\begin{matrix}
\lambda_1& &0\\
 &\ddots& \\
0& &\lambda_n
\end{matrix}\right)\,\cdots(5)
```
のように行列$A$を対角化できる．このとき行列$P$を変換行列と呼ぶ．

なお一般に，$n$次正方行列$A,B$について正則行列$P$が存在し，$P^{-1}AP=B$という関係が成り立つとき，$A$と$B$は相似であるという．相似変換では行列のランク，トレース，行列式，固有方程式，固有値は変わらないという性質がある．

## 固有値分解
行列の対角化のさらに特別な条件について考えてみる．
ここでは行列$A$を$n$次対称行列とする．$A$が対称行列のとき，$A$の固有ベクトル$\boldsymbol{x_1},\cdots,\boldsymbol{x_n}$は全て互いに直交するように取ることができる．さらにノルムが1になるように取ると，(5)式の$P$は直交行列となる．
そこで，$A$の正規直交な$n$本の固有ベクトルを$\boldsymbol{h_1},\cdots,\boldsymbol{h_n}$，変換行列を$H=(\boldsymbol{h_1},\cdots,\boldsymbol{h_n})$とおくと，$H$は直交行列であるから$H^{-1}=H^T$となる．よって(5)式より，$n$次対称行列$A$は

```math
H^TAH=
\left(\begin{matrix}
\lambda_1& &0\\
 &\ddots& \\
0& &\lambda_n
\end{matrix}\right)(=\Lambda)
```
と対角化できる．さらに両辺に左から$H$，右から$H^T$をかけて，右辺を具体的に計算してやることで，

```math
A=H\Lambda H^T=\lambda_1\boldsymbol{h_1}\boldsymbol{{h_1}}^T+\cdots+\lambda_n\boldsymbol{h_n}\boldsymbol{{h_n}}^T\quad\cdots(6)
```
という変形ができる．これを行列$A$の固有値分解という．

## 特異値分解
詳細な導出は難しいため，ここでは大まかな理解を目指す．

固有値分解は対称行列に対して施せる変換であった．一方で特異値分解は任意の$n\times m$行列に対して適用することができる．
固有値分解と特異値分解は非常によく似た操作であるため，これらを比較しながら理解をすると良い．

まずは特異値の定義を確認する．
任意の$n\times m$行列$X$に対して，$\mathrm{rank}X=r$，$\mathrm{min}(n,m)=l$，対称行列$XX^T$，$X^TX$の固有値を$\lambda_1,\cdots,\lambda_n$とする．なお，対称行列の固有値は非負である．このとき，

```math
\sigma_i=\sqrt{\lambda_i}\,(i=1,\cdots,r),\,\sigma_k=0\,(k=r+1,\cdots,l)
```
を$X$の特異値という．

続いて特異値分解の定義を確認する．
任意の$n\times m$行列$X$に対して，$\sigma_i$を$X$の特異値とする．$n\times n$直交行列$U$，$m\times m$直交行列$V$によって，行列$X$を次のように変換することを特異値分解という．

```math
X=U\Sigma V^T
```
行列$U$の列ベクトルを左特異ベクトル，$V$の列ベクトルを右特異ベクトルという．また$n\times m$行列$\Sigma$は

```math
\Sigma=
\left(\begin{matrix}
\sigma_1&0&\cdots&0&0&\cdots&0\\
0&\sigma_2&\cdots&0&0&\cdots&0\\
\vdots&\vdots&\ddots&\vdots&\vdots& &\vdots\\
0&0&\cdots&\sigma_r&0&\cdots&0\\
0&0&\cdots&0&0&\cdots&0\\
\vdots&\vdots& &\vdots&\vdots& &\vdots\\
0&0&\cdots&0&0&\cdots&0\\
\end{matrix}\right)
```
のように，対角成分に$X$の特異値が$\sigma_i\geq\sigma_{i+1}$の順に並んだ対角行列である．$\mathrm{rank}X+1$行(列)目以降の対角成分は$0$であり，特異値の定義$\sigma_k=0\,(k=r+1,\cdots,l)$と一致する．

ではここで，特異値分解の定義を応用して$XX^T$を計算してみると，

```math
XX^T=U\Sigma V^T(U\Sigma V^T)^T=U\Sigma V^TV\Sigma U^T=U\Sigma\Sigma^TU^T
```
という式を得ることができる．これを固有値分解の(6)式と並べてみる．

```math
\begin{align}
A&=H\Lambda H^T\\[5pt]
XX^T&=U\Sigma\Sigma^TU^T
\end{align}
```
$XX^T$は$n$次対称行列となるので行列$A$に対応し，$U$は$n\times n$直交行列であるから$H$に対応する．そして，$\Sigma\Sigma^T$は$A$の固有値が対角成分に並んだ行列$\Lambda$に対応することがわかる．ここからも，$\sigma_i=\sqrt{\lambda_i}$であることがわかる．

以上から，$XX^T$の固有値分解により，$X$の特異値と左特異ベクトルを列ベクトルに持つ直交行列$U$を求めることができる．すなわち，$XX^T$の正規直交する$n$本の固有ベクトルを求め，対応する固有値が大きい順に並べた行列が$U$となる．

同様の手順で$X^TX$を計算すると，

```math
X^TX=V\Sigma\Sigma^TV^T
```
となり，こちらは右特異ベクトルを列ベクトルに持つ行列$V$を求めることができる．

## 参考
講談社サイエンティフィク　[データサイエンスのための数学](https://www.kspub.co.jp/book/detail/5169988.html)