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   are unit vectors in  , define  , where   is the usual inner product on  . Then the following inequalities hold for  : 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] 

Applicability

edit

If  , then the vectors   can form an orthonormal set in  . In this case,   and the bounds are vacuous. Consequently, interpretation of the bounds is only meaningful if  . This will be assumed throughout the remainder of this article.

Proof for k = 1

edit

The "first Welch bound," corresponding to  , 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   Gram matrix   of the vectors  ; i.e.,

 

The trace of   is equal to the sum of its eigenvalues. Because the rank of   is at most  , and it is a positive semidefinite matrix,   has at most   positive eigenvalues with its remaining eigenvalues all equal to zero. Writing the non-zero eigenvalues of   as   with   and applying the Cauchy-Schwarz inequality to the inner product of an  -vector of ones with a vector whose components are these eigenvalues yields

 

The square of the Frobenius norm (Hilbert–Schmidt norm) of   satisfies

 

Taking this together with the preceding inequality gives

 

Because each   has unit length, the elements on the main diagonal of   are ones, and hence its trace is  . So,

 

or

 

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   for  , then

 

The previous expression has   non-negative terms in the sum, the largest of which is  . So,

 

or

 

which is precisely the inequality given by Welch in the case that  .

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   bound.

The proof given above shows that two separate mathematical inequalities are incorporated into the Welch bound when  . 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   are equal, which happens precisely when the vectors   constitute a tight frame for  .

The other inequality in the proof is satisfied with equality if and only if   is the same for every choice of  . In this case, the vectors are equiangular. So this Welch bound is met with equality if and only if the set of vectors   is an equiangular tight frame in  .

Similarly, the Welch bounds stated in terms of average squared overlap, are saturated for all   if and only if the set of vectors is a  -design in the complex projective space  .[4]


See also

edit

References

edit
  1. ^ Welch, L. (1974-05-01). "Lower bounds on the maximum cross correlation of signals (Corresp.)". IEEE Transactions on Information Theory. 20 (3): 397–399. doi:10.1109/TIT.1974.1055219. ISSN 1557-9654.
  2. ^ Klappenecker, Andreas; Roetteler, Martin (2005-02-11). "Mutually Unbiased Bases are Complex Projective 2-Designs". arXiv:quant-ph/0502031. {{cite journal}}: Cite journal requires |journal= (help)
  3. ^ Belovs, Aleksandrs; Smotrovs, Juris (2008-07-22). "A Criterion for Attaining the Welch Bounds with Applications for Mutually Unbiased Bases". arXiv:0802.0855. {{cite journal}}: Cite journal requires |journal= (help)
  4. ^ a b Datta, Somantika; Howard, Stephen; Cochran, Douglas (2012-05-29). "Geometry of the Welch Bounds". arXiv:0909.0206. {{cite journal}}: Cite journal requires |journal= (help)