Welch bounds
Encyclopedia
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.
are unit vectors in 
, define 
, where 
is the usual inner product on 
. Then the following inequalities hold for 
:
, 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.
, 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
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 
.
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
, Welch bounds are a family of inequalities pertinent to the problem of evenly spreading a set of unit vectors
Vector space
A vector space is a mathematical structure formed by a collection of vectors: objects that may be added together and multiplied by numbers, called scalars in this context. Scalars are often taken to be real numbers, but one may also consider vector spaces with scalar multiplication by complex...
in a vector space
Vector space
A vector space is a mathematical structure formed by a collection of vectors: objects that may be added together and multiplied by numbers, called scalars in this context. Scalars are often taken to be real numbers, but one may also consider vector spaces with scalar multiplication by complex...
. The bounds are important tools in the design and analysis of certain methods in telecommunication
Telecommunication
Telecommunication is the transmission of information over significant distances to communicate. In earlier times, telecommunications involved the use of visual signals, such as beacons, smoke signals, semaphore telegraphs, signal flags, and optical heliographs, or audio messages via coded...
engineering, particularly in coding theory
Coding theory
Coding theory is the study of the properties of codes and their fitness for a specific application. Codes are used for data compression, cryptography, error-correction and more recently also for network coding...
. The bounds were originally published in a 1974 paper by L. R. Welch.
Mathematical statement
If are unit vectors in , define , where is the usual inner product on . Then the following inequalities hold for :
Applicability
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
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
Trace (linear algebra)
In linear algebra, the trace of an n-by-n square matrix A is defined to be the sum of the elements on the main diagonal of A, i.e.,...
of
is equal to the sum of its eigenvalues. Because the rankRank (linear algebra)
The column rank of a matrix A is the maximum number of linearly independent column vectors of A. The row rank of a matrix A is the maximum number of linearly independent row vectors of A...
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 Welch bound equality
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
. 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 equiangularEquiangular lines
In geometry, a set of lines in Euclidean space is called equiangular if every pair of lines makes the same angle.Equiangular lines are related to two-graphs....
. So this Welch bound is met with equality if and only if the set of vectors
is an equiangular tight frame in .