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

はじめに

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

E資格試験に関する私の投稿記事リスト

目次

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)はそれぞれ下記の式となります。

\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)に変形できます。

\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}$は下記のようになります。

\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資格試験に関する私の投稿記事リスト

---

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

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