12
9

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 3 years have passed since last update.

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

Last updated at Posted at 2021-02-26

#はじめに
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)で表されます1

\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}$を求める1

  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)で表されます1

\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)で表されます1

\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)で表されます2

\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}$を求める1

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

  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 3 4 5 6

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

12
9
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
12
9

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?