I am studying the coherence of matrices in the context of sparse recovery. Let us say I have a matrix $\mathbf \Phi$ of size $M \times N$ with, say, unit Euclidean norm columns ${\mathbf \varphi}_n$. I am looking at the largest inner product between two columns, i.e., $$\mu = \max_{n_1\neq n_2 \in [1, 2, \ldots, N]} \left|{\mathbf \varphi}_{n_1}^{\rm T} \cdot {\mathbf \varphi}_{n_2} \right|$$ It is known that this coherence is lower-bounded by $$ \mu \geq \sqrt{\frac{N-M}{M(N-1)}}, $$ a bound that I know by the name Welch bound. This bound is achieved if the columns of $\mathbf \Phi$ form an equiangular tight frame. In this case, all colums have the same (magnitude) inner product. It is known that such frames can only exist if $M^2 \geq N$. Unfortunately for me, the matrices I am looking at are very flat, i.e., I have $M < \sqrt{N}$.

In this case, the Welch bound is not very tight. In fact, it becomes quite bad for growing $N$. This is easy to see if we fix $M$ and let $N\rightarrow \infty$: The Welch bound converges to $\sqrt{\frac{1}{M}}$ but naturally, the coherence of any $\mathbf \Phi$ approaches 1.

So here comes the question: for $M \times N$ matrices with $M < \sqrt{N}$, are there lower bounds on the coherence that are more tight than what the Welch bound predicts? In particular, is there any bound that reflects the behavior $\lim_{N\rightarrow \infty} \mu = 1$ for fixed $M$?

P.S.: If anybody has a good idea how to construct such matrices (better than just trying Monte Carlo), this would also be highly appreciated.

up vote 2 down vote accepted

After a long time I can finally answer my own question: There is a better bound for large $N$ given by $$\mu \geq 1-2N^{-\frac{1}{M-1}}.$$ Since for smaller $N$ it may produce negative values, the compound bound is in fact $$\mu \geq \min\left(\sqrt{\frac{N-M}{M(N-1)}},1-2N^{-\frac{1}{M-1}}\right).$$ Obviously this bound satisfies $\lim_{N\rightarrow \infty} \mu=1$ for any $M>1$, as desired.

Here is an example for $M=5$:

Comparison of coherence bounds for M=5

I found it in the reference [XZG05].

[XZG05] P. Xia, S. Zhou, and G. Giannakis, "Achieving the Welch Bound with Difference Sets", IEEE Trans. Information Theory, vol. 51, no. 5, May 2005.

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.