11
$\begingroup$

This question was asked at math.stackexchange, where it got several upvotes but no answers.


It is impossible to find $n+1$ mutually orthonormal vectors in $R^n$.

However, it is well established that the central angle between legs of a regular simplex with $n$-dimensional volume goes as $\theta = \mathrm{arccos}(-1/n)$. This approaches $90$ degrees as $n \rightarrow \infty$, so since there are $n+1$ vertices of a simplex with $n$-dimensional volume, we can conclude

Given $\epsilon > 0$, there exists a $n$ such that we can find $n+1~$ approximately mutually orthogonal vectors in $\mathbb{R}^n$, up to tolerance $\epsilon$. (Unit vectors $u$ and $v$ are said to be approximately orthogonal to tolerance $\epsilon$ if their inner product satisfies $\langle u,v \rangle < \epsilon$)

My question is a natural generalization of this - if we can squeeze $n+1$ approximately mutually orthonormal vectors into $\mathbb{R}^n$ for $n$ sufficiently large, how many more vectors can we squeeze in? $n+2$? $n+m$ for any $m$? $2n$? $n^2$? $e^n$?


Actually the $n+m$ case is easy to construct from the $n+1$ case. Given $\epsilon$, one finds the $k$ such that you can have $k+1$ $\epsilon$-approximate mutually orthogonal unit vectors in $\mathbb{R}^k$. Call these vectors $v_1, v_2, ..., v_k$. Then you could squeeze $mk+m$ vectors in $\mathbb{R}^{mk}$, by using the vectors $$\begin{bmatrix} v_1 \\ 0 \\ \vdots \\ 0 \end{bmatrix}, \begin{bmatrix} v_2 \\ 0 \\ \vdots \\ 0 \end{bmatrix}, \begin{bmatrix} v_{k+1} \\ 0 \\ \vdots \\ 0 \end{bmatrix}, \begin{bmatrix} 0 \\ v_1 \\ \vdots \\ 0 \end{bmatrix}, \begin{bmatrix} 0 \\ v_2 \\ \vdots \\ 0 \end{bmatrix}, \begin{bmatrix} 0 \\ v_{k+1} \\ \vdots \\ 0 \end{bmatrix}, \dots \begin{bmatrix} 0 \\ 0 \\ \vdots \\ v_1 \\ \end{bmatrix}, \begin{bmatrix} 0 \\ 0 \\ \vdots \\ v_2 \\ \end{bmatrix}, \begin{bmatrix} 0 \\ 0 \\ \vdots \\ v_{k+1} \\ \end{bmatrix}. $$ So, setting $n = mk$, we have found an $n$ such that we can fit $n + m$ $\epsilon$-orthogonal unit vectors in $\mathbb{R}^n$.

I've haven't been able to construct anything stronger than $n+m$, but I also haven't been able to show that this is the upper bound.

$\endgroup$
  • 4
    $\begingroup$ The tag "measure-concentration" is a good hint: in large dimension, two uniform random unit vectors are close to orthogonal with very high probability, so you get (exponentially) many pairwise almost orthogonal vectors by simply drawing them at random. $\endgroup$ – Benoît Kloeckner Feb 25 '14 at 9:53
  • 7
    $\begingroup$ Getting $\epsilon^{-2} \exp n$ vectors is a special case of a very general result that is easy to prove. Google "Johnson-Lindenstrauss Lemma". $\endgroup$ – Bill Johnson Feb 25 '14 at 14:53
16
$\begingroup$

A set of points on the unit sphere in ${\Bbb R}^n$ with $\langle x,y\rangle \le \cos \theta$ for all distinct $x$ and $y$ is called a spherical code with minimum angle $\theta$. For $0<\theta < \pi/2$, Kabatiansky and Levenshtein gave an exponential upper bound (of the form $\exp(C(\theta)n)$) for the maximum number of points in such a spherical code. There is also an exponential lower bound. This is related to sphere packings. See for example the recent paper by Cohn and Zhao, which will have more references: http://arxiv.org/pdf/1212.5966v2.pdf

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Here is the paper by Kabatiansky & Levenshtein. The original Russian-language version is available for free. mathnet.ru/php/… I can't find the English-translation online; Springer only has "Problems of Information Transmission" back to volume 37 (January 2001). Cohn & Zhao claim simplify and strengthen their argument, so unlikely to be worth tracking down. $\endgroup$ – Jess Riedel Dec 28 '16 at 20:44
8
$\begingroup$

From the area estimates you get that that for fixed $\varepsilon>0$ this number, say $M_\varepsilon(n)$, grows quite fast.

Direct calculations show that the total area of the locus of unit vectors in $\mathbb{R}^{n}$ which are not $\varepsilon$-perependicular to the given vector $u$ is about $$2\cdot e^{-(n-2)\cdot\varepsilon^2/2}\cdot\mathop{\rm area}\mathbb{S}^{n-1}.$$

In particular, $$M_\varepsilon(n)>\tfrac12\cdot e^{(n-2)\cdot\varepsilon^2/2}>\tfrac{1}{100}\cdot\lambda^n$$ where $\lambda=e^{\varepsilon^2/2}>1$

| cite | improve this answer | |
$\endgroup$
3
$\begingroup$

This is also related to equiangular tight frames (ETFs). A frame is a kind of "overcomplete basis" of an inner product space; more precisely a family $(f_1,\dots,f_n)$ of vectors of an inner product space $V$ is a frame if there exist constants $A,B>0$ such that for all $f\in V$ it holds that $$A\|f\|^2\leq \sum |\langle f,f_k\rangle|^2\leq B\|f\|^2.$$ The frame is called tight, if $A=B$ and it is called equiangular if there is some $c$ such that for all $k,l$: $|\langle f_k,f_l\rangle|=c$.

"Equiangular tight frame" usually also means that the vector $f_k$ are normalized.

If you have an equiangular tight frame consisting of $n$ vectors in $\mathbb{R}^d$ (or $\mathbb{C}^d$) then it holds that $$|\langle f_k,f_l\rangle| = \sqrt{\frac{n-d}{d(n-1)}}.$$ Note that for $n=d+m$ and also for $n=d^m$ this number always goes to zero for $d\to\infty$ saying that the vectors become asymptotically orthogonal.

The only catch is, that equiangular tight frames do not always exist…

There are several construction, such as the Mecedes-Benz-frame (with $n=d+1$), see here . A pretty recent preprint on the existence of ETFs is "On the existence of equiangular tight frames" by Sustika, Tropp, Dhillon and Heath. In that paper you find the result that "maximal ETFs" (i.e. ones with the largest number of vectors) exist (not in all dimensions) but have the size $N=d(d+1)/2$ in the real case and $N=d^2$ in the complex case.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ The complex case with $N=d^2$ is also known as a SIC-POVM. They appear to have an interesting structure as the orbit of a certain representation of the Heisenberg group: mathoverflow.net/questions/2897/… $\endgroup$ – Yoav Kallus Feb 26 '14 at 2:30
3
$\begingroup$

Terry Tao has a nice blog post on a 'cheap version' of the Kabatjanskii-Levenstein bound mentioned in Lucia's answer, using the so-called 'tensor product trick'.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.