27
$\begingroup$

This is to do with high dimensional geometry, which I'm always useless with. Suppose we have some large integer $n$ and some small $\epsilon>0$. Working in the unit sphere of $\mathbb R^n$ or $\mathbb C^n$, I want to pick a large family of vectors $(u_i)_{i=1}^k$ which is almost orthogonal in the sense that $|(u_i|u_j)| < \epsilon$ when $i\not=j$. I guess I'm interested in how the biggest choice of $k$ grows with $n$ and $\epsilon$.

For example, we can let $\{u_1,\cdots,u_n\}$ be the usual basis, and then choose $u_{n+1} = (1,1,\cdots,1)/n^{1/2}$, which works if $n^{-1/2} < \epsilon$. Then you can let $u_{n+2} = (1,\cdots,1,-1,\cdots,-1)/n^{1/2}$ and so forth, but it's not clear to me how far you can go.

$\endgroup$
5
  • $\begingroup$ Hi Matt. I have a dim recollection of the following question rom 2nd-year undergrad homework: given $k$ almost orthogonal vectors in $R^k$ in the sense you describe, obtain a lower bound on the dimension $n$ of the subspace they span. Turning this round would seem to give an upper bound on $k$ in terms of $n$, I think? $\endgroup$
    – Yemon Choi
    May 16, 2010 at 9:30
  • $\begingroup$ I've accepted Bill's answer, as it was the first to give a nice asymptotic answer. I thought that this was an innocuous question, but it's generated some nice responses. Thanks all. $\endgroup$ May 17, 2010 at 8:13
  • $\begingroup$ I read a related article "A cheap version of the Kabatjanskii-Levenstein bound for almost orthogonal vectors" (terrytao.wordpress.com/2013/07/18/…), it declares that: for any fixed K >= 1, one can pack n^K unit vectors into R^n whose inner products are all of size O( K^(1/2) n^(-1/2) log(n)^(1/2) ). Could anyone please help me by giving more details on the proof of this statement, or point to me where to find the proof. I am a newcommer to high-dimensional space. Any reply will be appreciated greatly. $\endgroup$
    – user80637
    Sep 24, 2015 at 3:09
  • $\begingroup$ The comment section of Tao's blog might be a good place for this. $\endgroup$ Sep 24, 2015 at 3:56
  • $\begingroup$ In coding theory there are explicit constructions. See the links in Robin Chapman's answer for relatively low dimensional cases, where relatively exact information can be given. In a related MSE thread I describe one construction with somewhat flexible parameters. $\endgroup$ Apr 24, 2023 at 16:20

6 Answers 6

23
$\begingroup$

Matt, to get $k$ points, you only need $n\ge C \epsilon^{-2} \log k$. See http://en.wikipedia.org/wiki/Johnson%E2%80%93Lindenstrauss_lemma or Google "Johnson-Lindenstrauss lemma".

$\endgroup$
4
  • $\begingroup$ Bill, do you know anything about this constant $C$? The wiki says $8$, but do you know a paper which contains the best known one? $\endgroup$
    – Favst
    May 29, 2013 at 5:18
  • 1
    $\begingroup$ Can anyone explain how this follows from the JL Lemma? (I know one can prove it using the same techniques as JL, but I don't see how it directly applies.) $\endgroup$
    – usul
    Nov 14, 2019 at 22:59
  • 1
    $\begingroup$ I believe the point is to apply JL to $\{0,e_1,\ldots,e_k\}\subseteq\mathbb{R}^k$ to find $u_1,\ldots,u_k\in\mathbb{R}^n$ such that each $\|u_j\|=1+O(\varepsilon)$ and each $\langle u_j,u_l\rangle=O(\varepsilon)$ for $j\neq l$. $\endgroup$ Jun 13, 2023 at 22:11
  • $\begingroup$ @Favst, a comment has recently been added to the talk page on the wikipedia with a claimed source for the constant. $\endgroup$ Nov 2, 2023 at 5:33
24
$\begingroup$

The following has always been one of my favourite facts in extremal combinatorics.

  • If you want to pick unit vectors in R^n such that the inner product between any two of them is at most 0, then the best you can do is choose 2n vectors (an orthonormal basis and minus that basis)
  • If you relax the condition to "at most epsilon" then you can get exponentially many by a volume argument or probabilistic methods, as other people have remarked.
  • And if you go in the other direction, insisting that the inner product is at most -epsilon, then the biggest number of vectors you can choose is bounded above independently of n -- it's of order 1/epsilon. To prove that last fact, you calculate the norm of the sum of the vectors in two different ways -- a nice exercise I won't do here.

I don't know how much is known if you impose the condition that no inner product is more than epsilon(n) for some function that tends to zero from above. It's not clear that the simple probabilistic argument gives the right result in this regime.

But in general I very much like the way the function has three such different behaviours.

$\endgroup$
4
  • 2
    $\begingroup$ @Tim: The standard volume argument using a maximal ${\sqrt 2} -\epsilon$-separated set seems not to work. What volume argument do you have in mind? $\endgroup$ May 17, 2010 at 11:43
  • $\begingroup$ Almost a year later I've just seen your comment. I had in mind that each point you put in rules out a spherical cap of spherical radius $\pi/2-\epsilon$. Since this has exponentially small volume, you can just greedily add exponentially many points. I think we must be talking at cross purposes though ... $\endgroup$
    – gowers
    May 14, 2011 at 20:03
  • 3
    $\begingroup$ Looking at this almost a further year later, I'm still confused by Bill's remark, because what I wrote in the previous comment seems (i) correct and (ii) the standard volume argument that he discusses. Can anyone shed light on this? $\endgroup$
    – gowers
    Apr 3, 2012 at 13:12
  • 3
    $\begingroup$ (four years later now) I think the confusion comes from the fact there are two different "standard volume arguments" (1) The greedy algorithm, which works primarily in the unit sphere (a "surface" argument) and (2) The argument based on the fact that a maximal delta-separated set is delta-dense, which works primarily in the unit ball (a genuine "volume" argument). In the present situation, (1) applies but (2) doesn't. $\endgroup$ Jun 14, 2014 at 12:23
14
$\begingroup$

Indeed, what Bill Johnson wrote can hold even for points all of whose coordinates are $\pm 1/\sqrt{n}$. First choose $k = \exp(\epsilon^2 n/4)$ vectors $v_1, \dots, v_k$ by choosing each coordinate to be $\pm 1$ with probability $1/2$ each. Then define $u_i = v_i/\sqrt{n}$. A Chernoff bound shows that the probability of $|\langle u_i, u_j \rangle| \geq \epsilon$ is at most $2 \exp(-(\epsilon^2/2)n)$. This equals $2/k^2$ by choice of $k$, and hence one can take a Union Bound over the at most $\binom{k}{2} < k^2/2$ pairs $(i,j)$ to show that there's a positive probability of $|\langle u_i, u_j \rangle| < \epsilon$ holding for all $i \neq j$.

PS: Perhaps I got the constants wrong, but they can always be adjusted to make things work out.

$\endgroup$
1
  • $\begingroup$ I have a somewhat related question. If I choose 2 orthogonal vectors of length $n$ uniformly at random (from the suitable Haar measure), and then keep their first $k$ coordinates. What can I say regarding the probability that the inner product of these two new vectors (first $k$ coordinates of the original orthogonal vector) is larger than some $\epsilon$? $\endgroup$
    – Student88
    Nov 9, 2022 at 7:26
13
$\begingroup$

The Johnson-Lindenstrauss lemma states that you can have $k = 2^{\Omega(\epsilon^2 n)}$. It's also known that you cannot have $k$ larger than $2^{O(\epsilon^2 \log(1/\epsilon) n)}$ so that the Johnson-Lindenstrauss lemma gives you a near-tight answer. See the last section of "Problems and results in Extremal Combinatorics Part I" by Noga Alon for a proof of this latter fact.

$\endgroup$
13
$\begingroup$

At least in the real case the buzzword is "spherical codes".
http://mathworld.wolfram.com/SphericalCode.html
http://neilsloane.com/packings/

The idea is to find as large as possible a set on an $n$-sphere whose distances are at least a given amount apart. It's a spherical geometry analogue of the dense sphere-packing problem and generalizes the kissing number problem for spheres.

As with these classical problems, lots of partial results are known but rather fewer are proved to be optimal.

$\endgroup$
1
  • $\begingroup$ "buzzword" is correct: I'd done some searching for "almost orthogonal", but found rather different problems! But this is exactly what I was after (although it seems that classically the interest is in low dimensions...) $\endgroup$ May 16, 2010 at 8:07
5
$\begingroup$

This was too long to be a comment, my apologies:

Further to Tim Gowers' comment and the following discussion, Chapter 6 of Bollobas' lovely white book "Combinatorics - set systems hypergraphs, families of vectors, and combinatorial probability" studies exactly this kind of question,.

In fact Tim's comment corresponds to Theorem 6 in that chapter of the book, I believe. The language of that theorem uses symmetric difference of subsets of $\{1,2,..,n\}$, which can be converted to inner products of normalized $n$ dimensional vectors with entries $\pm 1/\sqrt{n}$.

Let $\epsilon>0$ be small. The second case of Theorem 6 essentially states that if the normalized inner product is allowed to be in $[-1,\epsilon]$, equivalently, if the pairwise symmetric differences of the sets in the family are all slightly less than $n/2$ in relative terms, then the number of sets in the family, and hence the number of vectors with entries $\pm 1/\sqrt{n}$ can be as large as $2^{\epsilon n}.$

The proof of this part of the Theorem is given as an exercise with a nice hint in the book: Focus on subsets of size $k=\lceil n/2 \rceil$ and do sphere packing in the Hamming space.

The variation with the OPs question is that the allowed range for the normalized inner product is $[-\epsilon, +\epsilon]$ in the OPs question. From Jelani Nelson's answer, it seems that the penalty for restricting the inner product to a band is perhaps not as severe as one might expect. We go from $\epsilon n$ down to $\epsilon^2 \log(1/\epsilon)n$ in the exponent.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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