Границы Уэлча

В математике относящихся границы Уэлча представляют собой семейство неравенств, к проблеме равномерного распределения набора единичных векторов в векторном пространстве . Границы являются важными инструментами при разработке и анализе некоторых методов телекоммуникационной техники, особенно в теории кодирования . Границы были первоначально опубликованы в статье Л. Р. Уэлча в 1974 году .

Математическое утверждение

Если $\{x_{1},\ldots ,x_{m}\}$ являются единичными векторами в $\mathbb {C} ^{n}$, определять $c_{\max }=\max _{i\neq j}|\langle x_{i},x_{j}\rangle |$, где $\langle \cdot ,\cdot \rangle$ является обычным внутренним продуктом на $\mathbb {C} ^{n}$. Тогда для $k=1,2,\dots$: $$(c_{\max })^{2k}\geq {\frac {1}{m-1}}\left[{\frac {m}{\binom {n+k-1}{k}}}-1\right].$$Границы Уэлча также иногда выражаются в терминах усредненного квадрата перекрытия между набором векторов. В этом случае имеет место неравенство $${\frac {1}{m^{2}}}\sum _{i,j=1}^{m}|\langle x_{i},x_{j}\rangle |^{2k}\geq {\frac {1}{\binom {n+k-1}{k}}}.$$

Применимость

Если $m\leq n$, то векторы $\{x_{i}\}$ может образовывать ортонормированное множество в $\mathbb {C} ^{n}$. В этом случае, $c_{\max }=0$ и границы пусты. Следовательно, интерпретация границ имеет смысл только в том случае, если $m>n$. Это будет подразумеваться на протяжении оставшейся части статьи.

Доказательство для k = 1

«Первая граница Уэлча», соответствующая $k=1$, на сегодняшний день наиболее часто используется в приложениях. Его доказательство проходит в два этапа, каждый из которых зависит от более простого математического неравенства. На первом этапе используется неравенство Коши – Шварца и начинается с рассмотрения $m\times m$ Матрица Грамма $G$ векторов $\{x_{i}\}$; то есть,

$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]$

След ​ ​ $G$ равен сумме его собственных значений. Потому ранг что $G$ самое большее $n$, и это положительная полуопределенная матрица, $G$ имеет не более $n$ положительные собственные значения , а все остальные собственные значения равны нулю. Записывая ненулевые собственные значения $G$ как $\lambda _{1},\ldots ,\lambda _{r}$ с $r\leq n$ и применив неравенство Коши-Шварца к скалярному продукту $r$-вектор единиц с вектором, компонентами которого являются эти собственные значения, дает

$(\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}$

Квадрат нормы Фробениуса (нормы Гильберта – Шмидта) $G$ удовлетворяет

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

Если это объединить с предыдущим неравенством, то получим

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

Потому что каждый $x_{i}$ имеет единичную длину, элементы на главной диагонали $G$ являются единицами, и, следовательно, его след $\mathrm {Tr} \;G=m$. Так,

$\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}}$

или

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

Во второй части доказательства используется неравенство, заключающееся в простом наблюдении, что среднее значение набора неотрицательных чисел не может быть больше, чем наибольшее число в наборе. В математических обозначениях, если $a_{\ell }\geq 0$ для $\ell =1,\ldots ,L$, затем

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

Предыдущее выражение имеет $m(m-1)$ неотрицательные члены суммы, наибольшее из которых $c_{\max }^{2}$. Так,

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

или

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

что и есть неравенство, данное Уэлчем в случае, когда $k=1$.

Достижение границ Уэлча

В некоторых телекоммуникационных приложениях желательно создавать наборы векторов, которые с равенством соответствуют границам Уэлча. Было предложено несколько методов получения так называемых равенства Уэлча (WBE). наборов векторов $k=1$ граница.

Приведенное выше доказательство показывает, что в оценку Уэлча включаются два отдельных математических неравенства, когда $k=1$. Неравенство Коши – Шварца соблюдается равенством, когда два задействованных вектора коллинеарны. В приведенном выше доказательстве это происходит, когда все ненулевые собственные значения матрицы Грама $G$ равны, что происходит именно тогда, когда векторы $\{x_{1},\ldots ,x_{m}\}$ представляют собой жесткие рамки для $\mathbb {C} ^{n}$.

Другое неравенство в доказательстве удовлетворяется равенством тогда и только тогда, когда $|\langle x_{i},x_{j}\rangle |$ одинаково для каждого выбора $i\neq j$. В этом случае векторы равноугольные . Таким образом, эта граница Уэлча выполняется с равенством тогда и только тогда, когда набор векторов $\{x_{i}\}$ представляет собой равноугольную плотную рамку в $\mathbb {C} ^{n}$.

Точно так же границы Уэлча, сформулированные в терминах среднего квадрата перекрытия, являются насыщенными для всех $k\leq t$ тогда и только тогда, когда набор векторов является $t$-дизайн в сложном проективном пространстве $\mathbb {CP} ^{n-1}$.

См. также

• Сферический дизайн
• Квантовый Т-дизайн
• Равноугольные линии