Today, after getting to know about Mutual coherence, I became interested in the following problem. Let be an matrix, with distinct columns on a unit sphere in Its *mutual coherence* is then defined as

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

Welch bound is written as follows:

For this bound is trivial (equal to for any ). It is also sharp: all vectors are then just points I started to think how the bound can potentially be proved for and didn’t succeed. However, I came up with another bound. I asked a natural question: is it true that for

i.e. there is something here dealing with the symmetricity (which is natural since we have a objective in our optimization problem)? It is really true for (and, at least for big enough, way better than the earlier bound ). Indeed, adjacent angles must sum up to so the smallest of them is not greater than and is a decreasing function for Let be the vertex angles of a -polygon inscribed in a circle. It seems very doubtful that one can arrange its vertices so that not only all but also all consequent sums like or (apart from the full sum ) get into either of two intervals.

**Proof.** Of the points there should be two adjacent points with an angle not greater than between them. ♦

### Like this:

Like Loading...

## About Dmitry Ostrovsky

PhD student with interests in learning theory, statistics, and optimization, working with Anatoli Juditsky and Zaid Harchaoui.

Pingback: Mutual coherence – 2 | Mimicking the Oracle

Pingback: Mutual Coherence revisited | Mimicking the Oracle