Welch bounds

Last updated February 19, 2023

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

If $\{x_{1},\ldots ,x_{m}\}$ are unit vectors in $\mathbb {C} ^{n}$ , define $c_{\max }=\max _{i\neq j}|\langle x_{i},x_{j}\rangle |$ , where $\langle \cdot ,\cdot \rangle$ is the usual inner product on $\mathbb {C} ^{n}$ . Then the following inequalities hold for $k=1,2,\dots$ :

(c_{\max })^{2k}\geq {\frac {1}{m-1}}\left[{\frac {m}{\binom {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]

{\frac {1}{m^{2}}}\sum _{i,j=1}^{m}|\langle x_{i},x_{j}\rangle |^{2k}\geq {\frac {1}{\binom {n+k-1}{k}}}.

Applicability

If $m\leq n$ , then the vectors $\{x_{i}\}$ can form an orthonormal set in $\mathbb {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.

Proof for k = 1

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\times m$ Gram matrix $G$ of the vectors $\{x_{i}\}$ ; i.e.,

G=\left[{\begin{array}{ccc}\langle x_{1},x_{1}\rangle &\cdots &\langle x_{1},x_{m}\rangle \\\vdots &\ddots &\vdots \\\langle x_{m},x_{1}\rangle &\cdots &\langle x_{m},x_{m}\rangle \end{array}}\right]

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 $\lambda _{1},\ldots ,\lambda _{r}$ with $r\leq 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

(\mathrm {Tr} \;G)^{2}=\left(\sum _{i=1}^{r}\lambda _{i}\right)^{2}\leq r\sum _{i=1}^{r}\lambda _{i}^{2}\leq n\sum _{i=1}^{m}\lambda _{i}^{2}

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

||G||^{2}=\sum _{i=1}^{m}\sum _{j=1}^{m}|\langle x_{i},x_{j}\rangle |^{2}=\sum _{i=1}^{m}\lambda _{i}^{2}

Taking this together with the preceding inequality gives

\sum _{i=1}^{m}\sum _{j=1}^{m}|\langle x_{i},x_{j}\rangle |^{2}\geq {\frac {(\mathrm {Tr} \;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 $\mathrm {Tr} \;G=m$ . So,

\sum _{i=1}^{m}\sum _{j=1}^{m}|\langle x_{i},x_{j}\rangle |^{2}=m+\sum _{i\neq j}|\langle x_{i},x_{j}\rangle |^{2}\geq {\frac {m^{2}}{n}}

or

\sum _{i\neq j}|\langle x_{i},x_{j}\rangle |^{2}\geq {\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 $a_{\ell }\geq 0$ for $\ell =1,\ldots ,L$ , then

{\frac {1}{L}}\sum _{\ell =1}^{L}a_{\ell }\leq \max a_{\ell }

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}\geq {\frac {1}{m(m-1)}}\sum _{i\neq j}|\langle x_{i},x_{j}\rangle |^{2}\geq {\frac {m-n}{n(m-1)}}

or

(c_{\max })^{2}\geq {\frac {m-n}{n(m-1)}}

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

Achieving the Welch bounds

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},\ldots ,x_{m}\}$ constitute a tight frame for $\mathbb {C} ^{n}$ .

The other inequality in the proof is satisfied with equality if and only if $|\langle x_{i},x_{j}\rangle |$ is the same for every choice of $i\neq 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 $\mathbb {C} ^{n}$ .

Similarly, the Welch bounds stated in terms of average squared overlap, are saturated for all $k\leq t$ if and only if the set of vectors is a $t$ -design in the complex projective space $\mathbb {CP} ^{n-1}$ .^[4]

Related Research Articles

<span class="mw-page-title-main">Inner product space</span> Generalization of the dot product; used to define Hilbert spaces

In mathematics, an inner product space is a real vector space or a complex vector space with an operation called an inner product. The inner product of two vectors in the space is a scalar, often denoted with angle brackets such as in $. Inner products allow formal definitions of intuitive geometric notions, such as lengths, angles, and orthogonality of vectors. Inner product spaces generalize Euclidean vector spaces, in which the inner product is the dot product or scalar product of Cartesian coordinates. Inner product spaces of infinite dimension are widely used in functional analysis. Inner product spaces over the field of complex numbers are sometimes referred to as unitary spaces . The first usage of the concept of a vector space with an inner product is due to Giuseppe Peano, in 1898.$

In quantum mechanics, the uncertainty principle is any of a variety of mathematical inequalities asserting a fundamental limit to the accuracy with which the values for certain pairs of physical quantities of a particle, such as position, x, and momentum, p, can be predicted from initial conditions.

The Cauchy–Schwarz inequality is considered one of the most important and widely used inequalities in mathematics.

In mathematics, a symmetric matrix $with real entries is positive-definite if the real number is positive for every nonzero real column vector where is the transpose of . More generally, a Hermitian matrix is positive-definite if the real number is positive for every nonzero complex column vector where denotes the conjugate transpose of$

In mathematics, a Hermitian matrix is a complex square matrix that is equal to its own conjugate transpose—that is, the element in the $i$ -th row and $j$ -th column is equal to the complex conjugate of the element in the $j$ -th row and $i$ -th column, for all indices $i$ and $j$ :

In mathematics, the Rayleigh quotient for a given complex Hermitian matrix M and nonzero vector x is defined as:

In mathematics, spectral theory is an inclusive term for theories extending the eigenvector and eigenvalue theory of a single square matrix to a much broader theory of the structure of operators in a variety of mathematical spaces. It is a result of studies of linear algebra and the solutions of systems of linear equations and their generalizations. The theory is connected to that of analytic functions because the spectral properties of an operator are related to analytic functions of the spectral parameter.

In mathematics, a positive-definite function is, depending on the context, either of two types of function.

In functional analysis, a reproducing kernel Hilbert space (RKHS) is a Hilbert space of functions in which point evaluation is a continuous linear functional. Roughly speaking, this means that if two functions $and in the RKHS are close in norm, i.e., is small, then and are also pointwise close, i.e., is small for all . The converse does not need to be true. Informally, this can be shown by looking at the supremum norm: the sequence of functions converges pointwise, but do not converge uniformly i.e. do not converge with respect to the supremum norm.$

In linear algebra and functional analysis, the min-max theorem, or variational theorem, or Courant–Fischer–Weyl min-max principle, is a result that gives a variational characterization of eigenvalues of compact Hermitian operators on Hilbert spaces. It can be viewed as the starting point of many results of similar nature.

In mathematics, a norm is a function from a real or complex vector space to the non-negative real numbers that behaves in certain ways like the distance from the origin: it commutes with scaling, obeys a form of the triangle inequality, and is zero only at the origin. In particular, the Euclidean distance in a Euclidean space is defined by a norm on the associated Euclidean vector space, called the Euclidean norm, the 2-norm, or, sometimes, the magnitude of the vector. This norm can be defined as the square root of the inner product of a vector with itself.

Semidefinite programming (SDP) is a subfield of convex optimization concerned with the optimization of a linear objective function over the intersection of the cone of positive semidefinite matrices with an affine space, i.e., a spectrahedron.

In quantum mechanics, notably in quantum information theory, fidelity is a measure of the "closeness" of two quantum states. It expresses the probability that one state will pass a test to identify as the other. The fidelity is not a metric on the space of density matrices, but it can be used to define the Bures metric on this space.

The expander mixing lemma intuitively states that the edges of certain $-regular graphs are evenly distributed throughout the graph. In particular, the number of edges between two vertex subsets and is always close to the expected number of edges between them in a random -regular graph, namely .$

In probability theory, Bernstein inequalities give bounds on the probability that the sum of random variables deviates from its mean. In the simplest case, let X₁, ..., X_n be independent Bernoulli random variables taking values +1 and −1 with probability 1/2, then for every positive $,$

In mathematics, the Grothendieck inequality states that there is a universal constant $with the following property. If M ij is an n \times n matrix with$

In mathematics, a dissipative operator is a linear operator A defined on a linear subspace D(A) of Banach space X, taking values in X such that for all λ > 0 and all x ∈ D(A)

In mathematics, the logarithmic norm is a real-valued functional on operators, and is derived from either an inner product, a vector norm, or its induced operator norm. The logarithmic norm was independently introduced by Germund Dahlquist and Sergei Lozinskiĭ in 1958, for square matrices. It has since been extended to nonlinear operators and unbounded operators as well. The logarithmic norm has a wide range of applications, in particular in matrix theory, differential equations and numerical analysis. In the finite-dimensional setting, it is also referred to as the matrix measure or the Lozinskiĭ measure.

In statistical mechanics, the Griffiths inequality, sometimes also called Griffiths–Kelly–Sherman inequality or GKS inequality, named after Robert B. Griffiths, is a correlation inequality for ferromagnetic spin systems. Informally, it says that in ferromagnetic spin systems, if the 'a-priori distribution' of the spin is invariant under spin flipping, the correlation of any monomial of the spins is non-negative; and the two point correlation of two monomial of the spins is non-negative.

In probability theory, concentration inequalities provide bounds on how a random variable deviates from some value. The law of large numbers of classical probability theory states that sums of independent random variables are, under very mild conditions, close to their expectation with a large probability. Such sums are the most basic examples of random variables concentrated around their mean. Recent results show that such behavior is shared by other functions of independent random variables.

References

↑ 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.
↑ 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)
↑ 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)
1 2 Datta, Somantika; Howard, Stephen; Cochran, Douglas (2012-05-29). "Geometry of the Welch Bounds". arXiv: 0909.0206 .{{cite journal}}: Cite journal requires |journal= (help)

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[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)

[:0-4] 1 2 Datta, Somantika; Howard, Stephen; Cochran, Douglas (2012-05-29). "Geometry of the Welch Bounds". arXiv: 0909.0206 .{{cite journal}}: Cite journal requires |journal= (help)

[1]

[2]

[3]

[4]