Границы Уэлча - Welch bounds - Wikipedia

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

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

Если ${\displaystyle \{x_{1},\ldots ,x_{m}\}}$ являются единичными векторами в ${\displaystyle \mathbb {C} ^{n}}$, определять ${\displaystyle c_{\max }=\max _{i\neq j}|\langle x_{i},x_{j}\rangle |}$, куда ${\displaystyle \langle \cdot ,\cdot \rangle }$ это обычный внутренний продукт на ${\displaystyle \mathbb {C} ^{n}}$. Тогда для ${\displaystyle k=1,2,\dots }$:

${\displaystyle (c_{\max })^{2k}\geq {\frac {1}{m-1}}\left[{\frac {m}{\binom {n+k-1}{k}}}-1\right]}$

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

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

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

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

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

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

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

Площадь Норма Фробениуса (Норма Гильберта – Шмидта) ${\displaystyle G}$ удовлетворяет

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

Принимая это вместе с предыдущим неравенством, получаем

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

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

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

или же

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

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

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

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

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

или же

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

что и есть неравенство, данное Велчем в случае, когда ${\displaystyle k=1}$.

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

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

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

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

Рекомендации

• Datta, S .; Howard, S.D .; Кокран, Д. (2012). «Геометрия границ Уэлча». Линейная алгебра и ее приложения. 437 (10): 2455–70. arXiv:0909.0206. Дои:10.1016 / j.laa.2012.05.036.
• Уэлч, Л. (Май 1974 г.). «Нижние границы максимальной взаимной корреляции сигналов». IEEE Transactions по теории информации. 20 (3): 397–9. Дои:10.1109 / TIT.1974.1055219.