PRML　演習問題  2.19（標準）　解答

## はじめに
本記事は, 機械学習の教科書の決定版ともいえる, **Christopher Bishop先生**による[**『Pattern Recognition and Machine Learning （パターン認識と機械学習）』**](https://www.microsoft.com/en-us/research/people/cmbishop/prml-book/), 通称**PRML**の演習問題のうち, 私が解いた問題の解答を記したものです. これは, 私の所属する[生物測定学研究室](https://www.ut-biomet.org/)の輪読会で**PRML**を取り扱っており, その勉強の一環として演習問題を解いたときのものです. なお, 他の演習問題の解答例に関する記事については, [PRML　演習問題　解答集　まとめ](https://qiita.com/Lab_of_Biomet/items/15e38ca34fafa8176d89)をご覧ください.

## 問題
> 固有ベクトルの方程式について
$$
\begin {align*}
\boldsymbol { \Sigma } \mathbf { u } _ { i } = \lambda _ { i } \mathbf { u } _ { i }
\tag{2.45}
\end{align*}
$$
が成立する実対称行列 $\mathbf { \Sigma }$ は, 固有値を係数とする固有ベクトルで展開した, 
$$
\begin {align*}
\boldsymbol { \Sigma } = \sum _ { i = 1 } ^ { D } \lambda _ { i } \mathbf { u } _ { i } \mathbf { u } _ { i } ^ { \mathrm { T } }
\tag{2.48}
\end{align*}
$$
の形で表せることを示せ. 同様に， 逆行列 $\mathbf { \Sigma } ^ { - 1 }$ は
$$
\begin {align*}
\mathbf { \Sigma } ^ { - 1 } = \sum _ { i = 1 } ^ { D } \frac { 1 } { \lambda _ { i } } \mathbf { u } _ { i } \mathbf { u } _ { i } ^ { \mathrm { T } }
\tag{2.49}
\end{align*}
$$
の形で表現できることを示せ.


## (2.48) 式の証明
この問題は行列表現で考えていくと理解がしやすいです。
まず, (2.48) 式の右辺を行列形式に変形していき,

```math
\begin {align*}
\sum _ { i = 1 } ^ { D }  \lambda _ { i } \mathbf { u } _ { i } \mathbf { u } _ { i } ^ { \mathrm { T } } 
= \mathbf { U } \mathbf { \Lambda } \mathbf { U } ^ { \mathrm { T } }  = \mathbf { M }
\tag{2.19.1}
\end{align*}
```

と定義してみます. ここで, $\mathbf { U }$ は固有ベクトルを横に並べた直交行列で, $\mathbf { \Lambda }$ は対角成分に固有値をもつ対角行列です.
ここで, 行列 $\mathbf { M }$ の左側から $\mathbf { U } ^ { \mathrm { T } }$, 右側から $\mathbf { U }$ をかけると,

```math
\begin {align*}
\mathbf { U }  ^ { \mathrm { T } } \mathbf { M } \mathbf { U } = \mathbf { U } ^ { \mathrm { T } } \left ( \mathbf { U } \mathbf { \Lambda } \mathbf { U } ^ { \mathrm { T } } \right ) \mathbf { U } = \mathbf { \Lambda }
\tag{2.19.2}
\end{align*}
```

が得られます.

一方で, (2.45) 式を行列形式に直して, 左側から $\mathbf { U } ^ \mathrm { T }$ をかけると

```math
\begin {align*}
\mathbf { U } ^ \mathrm { T } \boldsymbol { \Sigma } \mathbf { U } 
& = \mathbf { U } ^ \mathrm { T } \boldsymbol { \Lambda } \mathbf { U } \\
& = \mathbf { U } ^ \mathrm { T } \mathbf { U } \boldsymbol { \Lambda } \\
& = \boldsymbol { \Lambda }
\tag{2.19.3}
\end{align*}
```

となります. したがって, (2.19.2), (2.19.3) 式を比べると,

```math
\begin {align*}
\mathbf { U }  ^ { \mathrm { T } } \mathbf { M } \mathbf { U } = \mathbf { U } ^ \mathrm { T } \boldsymbol { \Sigma } \mathbf { U } 
\tag{2.19.4}
\end{align*}
```

が得られ, 左右からそれぞれ $\mathbf { U }$, $\mathbf { U }  ^ { \mathrm { T } }$ をかけると, $\mathbf { U }$ が直交行列であるため,

```math
\begin {align*}
\mathbf { M } = \boldsymbol { \Sigma }
\tag{2.19.5}
\end{align*}
```

が得られます. よって, (2.48) 式が証明できました.


## (2.49) 式の証明
(2.48) 式の逆行列を考えていくと,

```math
\begin {align*}
\mathbf { \Sigma } ^ { - 1 } 
& = \left ( \mathbf { U } \mathbf { \Lambda } \mathbf { U } ^ { \mathrm { T } } \right ) ^ { - 1 } \\
& = \left ( \mathbf { U } ^ { \mathrm { T } } \right ) ^ { - 1 } \mathbf { \Lambda } ^ { - 1 } \mathbf { U } ^ { - 1 } \\
& = \mathbf { U } \mathbf { \Lambda } ^ { - 1 } \mathbf { U } ^ { \mathrm { T } } \\
& =\sum _ { i = 1 } ^ { D } \frac { 1 } { \lambda _ { i } } \mathbf { u } _ { i } \mathbf { u } _ { i } ^ { \mathrm { T } }
\tag{2.19.6}
\end{align*}
```

より, (2.49) 式が証明できました. なおここで, $\mathbf { U }$ が直交行列であるため, $\mathbf { U } ^ { - 1 } = \mathbf { U } ^ \mathrm { T }$ が成り立つことも用いました.


## 問題の解釈
この問題を証明することで, 実対称行列は, 1度固有値分解を行えば, その固有値と固有ベクトルを利用することで, 逆行列を計算できることがわかります.
例として, 以下に具体的な`R`のスクリプトを示しておきます.

```r:eigenVal.R
##### Sample codes for (2.48) & (2.49) in PRML #####
dimA <- 3
A <- matrix(c(3, 2, 1,            
              2, 4, 3,
              1, 3, 2), 
            nrow = dimA, byrow = TRUE)
print(A)     ### 3 x 3 matrix
#      [,1] [,2] [,3]
# [1,]    3    2    1
# [2,]    2    4    3
# [3,]    1    3    2


#### Eigen decomposition of A
eigenA <- eigen(A)        ### return a list with eigen values and corresponding eigen vectors
eigenVal <- eigenA$values     ### eigen values
eigenVecs <- eigenA$vectors   ### eigen vectors


#### (2.48): Reconstruct the matrix A
checkA <- matrix(0, nrow = dimA, ncol = dimA)    ### prepare an empty box
for (i in 1:dimA){
  checkANow <- eigenVal[i] * tcrossprod(eigenVecs[, i])   
  checkA <- checkA + checkANow
}    ### (2.48)
print(checkA)     ### same as A
#      [,1] [,2] [,3]
# [1,]    3    2    1
# [2,]    2    4    3
# [3,]    1    3    2

#### (2.49): Construct the inverse matrix of A from eigen values & vectors
checkAInv <- matrix(0, nrow = dimA, ncol = dimA)  ### prepare an empty box
for (i in 1:dimA){
  checkAInvNow <- (1 / eigenVal[i]) * tcrossprod(eigenVecs[, i])   
  checkAInv <- checkAInv + checkAInvNow
}    ### (2.49)
print(checkAInv)
#            [,1]       [,2]       [,3]
# [1,]  0.3333333  0.3333333 -0.6666667
# [2,]  0.3333333 -1.6666667  2.3333333
# [3,] -0.6666667  2.3333333 -2.6666667

AInv <- solve(A)   ### inverse of A
print(AInv)        ### same as checkAInv
#            [,1]       [,2]       [,3]
# [1,]  0.3333333  0.3333333 -0.6666667
# [2,]  0.3333333 -1.6666667  2.3333333
# [3,] -0.6666667  2.3333333 -2.6666667
```

この結果を見ると, やはり (2.48), (2.49) 式が正しいことが確認できます.