Welch bounds

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].}$$ When ${\displaystyle k=1}$, this reduces to $${\displaystyle (c_{\max })^{2}\geq {\frac {m-n}{n(m-1)}}.}$$ Welch bounds are also sometimes stated in terms of the averaged squared overlap between the set of vectors. In this case, one has the inequality^[2][3][4]$${\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}}}.}$$

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.

Summarize Timeline Top Qs Fact Check

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