# Bounds on the coherence of very flat matrices (that are more tight than the Welch bound)

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.

## 1 Answer

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$: 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.