## 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. ♦

## About Dmitry Ostrovsky

PhD student with interests in statistics, optimization, and machine learning.
This entry was posted in Pretty little things. Bookmark the permalink.