2020/05/22 23:50 更新
Golden Thompsonの不等式
364 いいね ブックマーク
目次

前提知識

線形代数だけ。ですが、線形代数だけ知ってる人にあまり需要あるとは思いません...

前書き

皆さま、いかがお過ごしでしょうか。ここでは、ぼーっと生きてたらたまたま出会った、Golden Thompsonの不等式について書いていこうと思います。この不等式は統計力学あたりの物理から登場したものらしいですが、物理以外でも大変使いやすそうなものです。ここでは行列バージョンしか紹介しませんが、線形作用素も考えられるので、色々調べてみると面白いかもしれません。

まず

行列の指数関数があります。対称行列の集合を$S_n$、正定値行列の集合を$S_n^+$なんて書いておくことにします。
指数関数$\exp:S_n \rightarrow S_n^+$は

$$\exp(A)=\mathrm{e}^A=\sum_{k=0}^{\infty}\frac{1}{k!}A^k$$

と定義されます。これに関していくつかの性質が知られています。特に今回、注意したいことは、$e^{A}e^{B}$と$e^{A+B}$とは一般的に一致しないことです。有名な話ですね。一致する場合は、行列$A$と$B$が交換可能、つまり$AB=BA$が成立している場合に限られます。

Theorem (Golden Thompsonの不等式)

任意の対称行列$A,B$について、次が成立します。

$$\tag{1} \mathrm{Tr}(e^{A+B}) \leq \mathrm{Tr}(e^Ae^B).$$

この不等式の等号成立は、$AB=BA$のときのみです。

これを示していきたいです。簡単な補題を2つ示します。その2つとLie product formula (リーの積公式)と合わせると示すことができます。単純な見た目とは裏腹、思ったより証明が大変です。線形作用素でも証明は似ている、と思ってます。

Lemma 1

任意の正方行列$X$と自然数$m$に対して、

$$\tag{2} \left| \mathrm{Tr}(X^{2m}) \right| \leq \mathrm{Tr}\{(X^\mathrm{T}X)^{m}\}$$

が成立します。

一見単純に見えますが、実はこの補題が一番大切です。証明方法はいくつかありますが、ここでは帰納法を用いたものを考えます。他にも、関数の凸性を用いた証明もあります。

さて、欲しいのは補題の部分だけなのですが、帰納法による証明をするために、一般化したものを示します。少し長いですが、細かいところを気にしながら頑張るより、一般化した方が分かりやすいし、楽だと思いました。(本当はもっと単純に説明したかったのですが。)

Lemma 1の一般化

$2m$個の正方行列$X_1,...,X_{2m}$があったとき、

$$\tag{3} \left|\mathrm{Tr}(X_1 \cdots X_{2m})\ \right|^{2m} \leq \prod_{i=1}^{2m} \mathrm{Tr}(X_i^\mathrm{T} X_i)^{m}$$

が成立する。

上の$X_i$がすべて同じの$X$であれば、Lemma 1は示されることが分かります。
なんで、こういう風に一般化するの?と思うかもしれません。こうした方が、帰納法を使うときの仮定が強くなるからです。証明を見れば、わかるかもしれません。
まず、$m=1$を確認します。このときは、
トレース内積に関するコーシー·シュワルツの不等式に対応します。
それは、行列$X_1,X_2$に対して

$$\left| \mathrm{Tr}(X_1X_2) \right|^2 \leq \mathrm{Tr}(X_1^\mathrm{T}X_1)Tr(X_2^\mathrm{T}X_2)$$

が成立するというものでした。初見の方は、行列の要素を計算してみるとすぐわかると思います。
この不等式はコーシー·シュワルツの一般化に当たるものだと考えてもよさそうです。つまり、一般の内積で考えることもできます。ただし、今回は、じっくりトレースと付き合っていこうかなと思います。

さて、ある$m$より小さいところで(3)が成立していたと仮定します。
このとき、$2m$を$2$が$m$個あると考えて、仮定より、

$$\begin{aligned} \tag{4}& \left|\mathrm{Tr}((X_1X_2) \cdots (X_{2m-1}X_{2m}))\ \right|^{m} \\ &\leq \prod_{i=1}^{m} \mathrm{Tr}((X_{2i-1}X_{2i})^\mathrm{T} (X_{2i-1}X_{2i}))^{m/2} \end{aligned}$$

が成立します。さらに、もう一回$m=2$で仮定を用いると、

$$\begin{aligned} &\mathrm{Tr}((X_{2i-1}X_{2i})^\mathrm{T} (X_{2i-1}X_{2i}))^4 \\ &\leq \mathrm{Tr}(X_{2i-1} X_{2i-1}^\mathrm{T})^2 \mathrm{Tr}(X_{2i} X_{2i}^\mathrm{T})^2\mathrm{Tr}(X_{2i-1}^\mathrm{T} X_{2i-1})^2\mathrm{Tr}(X_{2i}^\mathrm{T} X_{2i})^2 \\ &=\mathrm{Tr}(X_{2i-1}^\mathrm{T} X_{2i-1})^4 \mathrm{Tr}(X_{2i}^\mathrm{T} X_{2i})^4 \end{aligned}$$

が成り立ちます。$\mathrm{Tr}(AB)=\mathrm{Tr}(BA)$を用いました。少し汚くなりましたが、(4)の右辺の積の中身を、(3)に当てはめただけです。ここで、一般化して帰納法を考えた嬉しさが表れてきました。
結局、

$$\begin{aligned} & \left|\mathrm{Tr}((X_1X_2) \cdots (X_{2m-1}X_{2m}))\ \right|^{m} \\ &\leq \prod_{i=1}^{m} \mathrm{Tr}(X_{2i-1}^\mathrm{T} X_{2i-1})^{m/2} \mathrm{Tr}(X_{2i}^\mathrm{T} X_{2i})^{m/2} \\ &=\prod_{i=1}^{2m} \mathrm{Tr}(X_{i}^\mathrm{T} X_{i})^{m/2} \end{aligned}$$

となり、両辺2乗すれば、証明終了です。やりました。拍手喝采です。

Lemma 2

任意の対称行列$A,B$と自然数$k$に対して、

$$\tag{5} \left| \mathrm{Tr}((AB)^{2^k}) \right| \leq \mathrm{Tr}(A^{2^k}B^{2^k})$$

が成立します。

Lemma 1より簡単にわかります。Lemma 1に$X=AB$,$m=2^{k-1}$を代入していきます。すると、

$$\begin{aligned} \left| \mathrm{Tr}(AB)^{2^k} \right| &\leq \mathrm{Tr}\{(BAAB)^{2^{k-1}}\} \\ &=\mathrm{Tr}(A^2B^2)^{2^{k-1}} \end{aligned}$$

がわかります。さらに、$X=A^2B^2$,$m=2^{k-2}$を代入すると、

$$\begin{aligned} \left| \mathrm{Tr}(A^2B^2)^{2^{k-1}} \right| &\leq \mathrm{Tr}\{(B^2A^2A^2B^2)^{2^{k-2}}\} \\ &=\mathrm{Tr}(A^4B^4)^{2^{k-2}} \end{aligned}$$

となります。あとはこれを繰り返すと、

$$ \left| \mathrm{Tr}(AB)^{2^k} \right| \leq \left| \mathrm{Tr}(A^2B^2)^{2^{k-1}} \right| \leq \cdots \leq \mathrm{Tr}(A^{2^k}B^{2^k})$$

が得られます。完成です。

Theoremの証明

ついにメインの証明です。Lie product formulaを認めればすぐ終わります。Lie product formulaはあとで説明します。
式(5)に、$A$に$e^{\frac{1}{2^k}A}$、$B$に$e^{\frac{1}{2^k}B}$を代入します。すると、

$$\begin{aligned} \mathrm{Tr}(e^{\frac{1}{2^k}A}e^{\frac{1}{2^k}B})^{2^{k}} &\leq \mathrm{Tr}\{(e^{\frac{1}{2^k}A})^{2^k}(e^{\frac{1}{2^k}B})^{2^{k}}\}\\ &=\mathrm{Tr}(e^Ae^B) \end{aligned}$$

を得ることができます。ここで、Lie product formula、リーの積公式というのは、

$$ \lim_{n \to \infty} (e^{\frac{1}{n}A}e^{\frac{1}{n}B})^n=e^{A+B}$$

というものです。雰囲気が超離散化みたいですね。違うけど。
これより、上の不等式で$k$を無限大へ飛ばせば、欲しかった不等式

$$ \mathrm{Tr}(e^{A+B}) \leq \mathrm{Tr}(e^Ae^B)$$

が得られます。
証明の最後に等号成立条件を見ていきたいと思います。Lemma 2の議論から、次のような大小関係があることが見えてきます。

$$ \mathrm{Tr}(e^Ae^B) \geq \mathrm{Tr}(e^{\frac{1}{2}A}e^{\frac{1}{2}B})^2 \geq \cdots \geq \mathrm{Tr}(e^{\frac{1}{2^k}A}e^{\frac{1}{2^k}B})^{2^k}\geq \cdots \geq \mathrm{Tr}(e^{A+B}).$$

これらが全て等号成立している場合を考えます。よって、

$$\begin{aligned} \mathrm{Tr}(e^Ae^B) = \mathrm{Tr}(e^{\frac{1}{2}A}e^{\frac{1}{2}B})^2 &\Leftrightarrow e^{\frac{1}{2}A}e^{\frac{1}{2}B} = e^{\frac{1}{2}B}e^{\frac{1}{2}A}\\ &\Leftrightarrow AB=BA \end{aligned}$$

になります。これで、すべてが示されました。頑張りました。

Lie product formula

$$ \lim_{n \to \infty} (e^{\frac{1}{n}A}e^{\frac{1}{n}B})^n=e^{A+B}.$$

後回しにしたこの積公式を説明していきます。オーダーを考えれば分かってきます。

$$e^{\frac{1}{k}A}=\rm{I} + \frac{1}{k}A + O\left(\frac{1}{k^2}\right)\ , \ e^{\frac{1}{k}B}=\rm{I} + \frac{1}{k}B + O\left(\frac{1}{k^2}\right)$$

が成立しています。これらをかけたものは、

$$e^{\frac{1}{k}A} e^{\frac{1}{k}B}=\rm{I} + \frac{1}{k}A + \frac{1}{k}B + O\left(\frac{1}{k^2}\right)$$

になります。また、

$$e^{\frac{1}{k}(A+B)}=\rm{I} + \frac{1}{k}(A+B) + O\left(\frac{1}{k^2}\right)$$

です。

$$\left| (e^{\frac{1}{k}(A+B)})^k -( e^{\frac{1}{k}A} e^{\frac{1}{k}B})^k \right| \leq \left|e^{\frac{1}{k}(A+B)} - e^{\frac{1}{k}A} e^{\frac{1}{k}B} \right| \left|(e^{\frac{1}{k}(A+B)})^{k-1} + \cdots + ( e^{\frac{1}{k}A} e^{\frac{1}{k}B})^{k-1} \right|$$

より、$k \to \infty$の極限で、右辺は$0$へ行きます。少し細かいところは省略しましたが、これで示されました。線形作用素でも同じような公式が存在し、Lie–Trotter product formulaなど呼ばれているらしいです。

コメント

思ったより長い記事になってしまいました。つらかったです。
さて、次にGT不等式(Golden Thompsonの不等式)の応用例を見ていきましょうか!にはなりません。今回はこれで終了です。本当は見ていきたいのですが、またの記事にさせてください。量子力学で線形作用素のハミルトニアンに対するバウンドや、機械学習における集中不等式ができたりすると期待できます。私が出会ったのは、$\log \det(e^{A+B})$の計算でした。
あと、怪しいところなどございましたら、是非突っ込んでください。ではまた。