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 learning theory, statistics, and optimization, working with Anatoli Juditsky and Zaid Harchaoui.
This entry was posted in Pretty little things. Bookmark the permalink.

2 Responses to Mutual сoherence I

  1. Pingback: Mutual coherence – 2 | Mimicking the Oracle

  2. Pingback: Mutual Coherence revisited | Mimicking the Oracle

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s