Mutual сoherence II

Arthur Gilmullin, a friend of mine, recently came up with another solution of the mutual coherence problem. It also works for  n > 2  (where  n  is the space dimension). The reformulation of the bound is also due to him.

Here is the general problem: we have p distinct vectors  a_1,\, ...,\, a_p  on the n-dimensional unit sphere and are interested in proving that for any such configuration there is a pair  (a_i, a_j),  i \ne j,  such that  |\cos (a_i, a_j)| \ge A_{n,p}  where  A_{n,p}  is some predefined number. As I wrote, for  n = 2  it holds

\displaystyle A_{2, p} = \left|\cos \frac{\pi}{p}\right|.

Let us now prove that

\displaystyle A_{n, p} = \left|\cos \frac{\pi(n-1)}{\lfloor p^{1/(n-1)} \rfloor }\right|.

To describe the position of a vector on a unit sphere on  \mathbb{R}^n  we need  n-1  angles  \varphi_1,\, ...,\, \varphi_{n-1}.  Divide the range  [0, 2\pi]  of possible values of  \varphi_1  to  k  equal (subsequent) half-intervals. Due to Dirichlet’s principle, there is at least one of them containing  \lceil \frac{p}{k} \rceil vectors. For these vectors the same argument works with  \varphi_2,  etc. Finally, we have  \ge \frac{p}{k^{n-1}} vectors for which each angular coordinate differ not more than by  2\pi/k.  Now choose  k such that  |\cos 2\pi/k|  is as big as possible but still providing  \frac{p}{k^{n-1}} \ge 1, so that Dirichlet principle still works. That is,  k = \lfloor p^{1/(n-1)} \rfloor.  So there is a pair of vectors with all angles  \varphi_i differing not more than by  \pi/\lfloor p^{1/(n-1)}\rfloor.  Finally, apply spherical triangle inequality concluding that there must be 2 points with angular distance not more than  \pi(n-1)/\lfloor p^{1/(n-1)} \rfloor.  Note also that for any  \varphi_i  we can actually identify the opposite intervals, since the corresponding change of  \varphi_i  in one term doesn’t affect the absolute value of the dot product.

About Dmitry Ostrovsky

PhD student with interests in statistics, optimization, and machine learning.

Leave a Reply


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

Google+ photo


Twitter picture


Facebook photo



Connecting to %s