【JDLA E資格】固有値分解・特異値分解

#はじめに
JDLA E資格試験に向け、固有値分解・特異値分解について、まとめた記事です。
E資格試験の応用数学パートでは、特異値分解の問題が出題されます。

[E資格試験に関する私の投稿記事リスト][link-1]
[link-1]:https://qiita.com/fridericusgauss/items/5a97f2645cdcefe15ce0

###目次

1. 固有値分解と特異値分解
2. 固有値分解
3. 特異値分解
4. おわりに

###数学表記
$\mathbb{R}$は実数集合で、bold体の文字はベクトル、あるいは行列です。
ベクトルは全て列ベクトルで、$N$次元ベクトルは$\boldsymbol{x}=(x_{1},x_{2},\cdots,x_{N})^{\mathrm{T}} \in \mathbb{R}^{N}$と表されます。
特に、$\boldsymbol{0}=(0,0,\cdots,0)^{\mathrm{T}}\in \mathbb{R}^{N}$は零ベクトル、$\boldsymbol{O}$は零行列、$\boldsymbol{I}=\mathrm{diag}(1,1,\cdots,1)\in \mathbb{R}^{N\times N}$は単位行列です。

#固有値分解と特異値分解
固有値分解と特異値分解は、任意の行列をある性質を持つ行列の積形式に分解する方法です。
これらはかなり似ていて、どちらも__固有値問題__を解くことで、行列を分解します。
固有値分解は対角化可能な正方行列に対して適用する方法で、特異値分解は非正方行列に対して適用する方法です。

#固有値分解
###固有値問題
固有値問題とは、正方行列$\boldsymbol{A}$について、式(1)の連立方程式を満たす組$\{(\lambda, \boldsymbol{x})\}$を求める問題です。

\boldsymbol{A} \boldsymbol{x}=\lambda \boldsymbol{x}
\tag{1}

ただし、$\boldsymbol{A} \in \mathbb{R}^{N\times N},
\boldsymbol{x} \in \mathbb{R}^{N}, \lambda \in \mathbb{R}$です。
式(1)を満たす$\lambda$を$\boldsymbol{A}$の__固有値__、$\boldsymbol{x}\neq \boldsymbol{0}$を$\boldsymbol{A}$の__固有ベクトル__と呼びます。
つまり、固有値問題を解くことは、固有値と固有ベクトルの組を求めることです。

###固有値分解
__対角化可能な__正方行列$\boldsymbol{A}\in \mathbb{R}^{N\times N}$を固有値分解するとは、$\boldsymbol{A}$を式(2)のように行列分解することです。

\boldsymbol{A}=\boldsymbol{P}\boldsymbol{\Lambda} \boldsymbol{P}^{\mathrm{T}}
\tag{2}

$\boldsymbol{P}\in \mathbb{R}^{N\times N}$は固有ベクトル(単位ベクトル)$\boldsymbol{x}_{n}$$(n=1,2,\cdots,N)$を並べた正規直交行列で、式(3)で表されます¹。

\boldsymbol{P}=[\boldsymbol{x}_{1},
\boldsymbol{x}_{2},\cdots,
\boldsymbol{x}_{N}]
\tag{3}

$\boldsymbol{\Lambda}\in \mathbb{R}^{N\times N}$は固有値$\lambda_{n}(n=1,2,\cdots,N)$を対角要素とする対角行列で、式(4)で表されます。

\boldsymbol{\Lambda}=\mathrm{diag}(\lambda_{1},\lambda_{2},\cdots,\lambda_{N})
\tag{4}

ただし、$\lambda_{n}$は降順に並んでいるとします。

###対角化可能
固有値分解は対角化可能な正方行列にしか適用できません。
なお、E資格試験では、特異値分解しか出題されず、特異値分解は任意の非正方行列に適用可能なので、本節を覚える必要はありません。

対角化とは、正方行列を適切な線型変換を与えることで、元の行列と相似な対角行列に変形することです。
正方行列$\boldsymbol{A}\in \mathbb{R}^{N\times N}$が対角化可能であるとは、式(5)を満たすような正則行列$\boldsymbol{P}\in \mathbb{R}^{N\times N}$と対角行列$\boldsymbol{\Lambda} \in \mathbb{R}^{N\times N}$が存在することです。

\boldsymbol{P}^{-1}\boldsymbol{A}\boldsymbol{P}=\boldsymbol{\Lambda} 
\tag{5}

また、正方行列$\boldsymbol{A}\in \mathbb{R}^{N\times N}$について、下記の命題が成立します。

$\boldsymbol{A}$は互いに線型独立な固有ベクトルを$N$個持つ $\Leftrightarrow$$\boldsymbol{A}$が対角化可能である

つまり、上の条件を満たせば、式(3)の正規直交行列$\boldsymbol{P}$と式(4)の対角行列$\boldsymbol{\Lambda}$が構成できるため、対角化可能です。

よって、__固有値問題を解き、$\boldsymbol{A}$の固有ベクトルを求めれば、$\boldsymbol{A}$が対角化可能かを判定することが可能__です。

###方針
式(1)の固有値問題は式(6)に変形できます。

(\boldsymbol{A} -\lambda \boldsymbol{I}) \boldsymbol{x}=\boldsymbol{0}
\tag{6}

ここで、固有ベクトルは$\boldsymbol{x}\neq \boldsymbol{0}$なので、固有ベクトルが存在することは、式(6)の連立方程式が非自明解を持つことと同値になります。
このためには、下記が必要条件となります。いずれも等価です。

• 行列$\boldsymbol{A} -\lambda \boldsymbol{I}$が正則でない
• 行列$\boldsymbol{A} -\lambda \boldsymbol{I}$の逆行列が存在しない
• 行列$\boldsymbol{A} -\lambda \boldsymbol{I}$の行列式が$0$となる（式(7)）

\mathrm{det}(\boldsymbol{A} -\lambda \boldsymbol{I})=0
\tag{7}

3つ目の条件（式(7)）を__固有方程式__（特性方程式）と呼びます。
このため、固有方程式（式(7)）を満たす$\lambda$が存在すれば、連立方程式（式(6)）を満たす非自明な固有ベクトル$\boldsymbol{x}\neq \boldsymbol{0}$が存在します。

以上から、下記が方針となります。

固有方程式（式(7)）を満たす$\lambda$が固有値であり、そのときに連立方程式（式(6)）を満たす$\boldsymbol{x}\neq \boldsymbol{0}$が固有ベクトルである。

###手順
以上の方針に従い、固有値分解の手順を説明します。

1. 固有方程式（式(7)）を$\lambda$について解き、固有値を求める。
   ここでは、全て異なる実数解であるとし、求めた固有値は$\lambda_{n}(n=1,2,\cdots,N)$とする。

2. 各固有値$\lambda_{n}$を連立方程式（式(6)）に代入し、それを満たす（単位ベクトルの）各固有ベクトル$\boldsymbol{x}_{n}$を求める¹。

3. 固有値と固有ベクトルの組$\{(\lambda_{n}, \boldsymbol{x}_{n})\}$から、正規直交行列$\boldsymbol{P}$（式(3)）、対角行列$\boldsymbol{\Lambda}$（式(4)）を求めた後、式(2)の形式で$\boldsymbol{A}$を行列分解する。

#特異値分解
###特異値問題
特異値問題という呼び方はあまり一般的ではないようですが、本記事では固有値問題と対応させて便宜上使います。
特異値問題とは、非正方行列$\boldsymbol{A}$について、式(8)、式(9)の連立方程式を満たす組$\{(\sigma, \boldsymbol{u},\boldsymbol{v})\}$を求める問題です。

\begin{align}
\boldsymbol{A} \boldsymbol{v}=\sigma \boldsymbol{u}
\tag{8}
\\
\boldsymbol{A}^{\mathrm{T}} \boldsymbol{u}=\sigma \boldsymbol{v}
\tag{9}
\end{align}

ただし、$\boldsymbol{A} \in \mathbb{R}^{M\times N},
\boldsymbol{u} \in \mathbb{R}^{M}, \boldsymbol{v} \in \mathbb{R}^{N}, \sigma \ge 0$です。
式(8)、式(9)を満たす$\sigma$を$\boldsymbol{A}$の__特異値__、$\boldsymbol{u}\neq \boldsymbol{0}$を$\boldsymbol{A}$の__左特異ベクトル__、$\boldsymbol{v}\neq \boldsymbol{0}$を$\boldsymbol{A}$の__右特異ベクトル__と呼びます。
つまり、特異値問題を解くことは、特異値、左特異ベクトル、右特異ベクトルの組を求めることです。
なお、左特異/右特異の名前の由来は特異値分解の式(12)の形式から明らかです。

特異値問題は固有値問題から解かれます。
式(8)、式(9)は式(10)、式(11)に変形できます。

\begin{align}
\boldsymbol{A}^{\mathrm{T}}\boldsymbol{A} \boldsymbol{v}=\sigma^2 \boldsymbol{v}
\tag{10}
\\
\boldsymbol{A}\boldsymbol{A}^{\mathrm{T}} \boldsymbol{u}=\sigma^2 \boldsymbol{u}
\tag{11}
\end{align}

【折り畳み】式(10)、式(11)の導出

>式(8)の両辺に左から$\boldsymbol{A}^{\mathrm{T}}$、式(9)の両辺に左から$\boldsymbol{A}$をかけると、式(8)、式(9)はそれぞれ下記の式となります。 > >```math >\begin{align} >\boldsymbol{A}^{\mathrm{T}}\boldsymbol{A} \boldsymbol{v}=\sigma \boldsymbol{A}^{\mathrm{T}}\boldsymbol{u} \\ >\boldsymbol{A}\boldsymbol{A}^{\mathrm{T}} \boldsymbol{u}=\sigma \boldsymbol{A}\boldsymbol{v} >\end{align} >``` > >各式の右辺にそれぞれ式(8)、式(9)が適用できるため、各式の右辺は式(10)、式(11)に変形できます。 > >```math >\begin{align} >\sigma \boldsymbol{A}^{\mathrm{T}}\boldsymbol{u} = \sigma \cdot \sigma\boldsymbol{v} = \sigma^2 \boldsymbol{v} \\ >\sigma \boldsymbol{A}\boldsymbol{v} = \sigma \cdot \sigma\boldsymbol{u} = \sigma^2 \boldsymbol{u} >\end{align} >``` >

式(10)は、$\boldsymbol{A}^{\mathrm{T}}\boldsymbol{A}$の固有値問題、つまり$\boldsymbol{A}^{\mathrm{T}}\boldsymbol{A}$の固有値$\sigma^2$と固有ベクトル$\boldsymbol{v}$を求める問題です。
また、式(11)は、$\boldsymbol{A}\boldsymbol{A}^{\mathrm{T}}$の固有値問題、つまり$\boldsymbol{A}\boldsymbol{A}^{\mathrm{T}}$の固有値$\sigma^2$と固有ベクトル$\boldsymbol{u}$を求める問題です。
このため、式(10)、式(11)の固有値問題を解けば、特異値$\sigma$、左特異ベクトル$\boldsymbol{u}$、右特異ベクトル$\boldsymbol{v}$を求められます。
したがって、式(10)、式(11)の固有値問題を解くことで、式(8)、式(9)の特異値問題を解くことができます。

###特異値分解
非正方行列$\boldsymbol{A}\in \mathbb{R}^{M\times N}$を特異値分解するとは、$\boldsymbol{A}$を式(12)のように行列分解することです。

\boldsymbol{A}=\boldsymbol{U}\boldsymbol{\Sigma} \boldsymbol{V}^{\mathrm{T}}
\tag{12}

$\boldsymbol{U}\in \mathbb{R}^{M\times M}$は左特異ベクトル(単位ベクトル)$\boldsymbol{u}_{m}$$(m=1,2,\cdots,M)$を並べた正規直交行列で、式(13)で表されます¹。

\boldsymbol{U}=[\boldsymbol{u}_{1},
\boldsymbol{u}_{2},\cdots,
\boldsymbol{u}_{M}]
\tag{13}

$\boldsymbol{V}\in \mathbb{R}^{N\times N}$は右特異ベクトル(単位ベクトル)$\boldsymbol{v}_{n}$$(n=1,2,\cdots,N)$を並べた正規直交行列で、式(14)で表されます¹。

\boldsymbol{V}=[\boldsymbol{v}_{1},
\boldsymbol{v}_{2},\cdots,
\boldsymbol{v}_{N}]
\tag{14}

$\boldsymbol{\Sigma}\in\mathbb{R}^{M\times N}$は非正方行列で、式(15)で表されます。

\boldsymbol{\Sigma} = \left\{
\begin{array}{ll}
\begin{bmatrix}
\boldsymbol{\Delta} & \boldsymbol{O}
\end{bmatrix}
 & ,M < N \\
\boldsymbol{\Delta} & ,M = N \\
\begin{bmatrix}
\boldsymbol{\Delta} \\
\boldsymbol{O}
\end{bmatrix}
 & ,M > N
\end{array}
\right.
\tag{15}

$\boldsymbol{\Delta}\in \mathbb{R}^{Q\times Q}$は特異値$\sigma_{q}(q=1,2,\cdots,Q)$を対角要素とする対角行列で、式(16)で表されます。

\boldsymbol{\Delta}=\mathrm{diag}(\sigma_{1},\sigma_{2},\cdots,\sigma_{Q})
\tag{16}

ただし、$\sigma_{q}$は降順に並んでいるとし、特異値が$r<Q$個ある場合、$\sigma_{r+1}=\sigma_{r+2}=\cdots=\sigma_{Q}=0$とします。
$Q=\min(M,N)$です。

【折り畳み】$\boldsymbol{\Sigma}$の要素の補足

>ここで、$\boldsymbol{\Sigma}$（式(15)）の要素がわかりにくいので補足します。 >特異値$\sigma_{q}$を得た後、式(16)に従い、特異値を対角要素にする$Q\times Q$の対角行列$\boldsymbol{\Delta}$を作ります。 >また、$\boldsymbol{\Sigma}$は$M\times N$の非正方行列です。 >ここで、$Q\le M$かつ$Q\le N$なので、$\boldsymbol{\Sigma}$の中に、$\boldsymbol{\Delta}$が収まります。 >よって、$\boldsymbol{\Sigma}$の左上を基準とし、$\boldsymbol{\Delta}$を配置した後、残りの要素を$0$で埋めることになります。 > >例えば、$\boldsymbol{\Sigma}\in\mathbb{R}^{2\times 3}$のとき、$Q=2$なので、$\boldsymbol{\Delta}$の対角要素は$\sigma_{1},\sigma_{2}$となります。 >このため、$\boldsymbol{\Sigma}$は下記のようになります。 > >```math >\boldsymbol{\Sigma} = >\begin{bmatrix} >\sigma_{1} & 0 & 0\\ >0 &\sigma_{2} & 0 >\end{bmatrix} >``` >

###方針
特異値分解の大きな方針は、式(10)、式(11)の固有値問題を解き、特異値、左特異ベクトル、右特異ベクトルを求めることです。

まず、式(10)、式(11)の固有値問題は式(17)、式(18)に変形できます。

\begin{align}
(\boldsymbol{A}^{\mathrm{T}}\boldsymbol{A}  -\sigma^2 \boldsymbol{I}) \boldsymbol{v}=\boldsymbol{0}
\tag{17}
\\
(\boldsymbol{A}\boldsymbol{A}^{\mathrm{T}}   -\sigma^2 \boldsymbol{I}) \boldsymbol{u}=\boldsymbol{0}
\tag{18}
\end{align}

式(17)に関する固有方程式（式(19)）または、式(18)に関する固有方程式（式(20)）を解けば、$\boldsymbol{A}^{\mathrm{T}}\boldsymbol{A}$または、$\boldsymbol{A}\boldsymbol{A}^{\mathrm{T}}$の固有値$\lambda=\sigma^2$が求められます。

\begin{align}
\mathrm{det}(\boldsymbol{A}^{\mathrm{T}}\boldsymbol{A}  -\sigma^2 \boldsymbol{I}) =0
\tag{19}
\\
\mathrm{det}(\boldsymbol{A}\boldsymbol{A}^{\mathrm{T}}   -\sigma^2 \boldsymbol{I}) =0
\tag{20}
\end{align}

そして、$\boldsymbol{A}$の特異値は$\sigma>0$なので、$\boldsymbol{A}^{\mathrm{T}}\boldsymbol{A}$または$\boldsymbol{A}\boldsymbol{A}^{\mathrm{T}}$の固有値$\lambda$を用いて、式(21)で表されます²。

\sigma=\sqrt{\lambda}, \lambda>0
\tag{21}

このため、__$\boldsymbol{A}$の特異値$\sigma$は、固有方程式（式(19)または式(20)）を解けば、求めることが可能__です。

次に、求めた$r$個の各特異値$\sigma$を用いて、__式(17)と式(18)の連立方程式を解けば、右特異ベクトル$\boldsymbol{v}\neq \boldsymbol{0}$と左特異ベクトル$\boldsymbol{u}\neq \boldsymbol{0}$を求めることが可能__です。

以上から、下記が方針となります。

$\boldsymbol{A}^{\mathrm{T}}\boldsymbol{A}$または$\boldsymbol{A}\boldsymbol{A}^{\mathrm{T}}$の固有方程式（式(19)または式(20)）を満たす固有値$\lambda$と式(21)で対応する$\sigma$が$\boldsymbol{A}$の特異値であり、 そのときに連立方程式（式(17)）を満たす$\boldsymbol{v}\neq \boldsymbol{0}$が右特異ベクトル、連立方程式（式(18)）を満たす$\boldsymbol{u}\neq \boldsymbol{0}$が左特異ベクトルである。

###手順
以上の方針に従い、特異値分解の手順を説明します。

1. 固有方程式（式(19)または式(20)）を$\lambda$について解き、$\boldsymbol{A}^{\mathrm{T}}\boldsymbol{A}$または$\boldsymbol{A}\boldsymbol{A}^{\mathrm{T}}$の固有値$\lambda_{n}$を求める。

2. 式(21)を用いて、各固有値$\lambda_{n}$に対応する各特異値$\sigma_{n}（n=1,2,\cdots,r）$を求める。

3. 各特異値$\sigma_{n}$を連立方程式（式(17)）に代入し、それを満たす（単位ベクトルの）各右特異ベクトル$\boldsymbol{v}_{n}$を求める¹。

4. 各特異値$\sigma_{m}$を連立方程式（式(18)）に代入し、それを満たす（単位ベクトルの）各左特異ベクトル$\boldsymbol{u}_{m}$を求める¹。

5. 特異値、左特異ベクトル、右特異ベクトルの組から、正規直交行列$\boldsymbol{U}$（式(13)）、$\boldsymbol{V}$（式(14)）、非対角行列$\boldsymbol{\Sigma}$（式(15)）を求めた後、式(12)の形式で$\boldsymbol{A}$を行列分解する。

#おわりに
E資格向けの固有値分解・特異値分解について解説しました。
なお、上記は、2021年2月時点における内容であることにご注意ください。

また、2021年3月5日に固有値分解の説明でご指摘をいただきましたので、一部修正しました。

[E資格試験に関する私の投稿記事リスト][link-1]

1. 本来、ある固有値に対応する固有ベクトルは無限に存在するが、E資格試験で出題される場合は単位ベクトル(正規化済)の固有ベクトル（$\|\boldsymbol{x}_{n}\|=1$）が使用されます。 ↩ ↩² ↩³ ↩⁴ ↩⁵ ↩⁶

2. 固有値が負のとき$\sigma$が虚数となるため、負の固有値に対応する特異値はない。 ↩