Welch hranice - Welch bounds - Wikipedia

v matematika, Welch hranice jsou rodina nerovnosti týkající se problému rovnoměrného rozložení sady jednotek vektory v vektorový prostor. Hranice jsou důležitými nástroji při navrhování a analýze určitých metod v systému Windows telekomunikace strojírenství, zejména v teorie kódování. Hranice byly původně publikovány v papíru z roku 1974 autorem L. R. Welch.

Matematický výrok

Li ${ displaystyle {x_ {1}, ldots, x_ {m} }}$ jsou jednotkové vektory v ${ displaystyle mathbb {C} ^ {n}}$, definovat ${ displaystyle c _ { max} = max _ {i neq j} | langle x_ {i}, x_ {j} rangle |}$, kde ${ displaystyle langle cdot, cdot rangle}$ je obvyklé vnitřní produkt na ${ displaystyle mathbb {C} ^ {n}}$. Pak platí následující nerovnosti ${ displaystyle k = 1,2, tečky}$:

${ displaystyle (c _ { max}) ^ {2k} geq { frac {1} {m-1}} left [{ frac {m} { binom {n + k-1} {k} }} - 1 vpravo]}$

Použitelnost

Li ${ displaystyle m leq n}$, pak vektory ${ displaystyle {x_ {i} }}$ může tvořit ortonormální sada v ${ displaystyle mathbb {C} ^ {n}}$. V tomto případě, ${ displaystyle c _ { max} = 0}$ a hranice jsou prázdné. V důsledku toho má výklad mezí smysl pouze tehdy, pokud ${ displaystyle m> n}$. Toto bude předpokládáno po zbytek tohoto článku.

Důkaz pro k = 1

„První svázaný Welch,“ odpovídá ${ displaystyle k = 1}$, je zdaleka nejběžněji používaným v aplikacích. Jeho důkaz probíhá ve dvou krocích, z nichž každý závisí na základní matematické nerovnosti. První krok vyvolá Cauchy – Schwarzova nerovnost a začíná zvážením ${ displaystyle m krát m}$ Gramová matice ${ displaystyle G}$ vektorů ${ displaystyle {x_ {i} }}$; tj.,

${ displaystyle G = left [{ begin {array} {ccc} langle x_ {1}, x_ {1} rangle & cdots & langle x_ {1}, x_ {m} rangle vdots & ddots & vdots langle x_ {m}, x_ {1} rangle & cdots & langle x_ {m}, x_ {m} rangle end {array}} right]}$

The stopa z ${ displaystyle G}$ se rovná součtu jeho vlastních čísel. Protože hodnost z ${ displaystyle G}$ je nanejvýš ${ displaystyle n}$a je to pozitivní semidefinit matice, ${ displaystyle G}$ má nanejvýš ${ displaystyle n}$ pozitivní vlastní čísla se zbývajícími vlastními čísly rovnými nule. Zápis nenulových vlastních čísel ${ displaystyle G}$ tak jako ${ displaystyle lambda _ {1}, ldots, lambda _ {r}}$ s ${ displaystyle r leq n}$ a aplikace Cauchy-Schwarzovy nerovnosti na vnitřní produkt an ${ displaystyle r}$-vektor těch s vektorem, jehož složkami jsou tato vlastní čísla, se získá

${ displaystyle ( mathrm {Tr} ; G) ^ {2} = vlevo ( součet _ {i = 1} ^ {r} lambda _ {i} vpravo) ^ {2} leq r součet _ {i = 1} ^ {r} lambda _ {i} ^ {2} leq n sum _ {i = 1} ^ {m} lambda _ {i} ^ {2}}$

Náměstí Frobeniova norma (Hilbert – Schmidtova norma) z ${ displaystyle G}$ splňuje

${ displaystyle || G || ^ {2} = součet _ {i = 1} ^ {m} součet _ {j = 1} ^ {m} | langle x_ {i}, x_ {j} rangle | ^ {2} = sum _ {i = 1} ^ {m} lambda _ {i} ^ {2}}$

Vezmeme-li to společně s předchozí nerovností, dává to

${ displaystyle sum _ {i = 1} ^ {m} sum _ {j = 1} ^ {m} | langle x_ {i}, x_ {j} rangle | ^ {2} geq { frac {( mathrm {Tr} ; G) ^ {2}} {n}}}$

Protože každý ${ displaystyle x_ {i}}$ má jednotkovou délku, prvky na hlavní úhlopříčce ${ displaystyle G}$ jsou jedni, a proto jeho stopa je ${ displaystyle mathrm {Tr} ; G = m}$. Tak,

${ displaystyle sum _ {i = 1} ^ {m} sum _ {j = 1} ^ {m} | langle x_ {i}, x_ {j} rangle | ^ {2} = m + sum _ {i neq j} | langle x_ {i}, x_ {j} rangle | ^ {2} geq { frac {m ^ {2}} {n}}}$

nebo

${ displaystyle sum _ {i neq j} | langle x_ {i}, x_ {j} rangle | ^ {2} geq { frac {m (m-n)} {n}}}$

Druhá část důkazu používá nerovnost zahrnující jednoduché pozorování, že průměr množiny nezáporných čísel nemůže být větší než největší číslo v množině. V matematickém zápisu, pokud ${ displaystyle a _ { ell} geq 0}$ pro ${ displaystyle ell = 1, ldots, L}$, pak

${ displaystyle { frac {1} {L}} součet _ { ell = 1} ^ {L} a _ { ell} leq max a _ { ell}}$

Předchozí výraz má ${ displaystyle m (m-1)}$ nezáporné podmínky v součtu, z nichž největší je ${ displaystyle c _ { max} ^ {2}}$. Tak,

${ displaystyle (c _ { max}) ^ {2} geq { frac {1} {m (m-1)}} sum _ {i neq j} | langle x_ {i}, x_ { j} rangle | ^ {2} geq { frac {mn} {n (m-1)}}}$

nebo

${ displaystyle (c _ { max}) ^ {2} geq { frac {m-n} {n (m-1)}}}$

což je právě nerovnost daná Welchem ​​v případě, že ${ displaystyle k = 1}$.

Dosažení rovnosti vázané na Welcha

V určitých telekomunikačních aplikacích je žádoucí konstruovat sady vektorů, které splňují Welchovy hranice s rovností. Bylo zavedeno několik technik k získání tzv Welch Bound Equality (WBE) sady vektorů pro k = 1 vázaný.

Důkaz uvedený výše ukazuje, že dvě oddělené matematické nerovnosti jsou začleněny do vazby Welch, když ${ displaystyle k = 1}$. Cauchy – Schwarzova nerovnost se setkává s rovností, když jsou dva zapojené vektory kolineární. Ve způsobu, jakým se používá ve výše uvedeném důkazu, k tomu dojde, když jsou všechny nenulové vlastní hodnoty matice Gram ${ displaystyle G}$ jsou stejné, což se děje přesně, když jsou vektory ${ displaystyle {x_ {1}, ldots, x_ {m} }}$ tvoří a těsný rám pro ${ displaystyle mathbb {C} ^ {n}}$.

Druhá nerovnost v důkazu je uspokojena rovností právě tehdy ${ displaystyle | langle x_ {i}, x_ {j} rangle |}$ je stejný pro každou volbu ${ displaystyle i neq j}$. V tomto případě jsou vektory rovnoramenný. Takže tato Welchova vazba se setkala s rovností právě tehdy, když byla sada vektorů ${ displaystyle {x_ {i} }}$ je rovnoramenný těsný rám v ${ displaystyle mathbb {C} ^ {n}}$.

Reference