# A cheap version of the Kabatjanskii-Levenstein bound for almost orthogonal vectors

Let $latex {n}&fg=000000$ be a natural number. We consider the question of how many “almost orthogonal” unit vectors $latex {v_1,\ldots,v_m}&fg=000000$ one can place in the Euclidean space $latex {{\bf R}^n}&fg=000000$. Of course, if we insist on $latex {v_1,\ldots,v_m}&fg=000000$ being exactly orthogonal, so that $latex {\langle v_i,v_j \rangle = 0}&fg=000000$ for all distinct $latex {i,j}&fg=000000$, then we can only pack at most $latex {n}&fg=000000$ unit vectors into this space. However, if one is willing to relax the orthogonality condition a little, so that $latex {\langle v_i,v_j\rangle}&fg=000000$ is small rather than zero, then one can pack a lot more unit vectors into $latex {{\bf R}^n}&fg=000000$, due to the important fact that pairs of vectors in high dimensions are typically almost orthogonal to each other. For instance, if one chooses $latex {v_i}&fg=000000$ uniformly and independently at random on the unit sphere, then a standard computation (based on viewing the $latex {v_i}&fg=000000$ as gaussian…

Ver la entrada original 1.027 palabras más

Anuncios