Inmathematics,Welch bounds are a family ofinequalities pertinent to the problem of evenly spreading a set of unitvectors in avector space. The bounds are important tools in the design and analysis of certain methods intelecommunication engineering, particularly incoding theory. The bounds were originally published in a 1974 paper byL. R. Welch.^[1]

If${\displaystyle \{x_1,\dots ,x_m\}}$ are unit vectors in${\displaystyle {\mathbb{C}}^n}$, define${\displaystyle c_{max}=\underset{i\ne j}{max}|⟨x_i,x_j⟩|}$, where${\displaystyle ⟨\cdot ,\cdot ⟩}$ is the usualinner product on${\displaystyle {\mathbb{C}}^n}$. Then the following inequalities hold for${\displaystyle k=1,2,\dots }$:$${\displaystyle (c_{max}{)}^{2k}\ge \frac{1}{m-1}\left[\frac{m}{(\genfrac{}{}{0ex}{}{n+k-1}{k})}-1\right].}$$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|⟨x_i,x_j⟩{|}^{2k}\ge \frac{1}{(\genfrac{}{}{0ex}{}{n+k-1}{k})}.}$$

If${\displaystyle m\le n}$, then the vectors${\displaystyle \{x_i\}}$ can form anorthonormal 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.

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 theCauchy–Schwarz inequality and begins by considering the${\displaystyle m\times m}$Gram matrix${\displaystyle G}$ of the vectors${\displaystyle \{x_i\}}$; i.e.,

Thetrace of${\displaystyle G}$ is equal to the sum of its eigenvalues. Because therank of${\displaystyle G}$ is at most${\displaystyle n}$, and it is apositive semidefinite matrix,${\displaystyle G}$ has at most${\displaystyle n}$ positiveeigenvalues with its remaining eigenvalues all equal to zero. Writing the non-zero eigenvalues of${\displaystyle G}$ as${\displaystyle {\lambda }_1,\dots ,{\lambda }_r}$ with${\displaystyle r\le 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{T}\mathrm{r}G{)}^2={\left(\sum _{i=1}^r{\lambda }_i\right)}^2\le r\sum _{i=1}^r{\lambda }_i^2\le n\sum _{i=1}^m{\lambda }_i^2}$

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

${\displaystyle ||G|{|}^2=\sum _{i=1}^m\sum _{j=1}^m|⟨x_i,x_j⟩{|}^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|⟨x_i,x_j⟩{|}^2\ge \frac{(\mathrm{T}\mathrm{r}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{T}\mathrm{r}G=m}$. So,

${\displaystyle \sum _{i=1}^m\sum _{j=1}^m|⟨x_i,x_j⟩{|}^2=m+\sum _{i\ne j}|⟨x_i,x_j⟩{|}^2\ge \frac{m^2}{n}}$

or

${\displaystyle \sum _{i\ne j}|⟨x_i,x_j⟩{|}^2\ge \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 }\ge 0}$ for${\displaystyle \ell =1,\dots ,L}$, then

${\displaystyle \frac{1}{L}\sum _{\ell =1}^L{a}_{\ell }\le 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\ge \frac{1}{m(m-1)}\sum _{i\ne j}|⟨x_i,x_j⟩{|}^2\ge \frac{m-n}{n(m-1)}}$

or

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

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

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-calledWelch 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,\dots ,x_m\}}$ constitute atight frame for${\displaystyle {\mathbb{C}}^n}$.

The other inequality in the proof is satisfied with equality if and only if${\displaystyle |⟨x_i,x_j⟩|}$ is the same for every choice of${\displaystyle i\ne j}$. In this case, the vectors areequiangular. 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\le t}$ if and only if the set of vectors is a${\displaystyle t}$-design in the complex projective space${\displaystyle {\mathbb{C}\mathbb{P}}^{n-1}}$.^[4]

• Spherical design
• Quantum t-design
• Equiangular lines

• Inequalities

• CS1 errors: missing periodical