24
$\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$
7
  • 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
  • 6
    $\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
24
$\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$
0
10
$\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$
1
  • $\begingroup$ In the first computation, it helped me to add some steps. First, note that $\sum_{j=1}^{n}|y_j|^2 = |y|^2 = 1$ when $y \in S$, the unit sphere. In going from $\frac{1}{n}\int n |y_1|^2 dS(y)$ to $\frac{1}{n} \int \sum_{j=1}^{n}|y_{j}|^2 dS(y)$ we might note that we are splitting up the integral and applying dS-invatiant permutations $1\rightarrow j$ for all $j$. V is measuring the variance, and this being small means the average (expectation value) of $e \cdot y$ should be close to 0. We could also apply a dS-invariant rotation matrix to $e$ to show invariance of choice of reference vector. $\endgroup$ – Jackson Walters Sep 16 '20 at 22:09
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$
0
$\begingroup$

In statistics orthogonality is deeply linked to correlation. Random vectors are orthogonal when the values they contain are uncorrelated, meaning that in the $x_i$ values of $\vec{v_1}$ and $\vec{v_2}$ do not appear common patterns. The higher the dimension is the higher is $i$ and so the probability is higher that $x_{i}$ value of $\vec{v_1}$ and the $x_i$ values of $\vec{v_2}$ have no common pattern, because the higher the dimension the higher the possibilities (in an urn problem increase the number of balls ...). Equivalent to the statement that $\vec{v_1}$ and $\vec{v_2}$ have no common patterns is the statement that they are uncorrelated what is equivalent to the statement that they are orthogonal.

So the key to understand why randomly drawn vectors are perpendicular in high dimensions is the deep link between orthogonality and statistical correlation :

https://stats.stackexchange.com/questions/171324/what-is-the-relationship-between-orthogonal-correlation-and-independence

This is linked to a more philosophical question if real randomness actually exists. There are strong hints that this is not the case, i.e. nonlinear dynamical systems (chaotic systems) are able to generate white noise in a deterministic way : https://ieeexplore.ieee.org/document/1236865 - Chaotic maps generating white noise

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