マトリックス チェルノフ境界

線形代数の特定の用途では、ランダム行列の有限和の最大固有値の確率分布の特性を知っておくと便利です。 はランダム行列の有限シーケンスであるとします。よく知られているスカラーの和のチェルノフ境界と同様に、与えられたパラメータtに対して次の境界が求められます 。 ${\displaystyle \{\mathbf {X} _{k}\}}$

${\displaystyle \Pr \left\{\lambda _{\max }\left(\sum _{k}\mathbf {X} _{k}\right)\geq t\right\}}$

以下の定理は、さまざまな仮定の下でこの一般的な質問に答えます。これらの仮定は、古典的なスカラーの対応物との類推によって以下で名前が付けられています。これらの定理はすべて、以下で導出される一般的な結果の特定の応用として (Tropp 2010) に記載されています。関連する研究の概要を示します。

次元 の固定された自己随伴行列の有限列を考え、を独立した標準正規変数または独立したラデマッハ乱数変数の有限列とします。 ${\displaystyle \{\mathbf {A} _{k}\}}$${\displaystyle d}$${\displaystyle \{\xi _{k}\}}$

そして、すべての に対して、 ${\displaystyle t\geq 0}$

${\displaystyle \Pr \left\{\lambda _{\text{max}}\left(\sum _{k}\xi _{k}\mathbf {A} _{k}\right)\geq t\right\}\leq d\cdot e^{-t^{2}/2\sigma ^{2}}}$

どこ

${\displaystyle \sigma^{2}={\bigg \Vert }\sum _{k}\mathbf {A} _{k}^{2}{\bigg \Vert }.}$

次元の固定行列の有限列を考え、を独立した標準正規分布または独立したラデマッハ乱数変数の有限列とする。分散パラメータを定義する。 ${\displaystyle \{\mathbf {B} _{k}\}}$${\displaystyle d_{1}\times d_{2}}$${\displaystyle \{\xi _{k}\}}$

${\displaystyle \sigma ^{2}=\max \left\{{\bigg \Vert }\sum _{k}\mathbf {B} _{k}\mathbf {B} _{k}^{*}{\bigg \Vert },{\bigg \Vert }\sum _{k}\mathbf {B} _{k}^{*}\mathbf {B} _{k}{\bigg \Vert }\right\}.}$

そして、すべての に対して、 ${\displaystyle t\geq 0}$

${\displaystyle \Pr \left\{{\bigg \Vert }\sum _{k}\xi _{k}\mathbf {B} _{k}{\bigg \Vert }\geq t\right\}\leq (d_{1}+d_{2})\cdot e^{-t^{2}/2\sigma ^{2}}.}$

古典的なチェルノフ境界は、独立で非負で一様に境界付けられたランダム変数の合計に関係します。行列設定では、類似の定理は、一様な固有値境界に従う半正定値ランダム行列の合計に関係します。

次元を持つ、独立したランダムな自己随伴行列の有限列を考える。各ランダム行列が次式を満たすと仮定する。 ${\displaystyle \{\mathbf {X} _{k}\}}$${\displaystyle d}$

${\displaystyle \mathbf {X} _{k}\succeq \mathbf {0} \quad {\text{and}}\quad \lambda _{\text{max}}(\mathbf {X} _{k})\leq R}$

ほぼ確実です。

定義する

${\displaystyle \mu _{\text{min}}=\lambda _{\text{min}}\left(\sum _{k}\mathbb {E} \,\mathbf {X} _{k}\right)\quad {\text{および}}\quad \mu _{\text{max}}=\lambda _{\text{max}}\left(\sum _{k}\mathbb {E} \,\mathbf {X} _{k}\right).}$

それから

${\displaystyle \Pr \left\{\lambda _{\text{min}}\left(\sum _{k}\mathbf {X} _{k}\right)\leq (1-\delta )\mu _{\text{min}}\right\}\leq d\cdot \left[{\frac {e^{-\delta }}{(1-\delta )^{1-\delta }}}\right]^{\​​mu _{\text{min}}/R}\quad {\text{for }}\delta \in [0,1){\text{, かつ}}}$

${\displaystyle \Pr \left\{\lambda _{\text{max}}\left(\sum _{k}\mathbf {X} _{k}\right)\geq (1+\delta )\mu _{\text{max}}\right\}\leq d\cdot \left[{\frac {e^{\delta }}{(1+\delta )^{1+\delta }}}\right]^{\​​mu _{\text{max}}/R}\quad {\text{for }}\delta \geq 0.}$

次式を満たす、独立でランダムな自己随伴行列の 列を考える。${\displaystyle \{\mathbf {X} _{k}:k=1,2,\ldots ,n\}}$

${\displaystyle \mathbf {X} _{k}\succeq \mathbf {0} \quad {\text{and}}\quad \lambda _{\text{max}}(\mathbf {X} _{k})\leq 1}$

ほぼ確実です。

平均期待値の最小および最大固有値を計算する。

${\displaystyle {\bar {\mu}}_{\text{min}}=\lambda _{\text{min}}\left({\frac {1}{n}}\sum _{k=1}^{n}\mathbb {E} \,\mathbf {X} _{k}\right)\quad {\text{および}}\quad {\bar {\mu}}_{\text{max}}=\lambda _{\text{max}}\left({\frac {1}{n}}\sum _{k=1}^{n}\mathbb {E} \,\mathbf {X} _{k}\right).}$

それから

${\displaystyle \Pr \left\{\lambda _{\text{min}}\left({\frac {1}{n}}\sum _{k=1}^{n}\mathbf {X} _{k}\right)\leq \alpha \right\}\leq d\cdot e^{-nD(\alpha \Vert {\bar {\mu }}_{\text{min}})}\quad {\text{for }}0\leq \alpha \leq {\bar {\mu }}_{\text{min}}{\text{, and}}}$

${\displaystyle \Pr \left\{\lambda _{\text{max}}\left({\frac {1}{n}}\sum _{k=1}^{n}\mathbf {X} _{k}\right)\geq \alpha \right\}\leq d\cdot e^{-nD(\alpha \Vert {\bar {\mu }}_{\text{max}})}\quad {\text{for }}{\bar {\mu }}_{\text{max}}\leq \alpha \leq 1.}$

バイナリ情報分散は次のように定義される。

${\displaystyle D(a\Vert u)=a\left(\log a-\log u\right)+(1-a)\left(\log(1-a)-\log(1-u)\right)}$

のために。 ${\displaystyle a,u\in [0,1]}$

スカラー設定では、ベネット不等式とバーンスタイン不等式は、有界または指数以下の独立したゼロ平均ランダム変数の合計の上端を表します。行列の場合、同様の結果はゼロ平均ランダム行列の合計に関係します。

次元を持つ、独立したランダムな自己随伴行列の有限列を考える。各ランダム行列が次式を満たすと仮定する。 ${\displaystyle \{\mathbf {X} _{k}\}}$${\displaystyle d}$

${\displaystyle \mathbb {E} \mathbf {X} _{k}=\mathbf {0} \quad {\text{and}}\quad \lambda _{\text{max}}(\mathbf {X} _{k})\leq R}$

ほぼ確実です。

総分散のノルムを計算する。

${\displaystyle \sigma ^{2}={\bigg \Vert }\sum _{k}\mathbb {E} \,(\mathbf {X} _{k}^{2}){\bigg \Vert }.}$

すると、次の不等式連鎖がすべての に対して成立します。 ${\displaystyle t\geq 0}$

${\displaystyle {\begin{aligned}\Pr \left\{\lambda _{\text{max}}\left(\sum _{k}\mathbf {X} _{k}\right)\geq t\right\}&\leq d\cdot \exp \left(-{\frac {\sigma ^{2}}{R^{2}}}\cdot h\left({\frac {Rt}{\sigma ^{2}}}\right)\right)\\&\leq d\cdot \exp \left({\frac {-t^{2}}{\sigma ^{2}+Rt/3}}\right)\\&\leq {\begin{cases}d\cdot \exp(-3t^{2}/8\sigma ^{2})\quad &{\text{for }}t\leq \sigma ^{2}/R;\\d\cdot \exp(-3t/8R)\quad &{\text{for }}t\geq \sigma ^{2}/R.\\\end{cases}}\end{aligned}}}$

関数はに対してとして定義されます。 ${\displaystyle h(u)}$${\displaystyle h(u)=(1+u)\log(1+u)-u}$${\displaystyle u\geq 0}$

次元を持つ、独立したランダムな自己随伴行列の有限列を考える。 ${\displaystyle \{\mathbf {X} _{k}\}}$${\displaystyle d}$

${\displaystyle \mathbb {E} \,\mathbf {X} _{k}=\mathbf {0} \quad {\text{and}}\quad \mathbb {E} \,(\mathbf {X} _{k}^{p})\preceq {\frac {p!}{2}}\cdot R^{p-2}\mathbf {A} _{k}^{2}}$

のために。 ${\displaystyle p=2,3,4,\ldots }$

分散パラメータを計算する。

${\displaystyle \sigma ^{2}={\bigg \Vert }\sum _{k}\mathbf {A} _{k}^{2}{\bigg \Vert }.}$

すると、次の不等式連鎖がすべての に対して成立します。 ${\displaystyle t\geq 0}$

${\displaystyle {\begin{aligned}\Pr \left\{\lambda _{\text{max}}\left(\sum _{k}\mathbf {X} _{k}\right)\geq t\right\}&\leq d\cdot \exp \left({\frac {-t^{2}/2}{\sigma ^{2}+Rt}}\right)\\&\leq {\begin{cases}d\cdot \exp(-t^{2}/4\sigma ^{2})\quad &{\text{for }}t\leq \sigma ^{2}/R;\\d\cdot \exp(-t/4R)\quad &{\text{for }}t\geq \sigma ^{2}/R.\\\end{cases}}\end{aligned}}}$

次元 の独立したランダム行列の有限列を考える。各ランダム行列が次式を満たすと仮定する。 ${\displaystyle \{\mathbf {Z} _{k}\}}$${\displaystyle d_{1}\times d_{2}}$

${\displaystyle \mathbb {E} \,\mathbf {Z} _{k}=\mathbf {0} \quad {\text{and}}\quad \Vert \mathbf {Z} _{k}\Vert \leq R}$

ほぼ確実です。分散パラメータを定義する

${\displaystyle \sigma ^{2}=\max \left\{{\bigg \Vert }\sum _{k}\mathbb {E} \,(\mathbf {Z} _{k}\mathbf {Z} _{k}^{*}){\bigg \Vert },{\bigg \Vert }\sum _{k}\mathbb {E} \,(\mathbf {Z} _{k}^{*}\mathbf {Z} _{k}){\bigg \Vert }\right\}.}$

そして、すべての${\displaystyle t\geq 0}$

${\displaystyle \Pr \left\{{\bigg \Vert }\sum _{k}\mathbf {Z} _{k}{\bigg \Vert }\geq t\right\}\leq (d_{1}+d_{2})\cdot \exp \left({\frac {-t^{2}/2}{\sigma ^{2}+Rt/3}}\right)}$

保持する。^[1]

アズマの不等式のスカラー版は、スカラーマルチンゲールが平均値を中心に正規集中を示し、偏差のスケールは差分シーケンスの合計最大二乗範囲によって制御されると述べています。以下は、行列設定での拡張です。

次元 の自己随伴行列の有限適応列と、次式を満たす自己随伴行列の 固定列を考える。${\displaystyle \{\mathbf {X} _{k}\}}$${\displaystyle d}$${\displaystyle \{\mathbf {A} _{k}\}}$

${\displaystyle \mathbb {E} _{k-1}\,\mathbf {X} _{k}=\mathbf {0} \quad {\text{and}}\quad \mathbf {X} _{k}^{2}\preceq \mathbf {A} _{k}^{2}}$

ほぼ確実です。

分散パラメータを計算する

${\displaystyle \sigma ^{2}={\bigg \Vert }\sum _{k}\mathbf {A} _{k}^{2}{\bigg \Vert }.}$

そして、すべての${\displaystyle t\geq 0}$

${\displaystyle \Pr \left\{\lambda _{\text{max}}\left(\sum _{k}\mathbf {X} _{k}\right)\geq t\right\}\leq d\cdot e^{-t^{2}/8\sigma ^{2}}}$

追加情報が利用できる場合、定数 1/8 は 1/2 に改善できます。1 つのケースは、各加数が条件付きで対称である場合に発生します。別の例では、が とほぼ確実に交換するという仮定が必要です。 ${\displaystyle \mathbf {X} _{k}}$${\displaystyle \mathbf {X} _{k}}$${\displaystyle \mathbf {A} _{k}}$

東行列の加数が独立であるという加法仮定を置くと、 Hoeffding の不等式の行列拡張が得られます。

次元 の独立したランダムな自己随伴行列の有限列を考え、 を固定された自己随伴行列の列とする。各ランダム行列が次式を満たすと仮定する。 ${\displaystyle \{\mathbf {X} _{k}\}}$${\displaystyle d}$${\displaystyle \{\mathbf {A} _{k}\}}$

${\displaystyle \mathbb {E} \,\mathbf {X} _{k}=\mathbf {0} \quad {\text{and}}\quad \mathbf {X} _{k}^{2}\preceq \mathbf {A} _{k}^{2}}$

ほぼ確実です。

そして、すべての${\displaystyle t\geq 0}$

${\displaystyle \Pr \left\{\lambda _{\text{max}}\left(\sum _{k}\mathbf {X} _{k}\right)\geq t\right\}\leq d\cdot e^{-t^{2}/8\sigma ^{2}}}$

どこ

${\displaystyle \sigma ^{2}={\bigg \Vert }\sum _{k}\mathbf {A} _{k}^{2}{\bigg \Vert }.}$

この結果の改良は（Mackey et al. 2012）で確立されました：すべての${\displaystyle t\geq 0}$

${\displaystyle \Pr \left\{\lambda _{\text{max}}\left(\sum _{k}\mathbf {X} _{k}\right)\geq t\right\}\leq d\cdot e^{-t^{2}/2\sigma ^{2}}}$

どこ

${\displaystyle \sigma ^{2}={\frac {1}{2}}{\bigg \Vert }\sum _{k}\mathbf {A} _{k}^{2}+\mathbb {E} \,\mathbf {X} _{k}^{2}{\bigg \Vert }\leq {\bigg \Vert }\sum _{k}\mathbf {A} _{k}^{2}{\bigg \Vert }.}$

スカラー設定では、マクダーミッド不等式は、アズマ不等式をDoob マルチンゲールに適用することにより、差を境界付ける一般的な方法の 1 つを提供します。境界付き差不等式のバージョンは、行列設定でも保持されます。

を独立したランダム変数の族とし、を変数を次元 の自己随伴行列に写像する関数とする。次式を満たす固定自己随伴行列の 列を考える。${\displaystyle \{Z_{k}:k=1,2,\ldots ,n\}}$${\displaystyle \mathbf {H} }$${\displaystyle n}$${\displaystyle d}$${\displaystyle \{\mathbf {A} _{k}\}}$

${\displaystyle \left(\mathbf {H} (z_{1},\ldots ,z_{k},\ldots ,z_{n})-\mathbf {H} (z_{1},\ldots ,z'_{k},\ldots ,z_{n})\right)^{2}\preceq \mathbf {A} _{k}^{2},}$

ここで、各インデックスに対する のすべての可能な値の範囲。分散パラメータを計算する。 ${\displaystyle z_{i}}$${\displaystyle z'_{i}}$${\displaystyle Z_{i}}$${\displaystyle i}$

${\displaystyle \sigma ^{2}={\bigg \Vert }\sum _{k}\mathbf {A} _{k}^{2}{\bigg \Vert }.}$

そして、すべての${\displaystyle t\geq 0}$

${\displaystyle \Pr \left\{\lambda _{\text{max}}\left(\mathbf {H} (\mathbf {z} )-\mathbb {E} \,\mathbf {H} (\mathbf {z} )\right)\geq t\right\}\leq d\cdot e^{-t^{2}/8\sigma ^{2}},}$

どこ。 ${\displaystyle \mathbf {z} =(Z_{1},\ldots ,Z_{n})}$

この結果の改良は（Paulin、Mackey & Tropp 2013）で確立されました（（Paulin、Mackey & Tropp 2016）も参照）。${\displaystyle t\geq 0}$

${\displaystyle \Pr \left\{\lambda _{\text{max}}\left(\mathbf {H} (\mathbf {z} )-\mathbb {E} \,\mathbf {H} (\mathbf {z} )\right)\geq t\right\}\leq d\cdot e^{-t^{2}/\sigma ^{2}},}$

どこでそして ${\displaystyle \mathbf {z} =(Z_{1},\ldots ,Z_{n})}$${\displaystyle \sigma ^{2}={\bigg \Vert }\sum _{k}\mathbf {A} _{k}^{2}{\bigg \Vert }.}$

このタイプの境界は、(Ahlswede & Winter 2003)によって初めて導かれました。自己随伴行列のガウス境界とラデマッハ境界に関する上記の定理を思い出してください。次元を持つ固定された自己随伴行列の有限列と、独立した標準正規または独立したラデマッハランダム変数の有限列に対して、 ${\displaystyle \{\mathbf {A} _{k}\}}$${\displaystyle d}$${\displaystyle \{\xi _{k}\}}$

${\displaystyle \Pr \left\{\lambda _{\text{max}}\left(\sum _{k}\xi _{k}\mathbf {A} _{k}\right)\geq t\right\}\leq d\cdot e^{-t^{2}/2\sigma ^{2}}}$

どこ

${\displaystyle \sigma ^{2}={\bigg \Vert }\sum _{k}\mathbf {A} _{k}^{2}{\bigg \Vert }.}$

アールスヴェーデとウィンターは、同じ結果を出すだろうが、

${\displaystyle \sigma _{AW}^{2}=\sum _{k}\lambda _{\max }\left(\mathbf {A} _{k}^{2}\right)}$。

比較すると、上の定理の はと と可換です。つまり、これは最大固有値の和ではなく、和の最大固有値です。これは、アールスウェーデ・ウィンター値 (ノルム三角不等式より) よりも大きくなることはありませんが、はるかに小さくなる可能性があります。したがって、上の定理は、アールスウェーデ・ウィンターの結果よりも厳しい境界を与えます。 ${\displaystyle \sigma ^{2}}$${\displaystyle \Sigma }$${\displaystyle \lambda _{\max }}$

(Ahlswede & Winter 2003) の主な貢献は、スカラー チェルノフ境界 (チェルノフ境界#加法形式 (絶対誤差) を参照) を証明するために使用されるラプラス変換法を自己随伴行列の場合に拡張したことです。以下の導出で手順を示します。このトピックに関する最近の研究はすべてこの同じ手順に従っており、主な違いは後続のステップから生じます。Ahlswede & Winter はゴールデン–トムソン不等式を使用して処理を進めますが、Tropp (Tropp 2010) はリーブの定理を使用します。

右辺をほぼ一定に保ちながら、 級数の長さ ( n ) と行列の次元 ( d ) を変化させたいとします。この場合、 n はdの対数にほぼ比例して変化する必要があります。いくつかの論文では、次元に依存せずに境界を確立しようと試みられています。Rudelson と Vershynin (Rudelson & Vershynin 2007) は、2 つのベクトルの外積である行列の結果を示しています。 (Magen & Zouzias 2010) は、低ランク行列について次元に依存しない結果を示しています。元の結果は、Ahlswede–Winter アプローチとは独立して導き出されましたが、(Oliveira 2010b) は、Ahlswede–Winter アプローチを使用して同様の結果を証明しています。

最後に、Oliveira (Oliveira 2010a) は、Ahlswede–Winter フレームワークとは独立して、行列マルチンゲールの結果を証明しています。Tropp (Tropp 2011) は、Ahlswede–Winter フレームワークを使用して結果をわずかに改善しています。どちらの結果もこの記事では示されていません。

(Ahlswede & Winter 2003) で発見されたラプラス変換の議論は、それ自体が重要な結果である。ランダムな自己随伴行列をとろう。すると、 ${\displaystyle \mathbf {Y} }$

${\displaystyle \Pr \left\{\lambda _{\max }(Y)\geq t\right\}\leq \inf _{\theta >0}\left\{e^{-\theta t}\cdot \operatorname {E} \left[\operatorname {tr} e^{\theta \mathbf {Y} }\right]\right\}.}$

これを証明するには、 を固定します 。すると ${\displaystyle \theta >0}$

${\displaystyle {\begin{aligned}\Pr \left\{\lambda _{\max }(\mathbf {Y} )\geq t\right\}&=\Pr \left\{\lambda _{\max }(\mathbf {\theta Y} )\geq \theta t\right\}\\&=\Pr \left\{e^{\lambda _{\max }(\theta \mathbf {Y} )}\geq e^{\theta t}\right\}\\&\leq e^{-\theta t}\operatorname {E} e^{\lambda _{\max }(\theta \mathbf {Y} )}\\&\leq e^{-\theta t}\operatorname {E} \operatorname {tr} e^{(\theta \mathbf {Y} )}\end{aligned}}}$

最後から 2 番目の不等式はマルコフの不等式です。最後の不等式は であるため成り立ちます。左端の量は とは独立しているため、 上の最小値はの上限のままです。 ${\displaystyle e^{\lambda _{\max }(\theta \mathbf {Y} )}=\lambda _{\max }(e^{\theta \mathbf {Y} })\leq \operatorname {tr} (e^{\theta \mathbf {Y} })}$${\displaystyle \theta }$${\displaystyle \theta >0}$

したがって、私たちの課題は、 を理解することです 。ただし、トレースと期待値はどちらも線形なので、それらを交換することができ、 を考慮するだけで十分です。これを行列生成関数と呼びます。ここが、(Ahlswede & Winter 2003) と (Tropp 2010) の方法が分岐するところです。次のプレゼンテーションは、(Ahlswede & Winter 2003) に続きます。 ${\displaystyle \operatorname {E} [\operatorname {tr} (e^{\theta \mathbf {Y} })]}$${\displaystyle \operatorname {E} e^{\theta \mathbf {Y} }:=\mathbf {M} _{\mathbf {Y} }(\theta )}$

ゴールデン・トムソン不等式は、

${\displaystyle \operatorname {tr} \mathbf {M} _{\mathbf {X} _{1}+\mathbf {X} _{2}}(\theta )\leq \operatorname {tr} \left[\left(\operatorname {E} e^{\theta \mathbf {X} _{1}}\right)\left(\operatorname {E} e^{\theta \mathbf {X} _{2}}\right)\right]=\operatorname {tr} \mathbf {M} _{\mathbf {X} _{1}}(\theta )\mathbf {M} _{\mathbf {X} _{2}}(\theta )}$ここでは、期待値の線形性を何度か使用しました。

と仮定します。この結果を繰り返すことで の上限を見つけることができます。であることに注目すると、 ${\displaystyle \mathbf {Y} =\sum _{k}\mathbf {X} _{k}}$${\displaystyle \operatorname {tr} \mathbf {M} _{\mathbf {Y} }(\theta )}$${\displaystyle \operatorname {tr} (\mathbf {AB} )\leq \operatorname {tr} (\mathbf {A} )\lambda _{\max }(\mathbf {B} )}$

${\displaystyle \operatorname {tr} \mathbf {M} _{\mathbf {Y} }(\theta )\leq \operatorname {tr} \left[\left(\operatorname {E} e^{\sum _{k=1}^{n-1}\theta \mathbf {X} _{k}}\right)\left(\operatorname {E} e^{\theta \mathbf {X} _{n}}\right)\right]\leq \operatorname {tr} \left(\operatorname {E} e^{\sum _{k=1}^{n-1}\theta \mathbf {X} _{k}}\right)\lambda _{\max }(\operatorname {E} e^{\theta \mathbf {X} _{n}}).}$

これを繰り返すと、

${\displaystyle \operatorname {tr} \mathbf {M} _{\mathbf {Y} }(\theta )\leq (\operatorname {tr} \mathbf {I} )\left[\Pi _{k}\lambda _{\max }(\operatorname {E} e^{\theta \mathbf {X} _{k}})\right]=de^{\sum _{k}\lambda _{\max }\left(\log \operatorname {E} e^{\theta \mathbf {X} _{k}}\right)}}$

これまで、 上の下限値を持つ境界を見つけました。今度は、これを境界で囲むことができます。いずれにせよ、アールスウェーデ-ウィンター境界が最大固有値の合計としてどのように生じるかがわかります。 ${\displaystyle \theta }$

(Tropp 2010) の主な貢献は、 (Ahlswede & Winter 2003) がゴールデン・トムソン不等式を適用したのに対し、リープの定理を適用したことです。Tropp の系は次のようになります。が固定された自己随伴行列で がランダムな自己随伴行列である場合、 ${\displaystyle H}$${\displaystyle X}$

${\displaystyle \operatorname {E} \operatorname {tr} e^{\mathbf {H} +\mathbf {X} }\leq \operatorname {tr} e^{\mathbf {H} +\log(\operatorname {E} e^{\mathbf {X} })}}$

証明: とする。するとリープの定理は次を言う。 ${\displaystyle \mathbf {Y} =e^{\mathbf {X} }}$

${\displaystyle f(\mathbf {Y} )=\operatorname {tr} e^{\mathbf {H} +\log(\mathbf {Y} )}}$

は凹です。最後のステップは、ジェンセンの不等式を使用して関数内の期待値を移動することです。

${\displaystyle \operatorname {E} \operatorname {tr} e^{\mathbf {H} +\log(\mathbf {Y} )}\leq \operatorname {tr} e^{\mathbf {H} +\log(\operatorname {E} \mathbf {Y} )}.}$

これにより、本論文の主要な結果、すなわち行列生成関数の対数の劣加法性が得られます。

を独立したランダム自己随伴行列の有限列とします。すると、すべての に対して、 ${\displaystyle \mathbf {X} _{k}}$${\displaystyle \theta \in \mathbb {R} }$

${\displaystyle \operatorname {tr} \mathbf {M} _{\sum _{k}\mathbf {X} _{k}}(\theta )\leq \operatorname {tr} e^{\sum _{k}\log \mathbf {M} _{\mathbf {X} _{k}}(\theta )}}$

証明: とすれば十分である。定義を拡張して、次のことを示す必要がある。 ${\displaystyle \theta =1}$

${\displaystyle \operatorname {E} \operatorname {tr} e^{\sum _{k}\theta \mathbf {X} _{k}}\leq \operatorname {tr} e^{\sum _{k}\log \operatorname {E} e^{\theta \mathbf {X} _{k}}}.}$

証明を完了するために、全期待値の法則を使用します。を を条件とする期待値とします。 はすべて独立していると仮定するため、 ${\displaystyle \operatorname {E} _{k}}$${\displaystyle \mathbf {X} _{1},\ldots ,\mathbf {X} _{k}}$${\displaystyle \mathbf {X} _{i}}$

${\displaystyle \operatorname {E} _{k-1}e^{\mathbf {X} _{k}}=\operatorname {E} e^{\mathbf {X} _{k}}.}$

定義する。 ${\displaystyle \mathbf {\Xi } _{k}=\log \operatorname {E} _{k-1}e^{\mathbf {X} _{k}}=\log \mathbf {M} _{\mathbf {X} _{k}}(\theta )}$

最後に、

${\displaystyle {\begin{aligned}\operatorname {E} \operatorname {tr} e^{\sum _{k=1}^{n}\mathbf {X} _{k}}&=\operatorname {E} _{0}\cdots \operatorname {E} _{n-1}\operatorname {tr} e^{\sum _{k=1}^{n-1}\mathbf {X} _{k}+\mathbf {X} _{n}}\\&\leq \operatorname {E} _{0}\cdots \operatorname {E} _{n-2}\operatorname {tr} e^{\sum _{k=1}^{n-1}\mathbf {X} _{k}+\log(\operatorname {E} _{n-1}e^{\mathbf {X} _{n}})}\\&=\operatorname {E} _{0}\cdots \operatorname {E} _{n-2}\operatorname {tr} e^{\sum _{k=1}^{n-2}\mathbf {X} _{k}+\mathbf {X} _{n-1}+\mathbf {\Xi } _{n}}\\&\vdots \\&=\operatorname {tr} e^{\sum _{k=1}^{n}\mathbf {\Xi } _{k}}\end{aligned}}}$

ここで、各ステップmにおいて、Troppの系を用いて、

${\displaystyle \mathbf {H} _{m}=\sum _{k=1}^{m-1}\mathbf {X} _{k}+\sum _{k=m+1}^{n}\mathbf {\Xi } _{k}}$

前回の結果から次のことが分かります。

${\displaystyle \Pr \left\{\lambda _{\max }\left(\sum _{k}\mathbf {X} _{k}\right)\geq t\right\}\leq \inf _{\theta >0}\left\{e^{-\theta t}\operatorname {tr} e^{\sum _{k}\log \mathbf {M} _{\mathbf {X} _{k}}(\theta )}\right\}}$

上で示した定理はすべてこの境界から導き出されたもので、定理はさまざまな方法で下限値を制限します。これらの手順は、示した証明よりもはるかに簡単です。

• Ahlswede, R.; Winter, A. (2003). 「量子チャネルによる識別のための強い逆」. IEEE Transactions on Information Theory . 48 (3): 569–579. arXiv : quant-ph/0012127 . doi :10.1109/18.985947. S2CID  523176.
• Mackey, L.; Jordan, MI; Chen, RY; Farrell, B .; Tropp, JA (2012 ) . 「交換可能ペア法によるマトリックス濃度不等式」。確率年報。42 (3): 906–945。arXiv : 1201.6002。doi :10.1214/13-AOP892。S2CID  9635314。
• Magen, A. ; Zouzias, A. (2010). 「低ランク行列値チェルノフ境界と近似行列乗算」. arXiv : 1005.2724 [cs.DS].
• Oliveira, RI (2010a). 「独立エッジを持つランダムグラフにおける隣接行列とラプラシアンの集中」arXiv : 0911.0600 [math.CO].
• Oliveira, RI (2010b). 「Rudelson によるランダム エルミート行列の和と不等式」. arXiv : 1004.3821 [math.PR].
• Paulin, D.; Mackey, L.; Tropp, JA (2013). 「カーネル結合からの行列濃度不等式の導出」. arXiv : 1305.0612 [math.PR].
• Paulin, D.; Mackey, L.; Tropp, JA (2016). 「ランダム行列のエフロン–スタイン不等式」. The Annals of Probability . 44 (5): 3431–3473. arXiv : 1408.3470 . doi :10.1214/15-AOP1054. S2CID  16263460.
• Rudelson, M.; Vershynin, R. (2007). 「大規模行列からのサンプリング: 幾何関数解析によるアプローチ」Journal of the Association for Computing Machinery . 54 (4 ed.). arXiv : math/9608208 . Bibcode :1996math......8208R. doi :10.1145/1255443.1255449. S2CID  6054789.
• Tropp, J. (2011). 「行列マルチンゲールに対するフリードマンの不等式」. arXiv : 1101.3039 [math.PR].
• Tropp, J. (2010). 「ランダム行列の合計に対するユーザーフレンドリーな末尾境界」.計算数学の基礎. 12 (4): 389–434. arXiv : 1004.4389 . doi :10.1007/s10208-011-9099-z. S2CID  17735965.