กลับไปหน้าบทความ

อ่าน 21 นาที

ไม่มีชื่อบทความ

For certain applications in linear algebra , it is useful to know properties of the probability distribution of the largest eigenvalue of a finite sum of random matrices .

Matrix Chernoff bound

For certain applications in linear algebra, it is useful to know properties of the probability distribution of the largest eigenvalue of a finite sum of random matrices. Suppose {Xk}{\displaystyle \{\mathbf {X} _{k}\}} is a finite sequence of random matrices. Analogous to the well-known Chernoff bound for sums of scalars, a bound on the following is sought for a given parameter t:

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

The following theorems answer this general question under various assumptions; these assumptions are named below by analogy to their classical, scalar counterparts. All of these theorems can be found in (Tropp 2010), as the specific application of a general result which is derived below. A summary of related works is given.

Matrix Gaussian and Rademacher series

Self-adjoint matrices case

Consider a finite sequence {Ak}{\displaystyle \{\mathbf {A} _{k}\}} of fixed, self-adjoint matrices with dimension d{\displaystyle d}, and let {ξk}{\displaystyle \{\xi _{k}\}} be a finite sequence of independent standard normal or independent Rademacher random variables.

Then, for all t0{\displaystyle t\geq 0},

Pr{λmax(kξkAk)t}det2/2σ2{\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}}}

where

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

Rectangular case

Consider a finite sequence {Bk}{\displaystyle \{\mathbf {B} _{k}\}} of fixed matrices with dimension d1×d2{\displaystyle d_{1}\times d_{2}}, and let {ξk}{\displaystyle \{\xi _{k}\}} be a finite sequence of independent standard normal or independent Rademacher random variables. Define the variance parameter

σ2=max{kBkBk,kBkBk}.{\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\}.}

Then, for all t0{\displaystyle t\geq 0},

Pr{kξkBkt}(d1+d2)et2/2σ2.{\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}}.}

Matrix Chernoff inequalities

The classical Chernoff bounds concern the sum of independent, nonnegative, and uniformly bounded random variables. In the matrix setting, the analogous theorem concerns a sum of positive-semidefinite random matrices subjected to a uniform eigenvalue bound.

Matrix Chernoff I

Consider a finite sequence {Xk}{\displaystyle \{\mathbf {X} _{k}\}} of independent, random, self-adjoint matrices with dimension d{\displaystyle d}. Assume that each random matrix satisfies

Xk0andλmax(Xk)R{\displaystyle \mathbf {X} _{k}\succeq \mathbf {0} \quad {\text{และ}}\quad \lambda _{\text{max}}(\mathbf {X} _{k})\leq R}

almost surely.

Define

μmin=λmin(kEXk)andμmax=λmax(kEXk).{\displaystyle \mu _{\text{min}}=\lambda _{\text{min}}\left(\sum _{k}\mathbb {E} \,\mathbf {X} _{k}\right)\quad {\text{and}}\quad \mu _{\text{max}}=\lambda _{\text{max}}\left(\sum _{k}\mathbb {E} \,\mathbf {X} _{k}\right).}

Then

Pr{λmin(kXk)(1δ)μmin}d[eδ(1δ)1δ]μmin/Rfor δ[0,1), and{\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{สำหรับ }}\delta \in [0,1){\text{และ}}}
Pr{λmax(kXk)(1+δ)μmax}d[eδ(1+δ)1+δ]μmax/Rfor δ0.{\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{สำหรับ }}\delta \geq 0.}

Matrix Chernoff II

Consider a sequence {Xk:k=1,2,,n}{\displaystyle \{\mathbf {X} _{k}:k=1,2,\ldots ,n\}} of independent, random, self-adjoint matrices that satisfy

Xk0andλmax(Xk)1{\displaystyle \mathbf {X} _{k}\succeq \mathbf {0} \quad {\text{และ}}\quad \lambda _{\text{max}}(\mathbf {X} _{k})\leq 1}

almost surely.

Compute the minimum and maximum eigenvalues of the average expectation,

μ¯min=λmin(1nk=1nEXk)andμ¯max=λmax(1nk=1nEXk).{\displaystyle {\bar {\mu }}_{\text{min}}=\lambda _{\text{min}}\left({\frac {1}{n}}\sum _{k=1}^{n}\mathbb {E} \,\mathbf {X} _{k}\right)\quad {\text{and}}\quad {\bar {\mu }}_{\text{max}}=\lambda _{\text{max}}\left({\frac {1}{n}}\sum _{k=1}^{n}\mathbb {E} \,\mathbf {X} _{k}\right).}

Then

Pr{λmin(1nk=1nXk)α}denD(αμ¯min)for 0αμ¯min, and{\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}}}
Pr{λmax(1nk=1nXk)α}denD(αμ¯max)for μ¯maxα1.{\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.}

The binary information divergence is defined as

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

for a,u[0,1]{\displaystyle a,u\in [0,1]}.

Matrix Bennett and Bernstein inequalities

In the scalar setting, Bennett and Bernstein inequalities describe the upper tail of a sum of independent, zero-mean random variables that are either bounded or subexponential. In the matrix case, the analogous results concern a sum of zero-mean random matrices.

Bounded case

Consider a finite sequence {Xk}{\displaystyle \{\mathbf {X} _{k}\}} of independent, random, self-adjoint matrices with dimension d{\displaystyle d}. Assume that each random matrix satisfies

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

almost surely.

Compute the norm of the total variance,

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

Then, the following chain of inequalities holds for all t0{\displaystyle t\geq 0}:

Pr{λmax(kXk)t}dexp(σ2R2h(Rtσ2))dexp(t2σ2+Rt/3){dexp(3t2/8σ2)for tσ2/R;dexp(3t/8R)for tσ2/R.{\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}}}

The function h(u){\displaystyle h(u)} is defined as h(u)=(1+u)log(1+u)u{\displaystyle h(u)=(1+u)\log(1+u)-u} for u0{\displaystyle u\geq 0}.

Consider a sequence {Xk}k=1n{\displaystyle \{\mathbf {X} _{k}\}_{k=1}^{n}} of independent and identically distributed random column vectors in Rd{\displaystyle \mathbb {R} ^{d}}. Assume that each random vector satisfies Xk2M{\displaystyle \Vert \mathbf {X} _{k}\Vert _{2}\leq M} almost surely, and E[XkXkT]21{\displaystyle \Vert \mathbb {E} [\mathbf {X} _{k}\mathbf {X} _{k}^{T}]\Vert _{2}\leq 1}. Then, for all t0{\displaystyle t\geq 0},[1]

Pr{1nk=1nXkXkTE[X1X1T]2t}(2min(d,n))2exp(n(t1)4M2){\displaystyle \Pr \left\{{\bigg \Vert }{\frac {1}{n}}\sum _{k=1}^{n}\mathbf {X} _{k}\mathbf {X} _{k}^{T}-\mathbb {E} [\mathbf {X} _{1}\mathbf {X} _{1}^{T}]{\bigg \Vert }_{2}\geq t\right\}\leq (2\min(d,n))^{2}\cdot \exp \left(-{\frac {n(t-1)}{4M^{2}}}\right)}

Subexponential case

Consider a finite sequence {Xk}{\displaystyle \{\mathbf {X} _{k}\}} of independent, random, self-adjoint matrices with dimension d{\displaystyle d}. Assume that

EXk=0andE(Xkp)p!2Rp2Ak2{\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}}

for p=2,3,4,{\displaystyle p=2,3,4,\ldots }.

Compute the variance parameter,

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

Then, the following chain of inequalities holds for all t0{\displaystyle t\geq 0}:

Pr{λmax(kXk)t}dexp(t2/2σ2+Rt){dexp(t2/4σ2)for tσ2/R;dexp(t/4R)for tσ2/R.{\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}}}

Rectangular case

Consider a finite sequence {Zk}{\displaystyle \{\mathbf {Z} _{k}\}}ของเมทริกซ์สุ่มอิสระที่มีมิติ1×2{\displaystyle d_{1}\times d_{2}}สมมติว่าเมทริกซ์สุ่มแต่ละตัวเป็นไปตามเงื่อนไขต่อไปนี้

อีเค=0และเคอาร์{\displaystyle \mathbb {E} \,\mathbf {Z} _{k}=\mathbf {0} \quad {\text{and}}\quad \Vert \mathbf {Z} _{k}\Vert \leq R}

เกือบจะแน่นอน กำหนดพารามิเตอร์ความแปรปรวน

σ2=สูงสุด{เคอี(เคเค*),เคอี(เค*เค)}.{\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\}.}

จากนั้น สำหรับทุกคนที0{\displaystyle t\geq 0}

ปร.{เคเคที}(1+2)เอ็กซ์(ที2/2σ2+อาร์ที/3){\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)}

ถือครอง

อสมการเมทริกซ์ Azuma, Hoeffding และ McDiarmid

เมทริกซ์ อาซูมะ

อสมการของ Azumaในรูปแบบสเกลาร์ระบุว่ามาร์ติงเกล แบบสเกลาร์ แสดงการกระจุกตัวแบบปกติรอบค่าเฉลี่ย และมาตราส่วนสำหรับการเบี่ยงเบนถูกควบคุมโดยช่วงกำลังสองสูงสุดทั้งหมดของลำดับความแตกต่าง ต่อไปนี้คือส่วนขยายในบริบทของเมทริกซ์

พิจารณาลำดับที่ปรับเปลี่ยนได้แบบจำกัด{Xเค}{\displaystyle \{\mathbf {X} _{k}\}}ของเมทริกซ์สมมาตรที่มีมิติ{\displaystyle d}และลำดับที่กำหนดไว้{เอเค}{\displaystyle \{\mathbf {A} _{k}\}}ของเมทริกซ์สมมาตรในตัวเองที่ตรงตามเงื่อนไข

อีเค1Xเค=0และXเค2เอเค2{\displaystyle \mathbb {E} _{k-1}\,\mathbf {X} _{k}=\mathbf {0} \quad {\text{and}}\quad \mathbf {X} _{k}^{2}\preceq \mathbf {A} _{k}^{2}}

แทบจะแน่นอน

คำนวณค่าพารามิเตอร์ความแปรปรวน

σ2=เคเอเค2.{\displaystyle \sigma ^{2}={\bigg \Vert }\sum _{k}\mathbf {A} _{k}^{2}{\bigg \Vert }.}

จากนั้น สำหรับทุกคนที0{\displaystyle t\geq 0}

ปร.{λสูงสุด(เคXเค)ที}อีที2/8σ2{\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 ได้เมื่อมีข้อมูลเพิ่มเติม กรณีหนึ่งเกิดขึ้นเมื่อแต่ละพจน์บวกXเค{\displaystyle \mathbf {X} _{k}}มีสมมาตรแบบมีเงื่อนไข ตัวอย่างอื่นต้องอาศัยข้อสมมติฐานว่าXเค{\displaystyle \mathbf {X} _{k}}การเดินทางไปทำงานแทบจะแน่นอนด้วยเอเค{\displaystyle \mathbf {A} _{k}}.

เมทริกซ์ โฮฟฟ์ดิง

การเพิ่มสมมติฐานว่าพจน์บวกในเมทริกซ์ Azuma เป็นอิสระต่อกัน จะทำให้ได้การขยายอสมการของ Hoeffding ในรูปแบบเมทริก ซ์

พิจารณาลำดับจำกัด{Xเค}{\displaystyle \{\mathbf {X} _{k}\}}ประกอบด้วยเมทริกซ์อิสระ สุ่ม และสมมาตรในตัวเอง ที่มีมิติ{\displaystyle d}และปล่อยให้{เอเค}{\displaystyle \{\mathbf {A} _{k}\}}เป็นลำดับของเมทริกซ์สมมาตรคงที่ สมมติว่าเมทริกซ์สุ่มแต่ละตัวเป็นไปตามเงื่อนไขต่อไปนี้

อีXเค=0และXเค2เอเค2{\displaystyle \mathbb {E} \,\mathbf {X} _{k}=\mathbf {0} \quad {\text{and}}\quad \mathbf {X} _{k}^{2}\preceq \mathbf {A} _{k}^{2}}

แทบจะแน่นอน

จากนั้น สำหรับทุกคนที0{\displaystyle t\geq 0}

ปร.{λสูงสุด(เคXเค)ที}อีที2/8σ2{\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}}}

ที่ไหน

σ2=เคเอเค2.{\displaystyle \sigma ^{2}={\bigg \Vert }\sum _{k}\mathbf {A} _{k}^{2}{\bigg \Vert }.}

ผลลัพธ์ที่ดีขึ้นนี้ได้รับการกำหนดไว้ใน( Mackey et al. 2012 ) : สำหรับทุกที0{\displaystyle t\geq 0}

ปร.{λสูงสุด(เคXเค)ที}อีที2/2σ2{\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}}}

ที่ไหน

σ2=12เคเอเค2+อีXเค2เคเอเค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 }.}

ผลต่างจำกัดของเมทริกซ์ (McDiarmid)

ในบริบทของสเกลาร์อสมการของ McDiarmidให้วิธีการทั่วไปวิธีหนึ่งในการกำหนดขอบเขตของความแตกต่างโดยการประยุกต์ใช้อสมการของ Azumaกับมาร์ติงเกลของ Doobนอกจากนี้ยังมีอสมการความแตกต่างที่มีขอบเขตในรูปแบบเมทริกซ์ด้วย

อนุญาต{เค:เค=1,2,,n}{\displaystyle \{Z_{k}:k=1,2,\ldots ,n\}}ให้ เป็นกลุ่มของตัวแปรสุ่มอิสระ และให้ชม{\displaystyle \mathbf {H} }เป็นฟังก์ชันที่แมปn{\displaystyle n}ตัวแปรไปยังเมทริกซ์สมมาตรที่มีมิติ{\displaystyle d}พิจารณาลำดับต่อไปนี้{เอเค}{\displaystyle \{\mathbf {A} _{k}\}}ของเมทริกซ์สมมาตรคงที่ที่สอดคล้องกับเงื่อนไข

(ชม(z1,,zเค,,zn)ชม(z1,,zเค,,zn))2เอเค2,{\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},}

ที่ไหนzฉัน{\displaystyle z_{i}}และzฉัน{\displaystyle z'_{i}}ครอบคลุมค่าที่เป็นไปได้ทั้งหมดของฉัน{\displaystyle Z_{i}}สำหรับแต่ละดัชนีฉัน{\displaystyle i}คำนวณค่าพารามิเตอร์ความแปรปรวน

σ2=เคเอเค2.{\displaystyle \sigma ^{2}={\bigg \Vert }\sum _{k}\mathbf {A} _{k}^{2}{\bigg \Vert }.}

จากนั้น สำหรับทุกคนที0{\displaystyle t\geq 0}

ปร.{λสูงสุด(ชม(z)อีชม(z))ที}อีที2/8σ2,{\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}},}

ที่ไหนz=(1,,n){\displaystyle \mathbf {z} =(Z_{1},\ldots ,Z_{n})}.

มีการปรับปรุงผลลัพธ์นี้ใน( Paulin, Mackey & Tropp 2013 ) (ดูเพิ่มเติมใน( Paulin, Mackey & Tropp 2016 ) ): สำหรับทุกที0{\displaystyle t\geq 0}

ปร.{λสูงสุด(ชม(z)อีชม(z))ที}อีที2/σ2,{\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}},}

ที่ไหนz=(1,,n){\displaystyle \mathbf {z} =(Z_{1},\ldots ,Z_{n})}และ σ2=เคเอเค2.{\displaystyle \sigma ^{2}={\bigg \Vert }\sum _{k}\mathbf {A} _{k}^{2}{\bigg \Vert }.}

ขอบเขตแรกของประเภทนี้ได้มาจาก( Ahlswede & Winter 2003 )โปรดระลึกถึงทฤษฎีบทข้างต้นสำหรับขอบเขต Gaussian และ Rademacher ของเมทริกซ์สมมาตร : สำหรับลำดับจำกัด{เอเค}{\displaystyle \{\mathbf {A} _{k}\}}ของเมทริกซ์คงที่แบบสมมาตรที่มีมิติ{\displaystyle d}และสำหรับ{ξเค}{\displaystyle \{\xi _{k}\}}ลำดับจำกัดของตัวแปรสุ่มปกติมาตรฐาน อิสระ หรือตัวแปรสุ่มราเดมาเชอร์อิสระ จากนั้น

ปร.{λสูงสุด(เคξเคเอเค)ที}อีที2/2σ2{\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}}}

ที่ไหน

σ2=เคเอเค2.{\displaystyle \sigma ^{2}={\bigg \Vert }\sum _{k}\mathbf {A} _{k}^{2}{\bigg \Vert }.}

Ahlswede และ Winter จะให้ผลลัพธ์เดียวกัน ยกเว้นว่า...

σเอ2=เคλสูงสุด(เอเค2){\displaystyle \sigma _{AW}^{2}=\sum _{k}\lambda _{\max }\left(\mathbf {A} _{k}^{2}\right)}.

เมื่อเปรียบเทียบกันแล้วσ2{\displaystyle \sigma ^{2}}ในทฤษฎีบทข้างต้น สลับที่กันได้Σ{\displaystyle \Sigma }และλสูงสุด{\displaystyle \lambda _{\max }}กล่าวคือ ค่าดังกล่าวเป็นค่าไอเกนที่ใหญ่ที่สุดของผลรวม ไม่ใช่ผลรวมของค่าไอเกนที่ใหญ่ที่สุด ค่านี้จะไม่มีวันมากกว่าค่าของ Ahlswede–Winter (ตามอสมการสามเหลี่ยมบรรทัดฐาน ) แต่สามารถมีค่าน้อยกว่ามากได้ ดังนั้น ทฤษฎีบทข้างต้นจึงให้ขอบเขตที่แน่นกว่าผลลัพธ์ของ Ahlswede–Winter

ผลงานหลักของ( Ahlswede & Winter 2003 )คือการขยายวิธีการแปลงลาปลาสที่ใช้ในการพิสูจน์ขอบเขตเชอร์นอฟแบบสเกลาร์ (ดู ขอบเขตเชอร์นอฟ # รูปแบบการบวก (ข้อผิดพลาดสัมบูรณ์) ) ไปสู่กรณีของเมทริกซ์สมมาตรในตัวเอง ขั้นตอนการคำนวณแสดงไว้ในการพิสูจน์ด้านล่าง งานวิจัยล่าสุดทั้งหมดในหัวข้อนี้ใช้ขั้นตอนเดียวกันนี้ และความแตกต่างหลักๆ มาจากขั้นตอนต่อมา Ahlswede & Winter ใช้ความไม่เท่าเทียมกันของโกลเด้น-ทอมป์สันในขณะที่ Tropp ( Tropp 2010 )ใช้ ทฤษฎีบท ของLieb

สมมติว่าเราต้องการเปลี่ยนแปลงความยาวของอนุกรม ( n ) และมิติของเมทริกซ์ ( d ) ในขณะที่รักษาด้านขวามือให้คงที่โดยประมาณ n จะต้องเปลี่ยนแปลงไปโดยประมาณตามลอการิทึมของdมีบทความหลายฉบับที่พยายามสร้างขอบเขตโดยไม่ขึ้นอยู่กับมิติ Rudelson และ Vershynin ( Rudelson & Vershynin 2007 )ให้ผลลัพธ์สำหรับเมทริกซ์ที่เป็นผลคูณภายนอกของเวกเตอร์สองตัว ( 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} }เป็นเมทริกซ์สมมาตรแบบสุ่ม จากนั้น

ปร.{λสูงสุด(วาย)ที}ข้อมูลθ>0{อีθทีอี[trอีθวาย]}.{\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\}.}

เพื่อพิสูจน์เรื่องนี้ ให้แก้ไข θ>0{\displaystyle \theta >0}. แล้ว

ปร.{λสูงสุด(วาย)ที}=ปร.{λสูงสุด(θวาย)θที}=ปร.{อีλสูงสุด(θวาย)อีθที}อีθทีอีอีλสูงสุด(θวาย)อีθทีอีtrอี(θวาย){\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}}}

อสมการรองสุดท้ายคืออสมการของมาร์คอฟอสมการสุดท้ายเป็นจริงเนื่องจากอีλสูงสุด(θวาย)=λสูงสุด(อีθวาย)tr(อีθวาย){\displaystyle e^{\lambda _{\max }(\theta \mathbf {Y} )}=\lambda _{\max }(e^{\theta \mathbf {Y} })\leq \operatorname {tr} (e^{\theta \mathbf {Y} })}เนื่องจากปริมาณทางซ้ายสุดไม่ขึ้นอยู่กับθ{\displaystyle \theta }ค่าต่ำสุดเหนือθ>0{\displaystyle \theta >0}ยังคงเป็นขีดจำกัดสูงสุดสำหรับมัน

ดังนั้น ภารกิจของเราคือการทำความเข้าใจอี[tr(อีθวาย)]{\displaystyle \operatorname {E} [\operatorname {tr} (e^{\theta \mathbf {Y} })]} อย่างไรก็ตาม เนื่องจากร่องรอยและความคาดหวังต่างก็เป็นเชิงเส้น เราจึงสามารถสลับลำดับกันได้ ดังนั้นจึงเพียงพอที่จะพิจารณาอีอีθวาย:=เอ็มวาย(θ){\displaystyle \operatorname {E} e^{\theta \mathbf {Y} }:=\mathbf {M} _{\mathbf {Y} }(\theta )}ซึ่งเราเรียกว่าฟังก์ชันก่อกำเนิดเมทริกซ์ นี่คือจุดที่วิธีการของ( Ahlswede & Winter 2003 )และ( Tropp 2010 )แตกต่างกัน การนำเสนอต่อไปนี้เป็นไปตาม( Ahlswede & Winter 2003 )

อสมการโกลเด้น-ทอมป์สันบ่งชี้ว่า

trเอ็มX1+X2(θ)tr[(อีอีθX1)(อีอีθX2)]=trเอ็มX1(θ)เอ็มX2(θ){\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 )}ซึ่งเราได้ใช้ความเป็นเส้นตรงของค่าคาดหวังหลายครั้ง

สมมติวาย=เคXเค{\displaystyle \mathbf {Y} =\sum _{k}\mathbf {X} _{k}}เราสามารถหาขอบเขตบนสำหรับtrเอ็มวาย(θ){\displaystyle \operatorname {tr} \mathbf {M} _{\mathbf {Y} }(\theta )}โดยการทำซ้ำผลลัพธ์นี้ โดยสังเกตว่าtr(เอบี)tr(เอ)λสูงสุด(บี){\displaystyle \operatorname {tr} (\mathbf {AB} )\leq \operatorname {tr} (\mathbf {A} )\lambda _{\max }(\mathbf {B} )}, แล้ว

trเอ็มวาย(θ)tr[(อีอีเค=1n1θXเค)(อีอีθXn)]tr(อีอีเค=1n1θXเค)λสูงสุด(อีอีθXn).{\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}}).}

เมื่อทำซ้ำเช่นนี้ เราจะได้

trเอ็มวาย(θ)(trฉัน)[Πเคλสูงสุด(อีอีθXเค)]=อีเคλสูงสุด(บันทึกอีอีθXเค){\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 }ในทางกลับกัน สิ่งนี้สามารถจำกัดได้ อย่างไรก็ตาม เราสามารถเห็นได้ว่าขอบเขตของ Ahlswede–Winter เกิดขึ้นจากผลรวมของค่าลักษณะเฉพาะที่ใหญ่ที่สุด

ทรอปป์

ผลงานสำคัญของ( Tropp 2010 )คือการประยุกต์ใช้ทฤษฎีบทของ Liebซึ่ง( Ahlswede & Winter 2003 )ได้ประยุกต์ใช้ความไม่เท่าเทียมกันของ Golden–Thompsonบทสรุปของ Tropp มีดังนี้: ถ้าชม{\displaystyle H}เป็นเมทริกซ์สมมาตรคงที่ และX{\displaystyle X}ถ้าเมทริกซ์สมมาตรแบบสุ่มนั้น

อีtrอีชม+Xtrอีชม+บันทึก(อีอีX){\displaystyle \operatorname {E} \operatorname {tr} e^{\mathbf {H} +\mathbf {X} }\leq \operatorname {tr} e^{\mathbf {H} +\log(\operatorname {E} e^{\mathbf {X} })}}

พิสูจน์: ให้วาย=อีX{\displaystyle \mathbf {Y} =e^{\mathbf {X} }}จากนั้นทฤษฎีบทของ Lieb ก็บอกเราว่า

เอฟ(วาย)=trอีชม+บันทึก(วาย){\displaystyle f(\mathbf {Y} )=\operatorname {tr} e^{\mathbf {H} +\log(\mathbf {Y} )}}

เป็นฟังก์ชันเว้า ขั้นตอนสุดท้ายคือการใช้ความไม่เท่าเทียมของเจนเซ่นเพื่อย้ายค่าคาดหวังเข้าไปภายในฟังก์ชัน:

อีtrอีชม+บันทึก(วาย)trอีชม+บันทึก(อีวาย).{\displaystyle \operatorname {E} \operatorname {tr} e^{\mathbf {H} +\log(\mathbf {Y} )}\leq \operatorname {tr} e^{\mathbf {H} +\log(\operatorname {E} \mathbf {Y} )}.}

นี่คือผลลัพธ์หลักของงานวิจัยนี้: คุณสมบัติการบวกย่อยของลอการิทึมของฟังก์ชันก่อกำเนิดเมทริกซ์

คุณสมบัติการบวกย่อยของ log mgf

อนุญาตXเค{\displaystyle \mathbf {X} _{k}}ให้ เป็นลำดับจำกัดของเมทริกซ์สมมาตรแบบสุ่มที่เป็นอิสระต่อกัน แล้วสำหรับทุก ๆθอาร์{\displaystyle \theta \in \mathbb {R} },

trเอ็มเคXเค(θ)trอีเคบันทึกเอ็มXเค(θ){\displaystyle \operatorname {tr} \mathbf {M} _{\sum _{k}\mathbf {X} _{k}}(\theta )\leq \operatorname {tr} e^{\sum _{k}\log \mathbf {M} _{\mathbf {X} _{k}}(\theta )}}

หลักฐาน: เพียงแค่ปล่อยก็เพียงพอแล้วθ=1{\displaystyle \theta =1}เมื่อขยายความนิยาม เราจำเป็นต้องแสดงให้เห็นว่า

อีtrอีเคθXเคtrอีเคบันทึกอีอีθXเค.{\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}}เป็นความคาดหวังที่ขึ้นอยู่กับเงื่อนไขX1,,Xเค{\displaystyle \mathbf {X} _{1},\ldots ,\mathbf {X} _{k}}เนื่องจากเราถือว่าทั้งหมดXฉัน{\displaystyle \mathbf {X} _{i}}เป็นอิสระต่อกัน

อีเค1อีXเค=อีอีXเค.{\displaystyle \operatorname {E} _{k-1}e^{\mathbf {X} _{k}}=\operatorname {E} e^{\mathbf {X} _{k}}.}

กำหนดΞเค=บันทึกอีเค1อีXเค=บันทึกเอ็มXเค(θ){\displaystyle \mathbf {\Xi } _{k}=\log \operatorname {E} _{k-1}e^{\mathbf {X} _{k}}=\log \mathbf {M} _{\mathbf {X} _{k}}(\theta )}.

สุดท้ายนี้ เรามี

อีtrอีเค=1nXเค=อี0อีn1trอีเค=1n1Xเค+Xnอี0อีn2trอีเค=1n1Xเค+บันทึก(อีn1อีXn)=อี0อีn2trอีเค=1n2Xเค+Xn1+Ξn=trอีเค=1nΞเค{\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 ร่วมกับ

ชม=เค=11Xเค+เค=+1nΞเค{\displaystyle \mathbf {H} _{m}=\sum _{k=1}^{m-1}\mathbf {X} _{k}+\sum _{k=m+1}^{n}\mathbf {\Xi } _{k}}

หางของเจ้านายถูกมัดไว้

ต่อไปนี้เป็นผลลัพธ์โดยตรงจากผลลัพธ์ก่อนหน้า:

ปร.{λสูงสุด(เคXเค)ที}ข้อมูลθ>0{อีθทีtrอีเคบันทึกเอ็มXเค(θ)}{\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\}}

ทฤษฎีบททั้งหมดที่กล่าวมาข้างต้นได้มาจากการจำกัดค่านี้ โดยทฤษฎีบทเหล่านั้นประกอบด้วยวิธีการต่างๆ ในการกำหนดขอบเขตของค่าต่ำสุด ขั้นตอนเหล่านี้ง่ายกว่าการพิสูจน์ที่ให้ไว้มาก

สรุปเนื้อหา

ข้อมูลสำคัญจากบทความ

ข้อมูลสำคัญเกี่ยวกับ ไม่มีชื่อบทความ

For certain applications in linear algebra , it is useful to know properties of the probability distribution of the largest eigenvalue of a finite sum of random matrices .

Self-adjoint matrices case

Consider a finite sequence { A k } {\displaystyle \{\mathbf {A} _{k}\}} of fixed, self-adjoint matrices with dimension d {\displaystyle d} , and let { ξ k } {\displaystyle \{\xi _{k}\}} be a finite sequence of independent standard normal or independent...

Rectangular case

Consider a finite sequence { B k } {\displaystyle \{\mathbf {B} _{k}\}} of fixed matrices with dimension d 1 × d 2 {\displaystyle d_{1}\times d_{2}} , and let { ξ k } {\displaystyle \{\xi _{k}\}} be a finite sequence of independent standard normal or...

Matrix Chernoff inequalities

The classical Chernoff bounds concern the sum of independent, nonnegative, and uniformly bounded random variables. In the matrix setting, the analogous theorem concerns a sum of positive-semidefinite random matrices subjected to a uniform eigenvalue bound.