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.
If { x 1 , … , x m } are unit vectors in C n , define c max = max i ≠ j | ⟨ x i , x j ⟩ | , where ⟨ ⋅ , ⋅ ⟩ is the usual inner product on C n . Then the following inequalities hold for k = 1 , 2 , … :
( c max ) 2 k ≥ 1 m − 1 [ m ( n + k − 1 k ) − 1 ] If m ≤ n , then the vectors { x i } can form an orthonormal set in C n . In this case, c max = 0 and the bounds are vacuous. Consequently, interpretation of the bounds is only meaningful if m > n . This will be assumed throughout the remainder of this article.
The "first Welch bound," corresponding to 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 m × m Gram matrix G of the vectors { x i } ; i.e.,
G = [ ⟨ x 1 , x 1 ⟩ ⋯ ⟨ x 1 , x m ⟩ ⋮ ⋱ ⋮ ⟨ x m , x 1 ⟩ ⋯ ⟨ x m , x m ⟩ ] The trace of G is equal to the sum of its eigenvalues. Because the rank of G is at most n , and it is a positive semidefinite matrix, G has at most n positive eigenvalues with its remaining eigenvalues all equal to zero. Writing the non-zero eigenvalues of G as λ 1 , … , λ r with r ≤ n and applying the Cauchy-Schwarz inequality to the inner product of an r -vector of ones with a vector whose components are these eigenvalues yields
( T r G ) 2 = ( ∑ i = 1 r λ i ) 2 ≤ r ∑ i = 1 r λ i 2 ≤ n ∑ i = 1 m λ i 2 The square of the Frobenius norm (Hilbert–Schmidt norm) of G satisfies
| | G | | 2 = ∑ i = 1 m ∑ j = 1 m | ⟨ x i , x j ⟩ | 2 = ∑ i = 1 m λ i 2 Taking this together with the preceding inequality gives
∑ i = 1 m ∑ j = 1 m | ⟨ x i , x j ⟩ | 2 ≥ ( T r G ) 2 n Because each x i has unit length, the elements on the main diagonal of G are ones, and hence its trace is T r G = m . So,
∑ i = 1 m ∑ j = 1 m | ⟨ x i , x j ⟩ | 2 = m + ∑ i ≠ j | ⟨ x i , x j ⟩ | 2 ≥ m 2 n or
∑ i ≠ j | ⟨ x i , x j ⟩ | 2 ≥ 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 a ℓ ≥ 0 for ℓ = 1 , … , L , then
1 L ∑ ℓ = 1 L a ℓ ≤ max a ℓ The previous expression has m ( m − 1 ) non-negative terms in the sum,the largest of which is c max 2 . So,
( c max ) 2 ≥ 1 m ( m − 1 ) ∑ i ≠ j | ⟨ x i , x j ⟩ | 2 ≥ m − n n ( m − 1 ) or
( c max ) 2 ≥ m − n n ( m − 1 ) which is precisely the inequality given by Welch in the case that 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-called Welch Bound Equality (WBE) sets of vectors for the k = 1 bound.
The proof given above shows that two separate mathematical inequalities are incorporated into the Welch bound when 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 G are equal, which happens precisely when the vectors { x 1 , … , x m } constitute a tight frame for C n .
The other inequality in the proof is satisfied with equality if and only if | ⟨ x i , x j ⟩ | is the same for every choice of i ≠ j . In this case, the vectors are equiangular. So this Welch bound is met with equality if and only if the set of vectors { x i } is an equiangular tight frame in C n .
