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
.
