14
$\begingroup$

I am struggling understanding this finding. Can somebody explain intuitively why randomly drawn high-dimensional vectors will tend to be mutually orthogonal? I realize that intuition in high dimensions might be too much to ask for, still, an explanation without having to integrate over several pages of symbols would be preferred.

$\endgroup$
  • 2
    $\begingroup$ (A) what is the source for this (B) what do you know so far? $\endgroup$ – Will Jagy Oct 28 '14 at 21:07
  • 5
    $\begingroup$ Others are using more rigour, but I think it simply as follows. By rotational symmetry of the distribution you might as well look at the inner product of a random vector and $(1,0,0,\ldots,0)$. That inner product is zero-mean, but its variance will be $1/n$. So when $n$ is in the hundreds, you need quite a few SDs off the mean to have a significant inner product (for a suitable value of "significant"). $\endgroup$ – Jyrki Lahtonen Oct 28 '14 at 22:03
  • $\begingroup$ @JyrkiLahtonen I will edit my answer to incorporate this line of reasoning explicitly. $\endgroup$ – Jonas Dahlbæk Oct 29 '14 at 8:33
  • $\begingroup$ @user161825: I had already upvoted your answer among others :-) $\endgroup$ – Jyrki Lahtonen Oct 29 '14 at 11:07
  • $\begingroup$ @JyrkiLahtonen thank you - this is very helpful. $\endgroup$ – b87lar Oct 29 '14 at 14:56
16
$\begingroup$

A random uniform unit vector is $X/\|X\|$ where $X$ is standard normal, thus the scalar product of two independent unit vectors $U$ and $V$ is $\langle U,V\rangle=\langle X,Y\rangle/(\|X\|\cdot\|Y\|)$ where $X$ and $Y$ are independent and standard normal. When $n\to\infty$, by the law of large numbers, $\|X\|/\sqrt{n}\to1$ almost surely and $\|Y\|/\sqrt{n}\to1$ almost surely, and by the central limit theorem, $\langle X,Y\rangle/\sqrt{n}$ converges in distribution to a standard one-dimensional normal random variable $Z$.

Thus, $\sqrt{n}\cdot\langle U,V\rangle\to Z$ in distribution, in particular, for every $\varepsilon\gt0$, $P(|\langle U,V\rangle|\geqslant\varepsilon)\to0$. In this sense, when $n\to\infty$, the probability that $U$ and $V$ are nearly orthogonal goes to $1$.

Likewise, $k$ independent uniform unit vectors are nearly orthogonal with very high probability when $n\to\infty$, for every fixed $k$.

$\endgroup$
8
$\begingroup$

Here is one way to reason, chosen for simplicity of calculations: Consider the unit vector $e=(1,0,0,\ldots,0)\in\mathbb R^n$. One way to measure how 'orthogonal' $e$ is to other vectors is to calculate the average of $(e\cdot x)^2$ as $x$ ranges over the unit sphere. If $S$ denotes the surface measure on the unit sphere corresponding to (normalized) area, then $$ \int |e\cdot y|^2 dS(y) =\int |y_1|^2 dS(y)=\frac{1}{n}\int \sum_{j=1}^n |y_j|^2 dS(y)=\frac{1}{n}. $$ Thus, in this sense, vectors are generally 'more' orthogonal in higher dimensional spaces.

Edit: This line of reasoning follows closely the argument given by JyrkiLahtonen in the comments above, as one sees by considering a random $\mathbb R^n$-valued vector $Y$, uniformly distributed on the unit sphere. If we consider the random variable $e\cdot Y$, then $$ E \; e\cdot Y=\int e\cdot y \;dS(y)=0, $$ because $S$ in invariant under the transformation $y\mapsto -y$. On the other hand $$ V(e\cdot Y)=\int |e\cdot y|^2 dS(y) =\frac{1}{n}, $$ as shown above. Therefore, intuitively, $e\cdot Y$ is small when $n$ is large. Rigorously, we can employ Chebyshev's inequality to obtain $$ P(|e\cdot Y|\geq \epsilon)\leq \frac{1}{n\epsilon^2}. $$

$\endgroup$
3
$\begingroup$

Here's an excerpt from Lecture 2 of Keith Ball's An Elementary Introduction to Modern Convex Geometry:

excerpt

See the link for details, but as the image shows, the measure of a spherical cap cut off by a hyperplane which is $\varepsilon$ away from the origin is bounded above by the ratio between volume of a ball of radius $\sqrt{1-\varepsilon^2}$ and the volume of a ball of radius 1, that is, $(1-\varepsilon^2)^{n/2}$. So if $X$ and $Y$ are independent random unit vectors (uniform on the sphere), then $$ P(\langle X,Y\rangle < \varepsilon) \ge 1 - (1-\varepsilon^2)^{n/2} \ge 1 - e^{-n\varepsilon^2/2} $$ which is close to $1$ when $n$ is large (if $\varepsilon$ is fixed, at least).

$\endgroup$
-3
$\begingroup$

As the brief proof showed below, it does not matter to suppose that the vector c is the diagonal vector of the n vector from the standard basis in the n-dimensional vector space with inner-product. It means that the projection vector of c onto vi is the same length(norm) with each other (irrelevant to i). Any randomly drawn vector is the same as c.

enter image description here

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