16
$\begingroup$

I saw that two random independent vectors are approximately orthogonal in high dimensional space.

How can I prove this? And is there an intuitive explanation?

Thank you.

$\endgroup$
  • 11
    $\begingroup$ @DouglasZare I assume you mean "multi-variable", not "single variable". But I must respectfully disagree with you that this is too elementary for MO. i never saw it in either undergraduate or graduate classes and only ran across it when working with lattices in cryptography. (My guess is the that OP found this statement in such an article, but you are right that he/she should have given the reference.) $\endgroup$ – Joe Silverman Aug 28 '16 at 15:47
  • 5
    $\begingroup$ I don't think answers in this depth and intuition would have been available in Math.Stackexchange. Maybe it should be re-opened? $\endgroup$ – Amir Sagiv Aug 28 '16 at 17:22
  • 5
    $\begingroup$ @ChristianRemling While one can understand the question asked here as answered by the same circle of ideas as "concentration of measure", I think it is excessive to regard this as a duplicate of those earlier questions $\endgroup$ – Yemon Choi Aug 28 '16 at 21:34
  • 7
    $\begingroup$ Moreover, to those who seem to have voted or are voting to close because the question is "not research level", doesn't this fit under one of MO's original remits: "questions that an expert from another area could answer easily, which are not part of the usual general UG mathematical education"? $\endgroup$ – Yemon Choi Aug 28 '16 at 21:35
  • 6
    $\begingroup$ @RW If you like, we could continue this discussion in chat or over email or, if anyone still uses it, on tea.mathoverflow.net However, as someone who has needed character theory of finite groups that is in Isaacs's book, apparently standard knowledge to various algebraists on MathOverflow, but certainly not part of a functional analyst's toolkit, I feel quite strongly that one person's "obviously not research level" is another person's "exactly what I need to get me past a roadblock in my own research". $\endgroup$ – Yemon Choi Aug 29 '16 at 11:19
22
$\begingroup$

There are many ways to interpret this question depending on how you "randomly" choose your vectors. Here's one example. Take the set of vectors $v\in\{-1,1\}^N$, where the coordinates of $v$ are chosen independently to be $+1$ half the time and $-1$ half the time. Then an easy calculation shows that the expected value of $$\frac{|v_1\cdot v_2|^2}{|v_1|^2|v_2|^2} \quad\text{is equal to}\quad\frac{1}{N}.$$ In other words, the expected value of $\cos^2\theta$, where $\theta$ is the angle between two randomly chosen vectors in this set, is $\frac{1}{N}$, which shows that randomly chosen vectors are reasonably orthogonal to one another if $N$ is large. One can compute the higher moments $\cos^{2k}\theta$ to get further information. Other random distributions may be computed similarly, for example the set of vectors whose coordinates are independently distributed in the interval $[-1,1]$.

I don't really have a good intuitive explanation, because I have trouble visualizing $N$ dimensional space. (By "intuitive", I'm assuming you mean "geometrically intuitive.")

For those who have voted to close this question, please don't. It does require some clarification to answer carefully, but it is an important principle in, for example, lattice-based cryptography.

$\endgroup$
  • 12
    $\begingroup$ Depending on your definition of "intuition", it's not too bad to get a rough idea for why this is: the first vector specifies 1 direction in an N-dimensional space. The second vector should have a much smaller overlap with that 1 direction than the remaining N-1 orthogonal directions. $\endgroup$ – Nathaniel Johnston Aug 28 '16 at 13:57
13
$\begingroup$

The results from a large number of repeated trials can be viewed as a random point in a high-dimensional space, so we can use our intuition about probability in the long run as a substitute for our inability to visualize geometry in high dimensions. The "trend towards the mean" after many repeated trials of the same experiment explains why you should expect such phenomena only in high dimensions. I will focus on the intuition, rather than a rigorous proof, since you asked about both and I think it's good to see why you should expect this type of result before reading a proof about it.

If you flip a fair coin a large number of times you would expect on average to have about as many heads as tails. Assigning "1" to an outcome of heads and "0" to an outcome of tails, for a sequence of $n$ independent coin flips $(x_1,\ldots,x_n)$ where $n$ is large you'd expect the average $(\sum x_i)/n$ to be very close to $1/2$. To recenter the data around $0$ instead of $1/2$, apply the affine transformation $y_i = 2x_i -1$. Then $y_i = 1$ or $-1$ and $(y_1,y_2,\ldots,y_n)$ is a random sequence from $\{\pm 1\}$ with average value $(\sum y_i)/n = 2(\sum x_i)/n - (\sum 1)/n = 2(\sum x_i)/n -1$ very close to $2(1/2) -1 = 0$ when $n$ is very large.

Everything I wrote above goes through if you replace the discrete $x_i$ in $\{0,1\}$ with uniformly chosen $x_i$ in $[0,1]$, so $y_i = 2x_i-1$ becomes a uniform random variable in $[-1,1]$. A vector $(y_1,\ldots,y_n)$ with coordinates chosen randomly (independently and uniformly) in $[-1,1]$ is, for large $n$ (not small $n$ like $2$ or $3$!) very likely to have the average of the coordinates nearly equal to $0$.

Now we make a connection to geometry. The average $(\sum y_i)/n$ can be viewed as the dot product of the vectors $\mathbf y = (y_1,\ldots,y_n)$ and $\mathbf v = (1/n,\ldots,1/n)$, so $\mathbf y \cdot \mathbf v$ is most likely small when $n$ is large. Intuitively you might think "small dot product means they are nearly orthogonal," but the dot product involves the length of the vectors, not only the angle between them, so a dot product might be small because one of the vectors is small. And indeed $\mathbf v$ has length $1/\sqrt{n}$, which tends to $0$ as $n \rightarrow \infty$. Maybe the angle between $\mathbf y$ and $\mathbf v$ doesn't matter? A little algebra will help us focus on the angle instead of the lengths.

Rewrite the dot product $\mathbf y\cdot \mathbf v$ as $(\mathbf y/\sqrt{n})\cdot \mathbf u$ where $\mathbf u = (1/\sqrt{n},\ldots,1/\sqrt{n})$ is a specific unit vector in $\mathbf R^n$. Since $||\mathbf y|| \leq \sqrt{n}$, and equality is certainly possible, the vector $\mathbf y/\sqrt{n}$ is a "random" vector in the unit ball of $\mathbf R^n$. Therefore our probabilistic intuition suggests that a random vector in the unit ball of $\mathbf R^n$ is very likely to have a small dot product with the specific unit vector $\mathbf u$. But geometrically what makes $\mathbf u$ so special? We can transform one unit vector to any other unit vector by a rotation (orthogonal transformation), and rotations do not change distances or dot products, so we are led to expect a random vector in the unit ball of $\mathbf R^n$ and a random unit vector in $\mathbf R^n$ to have a small dot product when $n$ is large. The unit ball and the unit sphere are different objects, but the following claim will let us put them on more of an equal footing in high dimensions.

Claim: most of the unit ball in $\mathbf R^n$ consists of vectors near the boundary when $n$ is large.

To explain the claim pick a small $\varepsilon > 0$ and divide the unit ball in $\mathbf R^n$ into $\{\mathbf w : ||\mathbf w|| \leq 1-\varepsilon\}$ and $\{\mathbf w : 1-\varepsilon < ||\mathbf w|| \leq 1\}$. The second set is all the vectors in the unit ball that are near the boundary and the first set has $n$-dimensional volume $(1-\varepsilon)^nb_n$, where $b_n$ is the volume of the $n$-dimensional unit ball. It turns out that even though the volume $2^n$ of the $n$-dimensional cube $[-1,1]^n$ explodes for large $n$ the unit-ball volume $b_n$ is bounded above as $n$ varies (I don't think this critical fact is intuitive; the value of $b_n$ is maximized at $n = 5$ or $6$ and actually tends to $0$ as $n$ gets large), so for fixed $\varepsilon > 0$ that first set has volume tending to $0$ as $n$ gets large because $(1-\varepsilon)^n \rightarrow 0$ as $n \rightarrow \infty$ no matter how ultra-tiny $\varepsilon$ is (you'd just better not make $\varepsilon$ depend on $n$). Thus, if you pick $\varepsilon$ and then make $n$ big enough, the bulk of the unit ball in $\mathbf R^n$ is in the second set. This completes the justification of the claim (including showing what it really means).

By the claim, in high dimensions a random vector in the unit ball is likely to be near the unit sphere, so we can say that picking a random vector in the unit ball is essentially the same as picking a random unit vector when we are in high dimensions (certainly not in two or three dimensions). We can finally interpret our original intuition that the average $(\sum y_i)/n$ is likely to be near $0$ when $n$ is large as saying that two random unit vectors in $\mathbf R^n$ are likely to have a small dot product, and for unit vectors (or just vectors bounded away from the origin), having a small dot product means the vectors are nearly orthogonal.

$\endgroup$
12
$\begingroup$

Pick two random unit vectors. After picking the first vector, switch to a coordinate system in which this is the first basis vector. The probability distribution for the second vector is assumed to be uniform among all directions, and so should assign an average magnitude of $\approx 1/\sqrt{n}$ to each component, making the dot product between the two vectors $\approx 1/\sqrt{n}$ as well. You have to split up the "total alloted length" of $1$ among increasingly many directions, only one of which counts toward non-orthogonality.

$\endgroup$
  • $\begingroup$ Imagine picking the second vector by doing a random walk where at each step, you first pick an axis, then take a step forward or back along that axis. There are $n-1$ choices that are all orthogonal to the first vector and only one choice that is not orthogonal. $\endgroup$ – usul Aug 31 '16 at 10:27
6
$\begingroup$

I think there is a stronger statement for large n. If you have n unit vectors (thought of as n points chosen uniformly at random on the sphere in R^n), and put them into the rows of an n x n matrix, the matrix will be nearly orthogonal. So you can choose n vectors at a time, not just 2!

You can test this by filling an n x n matrix with draws from a normal distribution with mean zero and standard deviation 1/sqrt(n). Each row will be approximately unit length, distributed uniformly at random near the sphere, and the whole matrix will be nearly orthogonal.

$\endgroup$
4
$\begingroup$

The key term here is the measure concentration phenomenon, explored in the work of Vitaly Milman and others. This refers to the fact that on a high-dimensional sphere most of the volume is concentrated near the equatorial hemisphere. If one assumes that one's probability distribution is uniform with respect to area, then this phenomenon is equivalent to the statement that a second vector chosen at random will be close to orthogonal to the original one. This is essentially a development of Yemon Choi's comment.

$\endgroup$
3
$\begingroup$

One way to come at this is to try to stretch your intuition even farther, toward the Johnson-Lindenstrauss lemma, which says that while we can only fit $n$ orthogonal vectors into $\mathbb{R}^n$, we can easily (randomly) fit exponentially many almost-orthogonal vectors. The precise statement of the lemma includes the result you mention as a special case, so it's not really fair to say it provides the intuition. Rather I mention it because if you can fit it into your toolbox for thinking about high dimensions it will make other things more intuitive.

$\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.