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.

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:

WordPress.com Logo

You are commenting using your WordPress.com 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