エンジニアを目指す浪人のブログ

情報系に役立ちそうな応用数理をゆるめにメモします

行列式の対数はその行列の凹関数であることを証明する

数学 数理最適化

本記事は以下の過去記事の結果を用います．

n次元ユークリッド空間上の関数が凸であるための必要十分条件は定義域内の任意の直線上で凸であることの証明をメモする - エンジニアを目指す浪人のブログ


本記事は以下の過去記事と関連しています．

いくつかの行列の公式を証明するその3 - エンジニアを目指す浪人のブログ


勉強を進めていて，行列式(determinant)の対数が凹(concave)であることを知りました．その証明を調べてメモしておくことにしました．文献[1][2][3]を参考にしてまとめます．


問題を設定するため，いくつか準備をします．

本記事で扱う行列，ベクトルの要素はすべて実数であるとします．

記号を準備します．

{\displaystyle I \;\;\;\;\;\;\;\; n \times n } 単位行列
{\displaystyle \mathbf{S}^n \;\;\;\;\;\; n \times n } 対称行列の集合
{\displaystyle \mathbf{S}_{+}^n \;\;\;\;\;\; n \times n } 半正定値行列の集合
{\displaystyle \mathbf{S}_{++}^n \;\;\;\; n \times n } 正定値行列の集合


凹関数の定義は文献[4]にあります．

正定値の定義は文献[5]にあります．

直交行列の定義は文献[6]にあります．


よく知られている以下の3つの事実を証明なしで用います(それぞれ例えば文献[5][7][8]にあります)．

事実0.1.
あらゆる正定値行列は正則であり，逆行列もまた正定値である．

事実0.2.
{\displaystyle \;\;\; \mathrm{det} \left( A B \right) = \mathrm{det} A \ \mathrm{det} B }

事実0.3.

あらゆる実対称行列 {\displaystyle A \ \left( = A^T \right) } について以下をみたすような直交行列 {\displaystyle P} が存在する．{\displaystyle \alpha_1,\ldots, \alpha_n } は {\displaystyle A } の固有値である．

{\displaystyle \;\;\; \mathrm{diag} \left( \alpha_1,\ldots, \alpha_n \right) = P^T A P }


あまり知られていないように思いますが，以下の事実を証明なしで用います(例えば文献[9]にあります)．

事実0.4.

あらゆる正定値行列 {\displaystyle A } について {\displaystyle A = B^2} をみたすような正定値行列 {\displaystyle B = A^{1/2}} がただ一つ存在する．{\displaystyle A^{1/2}} を行列 {\displaystyle A} の平方根行列(square root of a matrix)という．事実0.1.より {\displaystyle A^{1/2}} の逆行列 {\displaystyle A^{-1/2}} が存在し，これも正定値である．


以上の設定のもとで，本記事の目的に進みます．

'--------------------------------------------------------------------------------------------------------------------------------------------
事実1.

以下の関数 {\displaystyle f } は凹である．

{\displaystyle \;\; f : \mathbf{S}_{++}^{n} \to \mathbf{R} \;\;\; f : X \mapsto \log \left( \mathrm{det} X \right) }


証明.

{\displaystyle \mathbf{S}_{++}^n \subset \mathbf{S}_{+}^n \subset \mathbf{S}^n } である．{\displaystyle Z, V \in \mathbf{S}^n } とし，関数 {\displaystyle g(t) = f( Z + t V ) } とする．{\displaystyle t } は行列 {\displaystyle Z + t V } が正定値となる範囲に制限する．一般性を失わずに {\displaystyle t=0} はこのような範囲に含まれるようにできることから，{\displaystyle Z \in \mathbf{S}_{++}^n } としてよい．

冒頭の過去記事(n次元ユークリッド空間上)定理3はベクトルではなく行列にも適用可能(証明のベクトルを行列に入れかえても成り立つ)であるので，以下の命題が成り立つ．

(a){\displaystyle \;\;\; f : \mathbf{S}_{++}^{n} \to \mathbf{R} \; } は凹である
{\displaystyle \;\;\;\;\;\; \Leftrightarrow }
(b){\displaystyle \;\;\; g : \mathbf{R} \to \mathbf{R} \;\;\; g : t \mapsto f( Z + tV ), \; \ \mathrm{dom} \ g = \{ t : Z + t V \in \mathrm{dom} \ f \; ( = \mathbf{S}_{++}^{n} ) \} } は任意の {\displaystyle \;\;\;\;\;\; Z \in \mathbf{S}_{++}^{n}, } {\displaystyle V \in \mathbf{S}^{n} } について凹である


以降，(b)を示す．

{\displaystyle \;\;\; g(t) = f( Z + t V ) }

{\displaystyle \;\;\;\;\;\;\;\;\;\; = \log \mathrm{det} \left( Z + t V \right) }

{\displaystyle \;\;\;\;\;\;\;\;\;\; = \log \mathrm{det} \left( Z^{ 1/2 } Z^{ 1/2 } + t \ Z^{ 1/2 } Z^{ -1/2 } V Z^{ -1/2 } Z^{ 1/2 } \right) \;\;\;\; \because } 事実0.4.

{\displaystyle \;\;\;\;\;\;\;\;\;\; = \log \mathrm{det} \left( Z^{ 1/2 } \left( I + t \ Z^{ -1/2 } V Z^{ -1/2 } \right) Z^{ 1/2 } \right) }

{\displaystyle \;\;\;\;\;\;\;\;\;\; = \log \left[ \mathrm{det} Z^{ 1/2 } \ \mathrm{det} \left( I + t \ Z^{ -1/2 } V Z^{ -1/2 } \right) \mathrm{det} Z^{ 1/2 } \right] \;\;\; \because } 事実0.2.

{\displaystyle \;\;\;\;\;\;\;\;\;\; = \log \left[ \mathrm{det} \left( I + t \ Z^{ -1/2 } V Z^{ -1/2 } \right) \mathrm{det} Z^{ 1/2 } \ \mathrm{det} Z^{ 1/2 } \right] }

{\displaystyle \;\;\;\;\;\;\;\;\;\; = \log \left[ \mathrm{det} \left( I + t \ Z^{ -1/2 } V Z^{ -1/2 } \right) \mathrm{det} \left( Z^{ 1/2 } Z^{ 1/2 } \right) \right] \;\;\;\; \because } 事実0.2.

{\displaystyle \;\;\;\;\;\;\;\;\;\; = \log \left[ \mathrm{det} \left( I + t \ Z^{ -1/2 } V Z^{ -1/2 } \right) \mathrm{det} Z \right] }

{\displaystyle \;\;\;\;\;\;\;\;\;\; = \log \mathrm{det} \left( I + t \ Z^{ -1/2 } V Z^{ -1/2 } \right) + \log \mathrm{det} Z \;\;\;\;\;\; } (※)


行列 {\displaystyle Z^{ -1/2 } V Z^{ -1/2 } } の固有値を {\displaystyle \lambda_1,\ldots,\lambda_n } とする．事実0.4.より {\displaystyle Z^{ -1/2 } } は正定値なので対称行列であり，{\displaystyle V \in \mathbf{S}^n } とから {\displaystyle Z^{ -1/2 } V Z^{ -1/2 } } は対称行列であるので，事実0.3.より以下をみたす直交行列 {\displaystyle Q } が存在する．

{\displaystyle \;\;\; Z^{ -1/2 } V Z^{ -1/2 } = Q^T \Lambda Q, \;\;\; \Lambda = \mathrm{diag} \left( \lambda_1,\ldots, \lambda_n \right) }


これを用いて以下を得る．

(※)
{\displaystyle \;\;\;\;\;\;\;\;\;\; = \log \mathrm{det} \left( I + t \ Q^T \Lambda Q \right) + \log \mathrm{det} Z }

{\displaystyle \;\;\;\;\;\;\;\;\;\; = \log \mathrm{det} \left( Q^T Q + t \ Q^T \Lambda Q \right) + \log \mathrm{det} Z \;\;\;\;\;\;\;\; \because } 直交行列

{\displaystyle \;\;\;\;\;\;\;\;\;\; = \log \mathrm{det} \left( Q^T \left( I + t \Lambda \right) Q \right) + \log \mathrm{det} Z }

{\displaystyle \;\;\;\;\;\;\;\;\;\; = \log \left[ \mathrm{det} Q^T \mathrm{det} \left( I + t \Lambda \right) \mathrm{det} Q \right] + \log \mathrm{det} Z \;\;\; \because } 事実0.2.

{\displaystyle \;\;\;\;\;\;\;\;\;\; = \log \left[ \mathrm{det} Q^T \mathrm{det} Q \ \mathrm{det} \left( I + t \Lambda \right) \right] + \log \mathrm{det} Z }

{\displaystyle \;\;\;\;\;\;\;\;\;\; = \log \left[ \mathrm{det} \left( Q^T Q \right) \ \mathrm{det} \left( I + t \Lambda \right) \right] + \log \mathrm{det} Z \;\;\; \because } 事実0.2.

{\displaystyle \;\;\;\;\;\;\;\;\;\; = \log \left[ \mathrm{det} \left( I \right) \ \mathrm{det} \left( I + t \Lambda \right) \right] + \log \mathrm{det} Z \;\;\;\;\;\;\;\;\;\; \because } 直交行列

{\displaystyle \;\;\;\;\;\;\;\;\;\; = \log \mathrm{det} \left( I + t \Lambda \right) + \log \mathrm{det} Z }

{\displaystyle \;\;\;\;\;\;\;\;\;\; = \log \mathrm{det} \left( I + t \ \mathrm{diag} \left( \lambda_1,\ldots, \lambda_n \right) \right) + \log \mathrm{det} Z }

{\displaystyle \;\;\;\;\;\;\;\;\;\; = \log \mathrm{det} \left( I + \mathrm{diag} \left( t \lambda_1,\ldots, t \lambda_n \right) \right) + \log \mathrm{det} Z }

{\displaystyle \;\;\;\;\;\;\;\;\;\; = \log \mathrm{det} \ \mathrm{diag} \left( 1 + t \lambda_1,\ldots, 1 + t \lambda_n \right) + \log \mathrm{det} Z }

{\displaystyle \;\;\;\;\;\;\;\;\;\; = \log \prod_{i=1}^n \left( 1 + t \lambda_i \right) + \log \mathrm{det} Z }

{\displaystyle \;\;\;\;\;\;\;\;\;\; = \sum_{i=1}^n \log \left( 1 + t \lambda_i \right) + \log \mathrm{det} Z }


{\displaystyle \;\;\; g(t) = \sum_{i=1}^n \log \left( 1 + t \lambda_i \right) + \log \mathrm{det} Z }

{\displaystyle \;\;\; g'(t) = \sum_{i=1}^n \frac{ \left( 1 + t \lambda_i \right)' }{1 + t \lambda_i} = \sum_{i=1}^n \frac{ \lambda_i }{1 + t \lambda_i} }

{\displaystyle \;\;\; g''(t) = \sum_{i=1}^n \frac{ - \left( 1 + t \lambda_i \right)' \lambda_i }{ \left( 1 + t \lambda_i \right)^2 } = \sum_{i=1}^n \frac{ - \lambda_i^2 }{ \left( 1 + t \lambda_i \right)^2 } \le 0 }


したがって {\displaystyle g(t) } は凹であり(b)が成り立つ．さらに上の命題より(a)が成り立つ．(証明終わり)

'--------------------------------------------------------------------------------------------------------------------------------------------


以上，行列式の対数はその行列の凹関数であることを証明しました．



参考文献
[1] Boyd, S., and Vandenberghe, L. (2004), Convex Optimization, Cambridge University Press.
[2] University of California, Los Angeles Quanquan Gu先生のノート https://piazza-resources.s3.amazonaws.com/is58gs5cfya7ft/itawqt5undn2bv/lecture8.pdf
[3] Mathematics Stack Exchange https://math.stackexchange.com/questions/1192329/log-determinant-concavity-proof
[4] Wikipedia Convex function のページ https://en.wikipedia.org/wiki/Convex_function
[5] Wikipedia Definiteness of a matrix のページ https://en.wikipedia.org/wiki/Definiteness_of_a_matrix
[6] Wikipedia Orthogonal matrix のページ https://en.wikipedia.org/wiki/Orthogonal_matrix
[7] Wikipedia Determinant のページ https://en.wikipedia.org/wiki/Determinant
[8] Wikipedia Symmetric matrix のページ https://en.wikipedia.org/wiki/Symmetric_matrix#Real_symmetric_matrices
[9] Wikipedia Square root of a matrix のページ https://en.wikipedia.org/wiki/Square_root_of_a_matrix