Welch bounds

In mathematics, Welch bounds are a family of inequalities pertinent to the problem of evenly spreading a set of unit vectors in a vector space. The bounds are important tools in the design and analysis of certain methods in telecommunication engineering, particularly in coding theory. The bounds were originally published in a 1974 paper by L. R. Welch.^[1]

Mathematical statement[edit]

If ${\displaystyle \{x_{1},\ldots ,x_{m}\}}$ are unit vectors in ${\displaystyle \mathbb {C} ^{n}}$, define ${\displaystyle c_{\max }=\max _{i\neq j}|\langle x_{i},x_{j}\rangle |}$, where ${\displaystyle \langle \cdot ,\cdot \rangle }$ is the usual inner product on ${\displaystyle \mathbb {C} ^{n}}$. Then the following inequalities hold for ${\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 {\frac {1}{m^{2}}}\sum _{i,j=1}^{m}|\langle x_{i},x_{j}\rangle |^{2k}\geq {\frac {1}{\binom {n+k-1}{k}}}.}$$

Applicability[edit]

If ${\displaystyle m\leq n}$, then the vectors ${\displaystyle \{x_{i}\}}$ can form an orthonormal set in ${\displaystyle \mathbb {C} ^{n}}$. In this case, ${\displaystyle c_{\max }=0}$ and the bounds are vacuous. Consequently, interpretation of the bounds is only meaningful if ${\displaystyle m>n}$. This will be assumed throughout the remainder of this article.

Proof for k = 1[edit]

The "first Welch bound," corresponding to ${\displaystyle k=1}$, is by far the most commonly used in applications. Its proof proceeds in two steps, each of which depends on a more basic mathematical inequality. The first step invokes the Cauchy–Schwarz inequality and begins by considering the Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "http://localhost:6011/en.wikipedia.org/v1/":): {\displaystyle m\times m} Gram matrix ${\displaystyle G}$ of the vectors ${\displaystyle \{x_{i}\}}$; i.e.,

${\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 trace of ${\displaystyle G}$ is equal to the sum of its eigenvalues. Because the rank of ${\displaystyle G}$ is at most ${\displaystyle n}$, and it is a positive semidefinite matrix, ${\displaystyle G}$ has at most ${\displaystyle n}$ positive eigenvalues with its remaining eigenvalues all equal to zero. Writing the non-zero eigenvalues of ${\displaystyle G}$ as ${\displaystyle \lambda _{1},\ldots ,\lambda _{r}}$ with ${\displaystyle r\leq n}$ and applying the Cauchy-Schwarz inequality to the inner product of an ${\displaystyle r}$-vector of ones with a vector whose components are these eigenvalues yields

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

The square of the Frobenius norm (Hilbert–Schmidt norm) of ${\displaystyle G}$ satisfies

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

Taking this together with the preceding inequality gives

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

Because each ${\displaystyle x_{i}}$ has unit length, the elements on the main diagonal of ${\displaystyle G}$ are ones, and hence its trace is ${\displaystyle \mathrm {Tr} \;G=m}$. So,

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

or

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

The second part of the proof uses an inequality encompassing the simple observation that the average of a set of non-negative numbers can be no greater than the largest number in the set. In mathematical notation, if ${\displaystyle a_{\ell }\geq 0}$ for ${\displaystyle \ell =1,\ldots ,L}$, then

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

The previous expression has ${\displaystyle m(m-1)}$ non-negative terms in the sum, the largest of which is ${\displaystyle c_{\max }^{2}}$. So,

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

or

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

which is precisely the inequality given by Welch in the case that ${\displaystyle k=1}$.

Achieving the Welch bounds[edit]

In certain telecommunications applications, it is desirable to construct sets of vectors that meet the Welch bounds with equality. Several techniques have been introduced to obtain so-called Welch Bound Equality (WBE) sets of vectors for the ${\displaystyle k=1}$ bound.

The proof given above shows that two separate mathematical inequalities are incorporated into the Welch bound when ${\displaystyle k=1}$. The Cauchy–Schwarz inequality is met with equality when the two vectors involved are collinear. In the way it is used in the above proof, this occurs when all the non-zero eigenvalues of the Gram matrix ${\displaystyle G}$ are equal, which happens precisely when the vectors ${\displaystyle \{x_{1},\ldots ,x_{m}\}}$ constitute a tight frame for ${\displaystyle \mathbb {C} ^{n}}$.

The other inequality in the proof is satisfied with equality if and only if ${\displaystyle |\langle x_{i},x_{j}\rangle |}$ is the same for every choice of ${\displaystyle i\neq j}$. In this case, the vectors are equiangular. So this Welch bound is met with equality if and only if the set of vectors ${\displaystyle \{x_{i}\}}$ is an equiangular tight frame in ${\displaystyle \mathbb {C} ^{n}}$.

Similarly, the Welch bounds stated in terms of average squared overlap, are saturated for all ${\displaystyle k\leq t}$ if and only if the set of vectors is a ${\displaystyle t}$-design in the complex projective space ${\displaystyle \mathbb {CP} ^{n-1}}$.^[4]

See also[edit]

• Spherical design
• Quantum t-design
• Equiangular lines

References[edit]