Welch-bound equality

Posted on by Dustin G. Mixon

Historically, there has been some confusion over what it means for a short, fat matrix to have Welch-bound equality. There are actually some useful characterizations that come out of all of this, so bear with me as I go through a few frame-theoretic definitions:

In finite dimensions, a frame is a short, fat matrix which is full rank. The extreme singular values (squared) are called the frame bounds, and having nearly equal frame bounds corresponds to being well-conditioned, which is a beneficial property in the real world. The most well-conditioned frame is called a tight frame, which has the defining property that

(i) the rows are equal-norm and orthogonal.

Tight frames F are useful because they give a redundant linear encoding y=F^*x of a signal x that allows for painless recovery: x=\frac{1}{A}Fy, where A is the common squared-norm of the rows. Constructing tight frames is rather simple: perform Gram-Schmidt on the rows of any frame to orthogonalize them with equal norms. For the sake of democracy in the entries of the encoding y, some applications opt for a unit norm tight frame (UNTF), which has the additional property that

(ii) the columns are unit-norm.

Constructing UNTFs has proven a bit more difficult, and there’s been a lot of research to characterize these. As an example, taking any rows from a discrete Fourier transform matrix (and normalizing the resulting columns) will produce a UNTF since all of the entries have the same modulus. Finally, it is often beneficial to have the columns of F be incoherent, and this occurs when F is an equiangular tight frame (ETF), that is, a UNTF with the final property that

(iii) the inner products between distinct columns have equal size.

ETFs don’t exist for all matrix dimensions, and there are very few general constructions to date. Some of the biggest open problems in frame theory concern ETFs, but we’ll have to leave those for another post.

Now, there are two types of short, fat matrices that people like to call Welch-bound equality sequences: UNTFs and ETFs. As you’d expect, each one achieves equality in an important inequality, so let’s go over them. Here, we consider short, fat M\times N matrices F=[f_1\cdots f_N] which have (ii), but not necessarily (i) or (iii). As such, F might not even be a frame, but we can still take the Hilbert-Schmidt norm of the Gram matrix of its columns:

\displaystyle \|F^*F\|_{\mathrm{HS}}^2=\sum_{n=1}^N\sum_{n'=1}^N|\langle f_n,f_{n'}\rangle|^2.

This is often called the frame potential, and its significance will become apparent shortly. Since the columns of F have unit norm, and since F^*F has at most M nonzero eigenvalues, we have

\displaystyle N^2=\big(\mathrm{Tr}(F^*F)\big)^2=\bigg(\sum_{m=1}^M\lambda_m(F^*F)\bigg)^2\leq M\sum_{m=1}^M\big(\lambda_m(F^*F)\big)^2=M\|F^*F\|_{\mathrm{HS}}^2,

where the inequality follows from Cauchy-Schwarz with the all-ones vector. As such, equality is achieved if and only if the M largest eigenvalues of F^*F are equal; since these are also the eigenvalues of FF^*, this implies that FF^* is a multiple of the identity, and so F satisfies (i). Thus, the frame potential of F satisfies \|F^*F\|_{\mathrm{HS}}^2\geq N^2/M, with equality if and only if F is a UNTF. Some people call this the Welch bound, and therefore say that UNTFs have Welch-bound equality.

But there’s another bound out there that other people call the Welch bound, and its derivation actually uses the previous one. It concerns the worst-case coherence of a short, fat M\times N matrix F=[f_1\cdots f_N] that satisfies (ii):

\displaystyle \mu:=\max_{\substack{n,n'\in\{1,\ldots,N\}\\n\neq n'}}|\langle f_{n},f_{n'}\rangle|.

Since the columns of F have unit norm, we have

\displaystyle \frac{N^2}{M}\leq\|F^*F\|_{\mathrm{HS}}^2=\sum_{n=1}^N\sum_{n'=1}^N|\langle f_n,f_{n'}\rangle|^2\leq N+N(N-1)\mu^2.

Again, equality is achieved in the first inequality if and only if F satisfies (i). Also, equality is achieved in the second inequality if and only if F satisfies (iii). Rearranging gives the following bound:

\displaystyle \mu\geq\sqrt{\frac{N-M}{M(N-1)}},

with equality if and only if F is an ETF.

So which is actually the Welch bound? To resolve this, I defer to L.R. Welch’s original theorem statement:

Theorem (Welch bound). For every positive integer K,

\displaystyle \mu^{2K}\geq\frac{1}{N-1}\bigg(\frac{N}{\binom{M+K-1}{K}}-1\bigg).

As you can see, Welch actually gave an entire family of bounds, but they weren’t on the frame potential—they were on the worst-case coherence. In fact, the K=1 case of Welch’s theorem is precisely the worst-case coherence bound we found above. Therefore, it is probably more accurate to refer to ETFs as Welch-bound equality sequences, but I prefer to just call them ETFs.

As a side note, it is well known that M\times N ETFs must have N\leq M(M+1)/2 in the real case and N\leq M^2 in the complex case, and there are multiple proofs of these facts. What is probably less known is that the bound in the complex case can be derived using Welch bounds. (I just figured this out!) Indeed, for every fixed M, if we let N grow, then the Welch bound for K=2 will at some point exceed the bound for K=1, meaning equality in the K=1 bound is no longer achievable. This occurs as soon as

\displaystyle \bigg(\frac{2N-M(M+1)}{M(M+1)(N-1)}\bigg)^{1/4}>\bigg(\frac{N-M}{M(N-1)}\bigg)^{1/2}.

Raising both sides to the 4th power and rearranging then gives

\displaystyle 0<\big(2N-M(M+1)\big)M(N-1)-(M+1)(N-M)^2=(N-M^2)(M-1)N.

Since N\geq M>1, this means that ETFs cannot exist whenever N>M^2, as claimed.

4 thoughts on “Welch-bound equality”

  1. Pingback: Finite normalized tight frames « Short, Fat Matrices
  2. Pingback: Building frames from codes « Short, Fat Matrices
  3. Pingback: Achieving the Welch bound with difference sets « Short, Fat Matrices
  4. Pingback: AIM workshop: Frame theory intersects geometry | Short, Fat Matrices

Leave a comment