Matrix Chernoff vázán - Matrix Chernoff bound - Wikipedia

Pro určité aplikace v lineární algebra, je užitečné znát vlastnosti rozdělení pravděpodobnosti největší vlastní číslo a konečný součet z náhodné matice. Předpokládat ${ displaystyle { mathbf {X} _ {k} }}$ je konečná posloupnost náhodných matic. Analogicky k dobře známým Černoff svázán pro součty skalárů se pro daný parametr hledá vazba na následujícít:

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

Následující věty odpovídají na tuto obecnou otázku za různých předpokladů; tyto předpoklady jsou pojmenovány níže analogicky k jejich klasickým skalárním protějškům. Všechny tyto věty lze nalézt v (Tropp 2010 ), jako konkrétní použití obecného výsledku, který je odvozen níže. Je uveden souhrn souvisejících prací.

Série Matrix Gaussian a Rademacher

Pouzdro matice s vlastním nastavením

Zvažte konečnou posloupnost ${ displaystyle { mathbf {A} _ {k} }}$ pevných, samoadjungovaných matic s rozměrem ${ displaystyle d}$a nechte ${ displaystyle { xi _ {k} }}$ být konečnou posloupností nezávislý Standard normální nebo nezávislé Rademacher náhodné proměnné.

Pak pro všechny ${ displaystyle t geq 0}$,

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

kde

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

Obdélníkové pouzdro

Zvažte konečnou posloupnost ${ displaystyle { mathbf {B} _ {k} }}$ pevných, samoadjungovaných matic s rozměrem ${ displaystyle d_ {1} krát d_ {2}}$a nechte ${ displaystyle { xi _ {k} }}$ být konečnou posloupností nezávislých standardních normálních nebo nezávislých náhodných proměnných Rademacher. Definujte parametr rozptylu

${ 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} vpravo }.}$

Pak pro všechny ${ 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}}.}$

Matrix Chernoff nerovnosti

Klasický Černoffovy hranice týká se součtu nezávislých, nezáporných a rovnoměrně ohraničených náhodných proměnných. v maticovém nastavení se analogická věta týká součtu kladně semidefinitní náhodné matice podrobené jednotné vázané vlastní hodnotě.

Matrix Chernoff I.

Zvažte konečnou posloupnost ${ displaystyle { mathbf {X} _ {k} }}$ nezávislých náhodných matic s dimenzí ${ displaystyle d}$Předpokládejme, že každá náhodná matice vyhovuje

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

téměř jistě.

Definovat

${ displaystyle mu _ { text {min}} = lambda _ { text {min}} vlevo ( sum _ {k} mathbb {E} , mathbf {X} _ {k} vpravo) quad { text {a}} quad mu _ { text {max}} = lambda _ { text {max}} vlevo ( sum _ {k} mathbb {E} , mathbf {X} _ {k} right).}$

Pak

${ displaystyle Pr left { lambda _ { text {min}} left ( sum _ {k} mathbf {X} _ {k} right) leq (1- delta) mu _ { text {min}} vpravo } leq d cdot vlevo [{ frac {e ^ {- delta}} {(1- delta) ^ {1- delta}}} vpravo ] ^ { mu _ { text {min}} / R} quad { text {pro}} delta v [0,1] { text {, a}}}$

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

Matrix Chernoff II

Zvažte sekvenci ${ displaystyle { mathbf {X} _ {k}: k = 1,2, ldots, n }}$ nezávislých, náhodných, samoadjungovaných matic, které splňují

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

téměř jistě.

Vypočítejte minimální a maximální vlastní hodnoty průměrného očekávání,

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

Pak

${ 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 {a}}}$

${ 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 {pro}} { bar { mu}} _ { text {max}} leq alpha leq 1.}$

Binární divergence informací je definována jako

${ Displaystyle D (a Vert u) = a left ( log a- log u right) + (1-a) left ( log (1-a) - log (1-u) ) že jo)}$

pro ${ displaystyle a, u v [0,1]}$.

Nerovnosti Matrix Bennett a Bernstein

Ve skalárním prostředí Bennett a Bernstein nerovnosti popsat horní konec součtu nezávislých, nulových průměrných náhodných proměnných, které jsou buď omezené, nebo subexponenciální. V maticovém případě se analogické výsledky týkají součtu náhodných matic s nulovou střední hodnotou.

Ohraničený případ

Zvažte konečnou posloupnost ${ displaystyle { mathbf {X} _ {k} }}$ nezávislých náhodných matic s dimenzí ${ displaystyle d}$Předpokládejme, že každá náhodná matice vyhovuje

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

téměř jistě.

Vypočítejte normu celkového rozptylu,

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

Následující řetězec nerovností platí pro všechny ${ displaystyle t geq 0}$:

${ displaystyle { begin {zarovnáno} 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 {pro}} t geq sigma ^ {2} / R. end {případy}} end {zarovnaný}}}$

Funkce ${ displaystyle h (u)}$ je definován jako ${ Displaystyle h (u) = (1 + u) log (1 + u) -u}$ pro ${ displaystyle u geq 0}$.

Subexponenciální případ

Zvažte konečnou posloupnost ${ displaystyle { mathbf {X} _ {k} }}$ nezávislých náhodných matic s dimenzí ${ displaystyle d}$.Předpokládat, že

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

pro ${ displaystyle p = 2,3,4, ldots}$.

Vypočítejte parametr odchylky,

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

Následující řetězec nerovností platí pro všechny ${ displaystyle t geq 0}$:

${ displaystyle { begin {zarovnáno} 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 {pro}} t geq sigma ^ {2} / R. end {případy}} end {zarovnáno}}}$

Obdélníkové pouzdro

Zvažte konečnou posloupnost ${ displaystyle { mathbf {Z} _ {k} }}$ nezávislých, náhodných matic s dimenzí ${ displaystyle d_ {1} krát d_ {2}}$Předpokládejme, že každá náhodná matice vyhovuje

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

téměř jistě. Definujte parametr odchylky

${ displaystyle sigma ^ {2} = max vlevo {{ 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 }.}$

Pak pro všechny ${ 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)}$

drží.^[1]

Nerovnosti Matrix Azuma, Hoeffding a McDiarmid

Matrix Azuma

Skalární verze Azumaova nerovnost uvádí, že skalární martingale vykazuje normální koncentraci kolem své střední hodnoty a stupnice pro odchylky je řízena celkovým maximálním čtvercovým rozsahem rozdílové sekvence. Toto je rozšíření v maticovém nastavení.

Zvažte konečnou přizpůsobenou sekvenci ${ displaystyle { mathbf {X} _ {k} }}$ samoadjungovaných matic s dimenzí ${ displaystyle d}$a pevnou sekvenci ${ displaystyle { mathbf {A} _ {k} }}$ samoadjungovaných matic, které splňují

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

téměř jistě.

Vypočítejte parametr odchylky

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

Pak pro všechny ${ 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}}}$

Konstantu 1/8 lze vylepšit na 1/2, pokud jsou k dispozici další informace. Při každém sčítání dojde k jednomu případu ${ displaystyle mathbf {X} _ {k}}$ je podmíněně symetrický. Další příklad vyžaduje předpoklad, že ${ displaystyle mathbf {X} _ {k}}$ dojíždí téměř jistě s ${ displaystyle mathbf {A} _ {k}}$.

Matrix Hoeffding

Umístěním předpokladu sčítání, že sčítání v Matrix Azuma jsou nezávislé, získá rozšíření matice Hoeffdingovy nerovnosti.

Zvažte konečnou posloupnost ${ displaystyle { mathbf {X} _ {k} }}$ nezávislých náhodných matic s dimenzí ${ displaystyle d}$a nechte ${ displaystyle { mathbf {A} _ {k} }}$ být posloupností fixních matic se samočinnou vazbou

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

téměř jistě.

Pak pro všechny ${ 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}}}$

kde

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

Vylepšení tohoto výsledku bylo stanoveno v (Mackey a kol. 2012 ):pro všechny ${ 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}}}$

kde

${ 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}.}$

Maticově ohraničený rozdíl (McDiarmid)

Ve skalárním prostředí McDiarmidova nerovnost poskytuje jeden běžný způsob ohraničení rozdílů aplikací Azumaova nerovnost do a Doob martingale. V nastavení matice platí verze omezené rozdílové nerovnosti.

Nechat ${ displaystyle {Z_ {k}: k = 1,2, ldots, n }}$ být nezávislá skupina náhodných proměnných a nechat ${ displaystyle mathbf {H}}$ být funkcí, která mapuje ${ displaystyle n}$ proměnné do samoadjungované matice dimenze ${ displaystyle d}$Zvažte sekvenci ${ displaystyle { mathbf {A} _ {k} }}$ pevných samoadjungovaných matic, které splňují

${ 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},}$

kde ${ displaystyle z_ {i}}$ a ${ displaystyle z '_ {i}}$ rozsah přes všechny možné hodnoty ${ displaystyle Z_ {i}}$ pro každý index ${ displaystyle i}$Vypočítejte parametr odchylky

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

Pak pro všechny ${ 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}},}$

kde ${ displaystyle mathbf {z} = (Z_ {1}, ldots, Z_ {n})}$.

Zlepšení tohoto výsledku bylo stanoveno v (Paulin, Mackey & Tropp 2013 ) (viz také (Paulin, Mackey & Tropp 2016 )):pro všechny ${ 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}},}$

kde ${ displaystyle mathbf {z} = (Z_ {1}, ldots, Z_ {n})}$ a${ displaystyle sigma ^ {2} = { bigg Vert} sum _ {k} mathbf {A} _ {k} ^ {2} { bigg Vert}.}$

Přehled souvisejících vět

První hranice tohoto typu byly odvozeny (Ahlswede & Winter 2003 ). Připomeňme si výše uvedená věta pro samoadjungované maticové Gaussovy a Rademacherovy hranice: Pro konečnou sekvenci ${ displaystyle { mathbf {A} _ {k} }}$ pevných, samoadjungovaných matic s rozměrem ${ displaystyle d}$ a pro ${ displaystyle { xi _ {k} }}$ konečná posloupnost nezávislý Standard normální nebo nezávislé Rademacher náhodné proměnné

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

kde

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

Ahlswede a Winter by poskytli stejný výsledek, s výjimkou

${ displaystyle sigma _ {AW} ^ {2} = součet _ {k} lambda _ { max} left ( mathbf {A} _ {k} ^ {2} right)}$.

Pro srovnání ${ displaystyle sigma ^ {2}}$ ve větě výše dojíždí ${ displaystyle Sigma}$ a ${ displaystyle lambda _ { max}}$; to znamená, že se jedná o největší vlastní číslo součtu, nikoli o součet největších vlastních čísel. Nikdy není větší než hodnota Ahlswede – Winter (podle norma nerovnost trojúhelníku ), ale může být mnohem menší. Proto výše uvedená věta dává pevnější vazbu než výsledek Ahlswede – Winter.

Hlavní příspěvek (Ahlswede & Winter 2003 ) bylo rozšířením metody Laplaceovy transformace použité k prokázání skalární Chernoffovy vazby (viz Černoffova vázaná věta # pro aditivní formu (absolutní chyba) ) k případu samoadjungovaných matic. Postup uvedený v derivace níže. Všechny nedávné práce na toto téma se řídí stejným postupem a hlavní rozdíly vyplývají z následujících kroků. Ahlswede & Winter používají Golden – Thompsonova nerovnost pokračovat, zatímco Tropp (Tropp 2010 ) používá Liebova věta.

Předpokládejme, že si někdo přeje změnit délku série (n) a rozměry tematik (d), přičemž pravou stranu udržujte přibližně konstantní. Pak se musí přibližně lišit od protokolud. Několik článků se pokusilo vytvořit vazbu bez závislosti na rozměrech. Rudelson a Vershynin (Rudelson & Vershynin 2007 ) dát výsledek pro matice, které jsou vnějším produktem dvou vektorů. (Magen & Zouzias 2010 ) poskytnout výsledek bez dimenzionální závislosti pro matice s nízkým hodnocením. Původní výsledek byl odvozen nezávisle na přístupu Ahlswede – Winter, ale (Oliveira 2010b ) chyba harv: žádný cíl: CITEREFOliveira2010b (Pomoc) dokazuje podobný výsledek použitím přístupu Ahlswede – Winter.

Nakonec Oliveira (Oliviera 2010a ) chyba harv: žádný cíl: CITEREFOliviera2010a (Pomoc) dokazuje výsledek pro matice martingales nezávisle na rámci Ahlswede – Winter. Tropp (Tropp 2011 ) mírně zlepšuje výsledek pomocí rámce Ahlswede – Winter. Ani jeden výsledek není uveden v tomto článku.

Odvození a důkaz

Ahlswede a zima

Argument Laplaceovy transformace nalezený v (Ahlswede & Winter 2003 ) je sám o sobě významným výsledkem: Let ${ displaystyle mathbf {Y}}$ být náhodná samoadjungovaná matice. Pak

${ 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 }.}$

Abyste to dokázali, opravte to ${ displaystyle theta> 0}$. Pak

${ displaystyle { begin {zarovnáno} 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 {zarovnáno}}}$

Sekundární nerovnost je Markovova nerovnost. Od té doby platí poslední nerovnost ${ displaystyle e ^ { lambda _ { max} theta mathbf {Y}} = lambda _ { max} e ^ { theta mathbf {Y}} leq operatorname {tr} e ^ { theta mathbf {Y}}}$. Protože množství nejvíce vlevo je nezávislé na ${ displaystyle theta}$, infimum skončilo ${ displaystyle theta> 0}$ zůstává horní mezí.

Naším úkolem je tedy porozumět ${ displaystyle operatorname {E} operatorname {tr} e ^ { theta mathbf {Y}}}$ Vzhledem k tomu, že stopa i očekávání jsou lineární, můžeme je dojíždět, takže je dostatečné je zvážit ${ displaystyle operatorname {E} e ^ { theta mathbf {Y}}: = mathbf {M} _ { mathbf {Y}} ( theta)}$, které říkáme funkce generující matici. To je místo, kde metody (Ahlswede & Winter 2003 ) a (Tropp 2010 ) se rozcházejí. Následuje bezprostředně následující prezentace (Ahlswede & Winter 2003 ).

The Golden – Thompsonova nerovnost to naznačuje

${ displaystyle operatorname {tr} mathbf {M} _ { mathbf {X} _ {1} + mathbf {X} _ {2}} ( theta) leq operatorname {tr} vlevo [ 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)}$, kde jsme několikrát použili linearitu očekávání.

Předpokládat ${ displaystyle mathbf {Y} = součet _ {k} mathbf {X} _ {k}}$. Můžeme najít horní mez pro ${ displaystyle operatorname {tr} mathbf {M} _ { mathbf {Y}} ( theta)}$ iterací tohoto výsledku. Všímat si toho ${ displaystyle operatorname {tr} ( mathbf {AB}) leq operatorname {tr} ( mathbf {A}) lambda _ { max} ( mathbf {B})}$, pak

${ 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}}).}$

Iterací to dostaneme

${ 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}} vpravo)}}$

Zatím jsme našli vazbu s infimem nad ${ displaystyle theta}$. Na druhé straně to může být omezeno. V každém případě lze vidět, jak Ahlswede – Winterová vazba vzniká jako součet největších vlastních čísel.

Tropp

Hlavní příspěvek (Tropp 2010 ) je aplikace Liebova věta kde (Ahlswede & Winter 2003 ) použil Golden – Thompsonova nerovnost. Troppův důsledek je následující: Pokud ${ displaystyle H}$ je pevná samoadjungovaná matice a ${ displaystyle X}$ je tedy náhodná samoadjungovaná matice

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

Důkaz: Let ${ displaystyle mathbf {Y} = e ^ { mathbf {X}}}$. Pak nám to říká Liebova věta

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

je konkávní. Posledním krokem je použití Jensenova nerovnost přesunout očekávání uvnitř funkce:

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

To nám dává hlavní výsledek příspěvku: subadditivitu logu funkce generující matici.

Subadditivita log mgf

Nechat ${ displaystyle mathbf {X} _ {k}}$ být konečnou posloupností nezávislých náhodných samoadjungovaných matic. Pak pro všechny ${ 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)}}$

Důkaz: Stačí nechat ${ displaystyle theta = 1}$. Při rozšiřování definic to musíme ukázat

${ 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}}}.}$

K vyplnění důkazu používáme zákon úplného očekávání. Nechat ${ displaystyle operatorname {E} _ {k}}$ být očekávání podmíněné ${ displaystyle mathbf {X} _ {1}, ldots, mathbf {X} _ {k}}$. Protože předpokládáme všechny ${ displaystyle mathbf {X} _ {i}}$ jsou nezávislí,

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

Definovat ${ displaystyle mathbf { Xi} _ {k} = log operatorname {E} _ {k-1} e ^ { mathbf {X} _ {k}} = log mathbf {M} _ { mathbf {X} _ {k}} ( theta)}$.

Konečně máme

${ 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 {zarovnáno}}}$

kde na každém kroku m používáme Troppův důsledek s

${ displaystyle mathbf {H} _ {m} = součet _ {k = 1} ^ {m-1} mathbf {X} _ {k} + součet _ {k = m + 1} ^ {n } mathbf { Xi} _ {k}}$

Hlavní ocas vázán

Následující je okamžitý z předchozího výsledku:

${ 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)} doprava }}$

Všechny výše uvedené věty jsou odvozeny z této vazby; věty spočívají v různých způsobech, jak omezit infimum. Tyto kroky jsou podstatně jednodušší než uvedené důkazy.

Reference

• Ahlswede, R .; Winter, A. (2003). "Silná konverzace pro identifikaci pomocí kvantových kanálů". Transakce IEEE na teorii informací. 48 (3): 569–579. arXiv:quant-ph / 0012127. doi:10.1109/18.985947. S2CID  523176.CS1 maint: ref = harv (odkaz)
• Mackey, L .; Jordan, M. I .; Chen, R. Y .; Farrell, B .; Tropp, J. A. (2012). "Nerovnosti koncentrace matice metodou výměnných párů". Letopisy pravděpodobnosti. 42 (3): 906–945. arXiv:1201.6002. doi:10.1214 / 13-AOP892. S2CID  9635314.CS1 maint: ref = harv (odkaz)
• Magen, A.; Zouzias, A. (2010). „Low-Rank Matrix-valued Chernoff Bounds and přibližná maticová multiplikace“. arXiv:1005.2724 [cs.DS ].CS1 maint: ref = harv (odkaz)
• Oliveira, R.I. (2010). "Koncentrace matice sousedství a Laplacian v náhodných grafech s nezávislými hranami". arXiv:0911.0600 [math.CO ].CS1 maint: ref = harv (odkaz)
• Oliveira, R.I. (2010). "Součty náhodných hermitovských matic a nerovnost podle Rudelsona". arXiv:1004.3821 [math.PR ].CS1 maint: ref = harv (odkaz)
• Paulin, D .; Mackey, L .; Tropp, J. A. (2013). "Odvození nerovností maticové koncentrace z vazeb jádra". arXiv:1305.0612 [math.PR ].CS1 maint: ref = harv (odkaz)
• Paulin, D .; Mackey, L .; Tropp, J. A. (2016). "Nerovnosti Efron – Stein pro náhodné matice“. Letopisy pravděpodobnosti. 44 (5): 3431–3473. arXiv:1408.3470. doi:10.1214 / 15-AOP1054. S2CID  16263460.CS1 maint: ref = harv (odkaz)
• Rudelson, M .; Vershynin, R. (2007). "Vzorkování z velkých matic: přístup prostřednictvím geometrické funkční analýzy". J. Doc. Comput. Mach. (4. vyd.). 54. arXiv:matematika / 9608208. Bibcode:1996math ...... 8208R. doi:10.1145/1255443.1255449. S2CID  6054789.CS1 maint: ref = harv (odkaz)
• Tropp, J. (2011). "Freedmanova nerovnost pro matice martingales". arXiv:1101.3039 [math.PR ].CS1 maint: ref = harv (odkaz)
• Tropp, J. (2010). "Uživatelsky přívětivé ocasní hranice pro součty náhodných matic". Základy výpočetní matematiky. 12 (4): 389–434. arXiv:1004.4389. doi:10.1007 / s10208-011-9099-z. S2CID  17735965.CS1 maint: ref = harv (odkaz)