Welch gränser

Inom matematik är Welch-gränser en familj av ojämlikheter som är relevanta för problemet att jämnt sprida en uppsättning enhetsvektorer i ett vektorrum . Gränserna är viktiga verktyg i design och analys av vissa metoder inom telekommunikationsteknik , särskilt inom kodningsteori . Ramarna publicerades ursprungligen i en tidning från 1974 av LR Welch .

Matematiskt påstående

Om $\{x_{1},\ldots ,x_{m}\}$ är enhetsvektorer i $\mathbb {C} ^{n}$ , definiera ${\displaystyle c_{\max }=\max _{i\neq j}|\langle x_{i},x_{j}\rangle |} , där ⟨ ⋅ , ⋅ ⟩ {\$ displaystyle $\ cdot \rangle }$ är den vanliga inre produkten på $\mathbb {C} ^{n}$ . Då gäller följande olikheter för $k=1,2,\dots$ :

(c_{\max })^{2k}\geq {\frac {1}{m-1}}\left[{\frac {m}{\binom {n+k-1}{k} }}-1\höger].

Welch-gränser anges också ibland i termer av den genomsnittliga kvadratiska överlappningen mellan uppsättningen vektorer. I det här fallet har man ojämlikheten

{\frac {1}{m^{2}}}\sum _{i,j=1}^{m}|\langle x_{i},x_{j}\rangle |^{2k} \geq {\frac {1}{\binom {n+k-1}{k}}}.

Tillämplighet

Om $m\leq n$ , då kan vektorerna $\{x_{i}\}$ bilda en ortonormal mängd i $\mathbb {C} ^{ n}$ . I det här fallet är $c_{\max }=0$ och gränserna är tomma. Följaktligen är tolkningen av gränserna endast meningsfull om $m>n$ . Detta kommer att antas under resten av denna artikel.

Bevis för k = 1

Den "första Welch-bundna", som motsvarar $k=1$ , är den överlägset vanligaste i applikationer. Dess bevis fortskrider i två steg, som vart och ett beror på en mer grundläggande matematisk ojämlikhet. Det första steget åberopar Cauchy–Schwarz-olikheten och börjar med att betrakta $m\times m$ grammatrisen $G$ för vektorerna $\{x_{i}\ }$ ; dvs.

G=\begin{\leftarray[{ \  }{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]

Spåret för $G$ är lika med summan av dess egenvärden . Eftersom rangordningen för $G$ är högst ${\displaystyle n} ,$ och det är en positiv semidefinitiv matris, har $G$ högst $n$ positiva egenvärden med alla sina återstående egenvärden lika med noll. Skriva egenvärden som inte är noll för $G$ som $\lambda _{1},\ldots ,\lambda _{r}$ med $r\ leq n$ och applicering av Cauchy-Schwarz-olikheten på den inre produkten av en $r$ -vektor av ettor med en vektor vars komponenter är dessa egenvärden ger

(\mathrm {Tr} \;G) ^{2}=\left(\sum _{i=1}^{r}\lambda _{i}\right)^{2}\leq r\sum _{i=1}^{r}\lambda _{i}^{2}\leq n\sum _{i=1}^{m}\lambda _{i}^{2}

Kvadraten på Frobenius-normen (Hilbert–Schmidt-normen) för $G$ uppfyller

||G||^{2}=\summa _{i=1}^{m}\summa _{j=1}^{m}|\langle x_{i},x_{j}\rangle |^{2}=\summa _{i=1}^{m}\lambda _{i}^{2}

Att ta detta tillsammans med den föregående ojämlikheten ger

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

Eftersom varje $x_{i}$ har enhetslängd, är elementen på huvuddiagonalen av $G$ ettor, och följaktligen är dess spår $\mathrm {Tr} \;G=m$ . Så,

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

eller

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

Den andra delen av beviset använder en olikhet som omfattar den enkla observationen att medelvärdet av en uppsättning icke-negativa tal inte kan vara större än det största talet i mängden. I matematisk notation, om $a_{\ell }\geq 0$ för ${\displaystyle \ell =1,\ldots ,L} ,$ då

{\frac {1}{L}}\summa _{\ell =1}^{L}a_{\ell }\leq \max a_{ \ell }

Det föregående uttrycket har $m(m-1)$ icke-negativa termer i summan, varav den största är $c_{\max }^{2}$ . Så,

(c_{\max })^{2}\geq {\frac {1}{m(m-1)}}\summa _{i\neq j }|\langle x_{i},x_{j}\rangle |^{2}\geq {\frac {mn}{n(m-1)}}

eller

(c_{\max })^{2}\geq {\frac {mn}{n(m-1)}}

vilket är exakt den olikhet som ges av Welch i fallet att $k=1$ .

Att uppnå Welch-gränserna

I vissa telekommunikationstillämpningar är det önskvärt att konstruera uppsättningar av vektorer som möter Welch-gränserna med likhet. Flera tekniker har introducerats för att erhålla så kallade Welch Bound Equality (WBE) uppsättningar av vektorer för $k=1$ -gränsen.

Beviset ovan visar att två separata matematiska olikheter är inkorporerade i Welch-gränsen när $k=1$ . Cauchy–Schwarz-ojämlikheten möts med likhet när de två inblandade vektorerna är kolinjära. På det sätt som det används i ovanstående bevis inträffar detta när alla egenvärden som inte är noll i grammatrisen $G$ är lika, vilket händer just när vektorerna ${\ displaystyle \{x_{1},\ldots ,x_{m}\}}$ utgör en snäv ram för $\mathbb {C} ^{n}$ .

Den andra olikheten i beviset nöjer sig med likheten om och endast om $|\langle x_{i},x_{j}\rangle |$ är samma för varje val av $i\neq j$ . I det här fallet är vektorerna ekvikantiga . Så denna Welch-bindning möts med likhet om och bara om uppsättningen av vektorer $\{x_{i}\}$ är en ekvikantig snäv ram i $\mathbb {C} ^{ n}$ .

På liknande sätt är Welch-gränserna angivna i termer av genomsnittlig kvadratisk överlappning mättade för alla $k\leq t$ om och endast om uppsättningen vektorer är en $t$ -design i den komplexa projektiven blanksteg $\mathbb {CP} ^{n-1}$ .

Se även