Mutual сoherence I

Today, after getting to know about Mutual coherence, I became interested in the following problem. Let $A$  be an $n \times p$  matrix, $p \ge 2,$  with distinct columns $a_1,\, ..,\, a_p$  on a unit sphere in $\mathbb{R}^n.$  Its mutual coherence is then defined as $\displaystyle M = \max_{i \ne j} |\langle a_i, a_j \rangle|.$

We are interested in the lower bound for $M$  holding for any matrix $A,$  that is, any given set of $p$  vectors on a unit sphere in $\mathbb{R}^n.$  Such bounds may be useful in compressed sensing,  where $A$  is “short and fat” in a sense that $p \gg n.$  From the practical point of view, considering $n << 1000$  is pointless; however, I decided to treat the case of very small $n$  because of its simplicity — and it seemed fun anyway.

Welch bound is written as follows: $\displaystyle M \ge \frac{p-n}{n(p-1)}.$

For $n = 1$  this bound is trivial (equal to $1$  for any $p$). It is also sharp: all vectors are then just points $\pm 1.$  I started to think how the bound can potentially be proved for $n = 2,$  and didn’t succeed. However, I came up with another bound. I asked a natural question: is it true that for $n=2,$ $\displaystyle M \ge \cos 2\pi/p,$

i.e. there is something here dealing with the symmetricity (which is natural since we have a $\ell_{\infty}$  objective in our optimization problem)? It is really true for $p \ge 4$  (and, at least for $p$  big enough, way better than the earlier bound $\frac{p-2}{2(p-1)}$).  Indeed, $p$  adjacent angles must sum up to $2 \pi,$  so the smallest of them is not greater than $2\pi/p < \pi/2,$  and $\cos x$  is a decreasing function for $x \cos\pi/p.$  Let $x_1,\, ..,\, x_p$  be the vertex angles of a $p$-polygon inscribed in a circle. It seems very doubtful that one can arrange its vertices so that not only all $x_1, .., x_p$  but also all consequent sums like $x_3 + x_4$  or $x_5 + x_1 + x_2 + x_3$  (apart from the full sum $x_1 + ... + x_p = 2\pi$)  get into either of two intervals.

Proof.  Of the $2p$  points $\pm a_1,\, ..,\, \pm a_p$  there should be two adjacent points with an angle not greater than $2\pi/(2p) = \pi/p$  between them. ♦ 