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.
This entry was posted in Pretty little things. Bookmark the permalink.

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 )

Google photo

You are commenting using your Google 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 )

Connecting to %s