Weird Things in High Dimensions
Some weird stuff happens in high-dimensions.
1. High Dimensional Oranges Are Almost All Peel
Consider an $n$-dimensional cube of side length 1 containing a smaller $n$-dimensional cube with side length $0.8$ (“pulp”) surrounded by a $0.1$-width border (“peel”).
The volume of the pulp is $0.8^n$, which rapidly approaches 0 as $n$ increases:
| Dimensions | Pulp Volume ($0.8^n$) |
|---|---|
| 1 | 0.800 |
| 2 | 0.640 |
| 3 | 0.512 |
| 5 | 0.328 |
| 10 | 0.107 |
| 20 | 0.012 |
| 50 | 0.000014 |
Another perspective: To randomly sample a point in this cube, we select $n$ independent coordinates from $[0,1]$. The point lies in the pulp only if all coordinates fall within $(0.1, 0.9)$. This probability is $(0.8)^n$, approaching 0 as $n$ increases.
In high dimensions, the volume is almost all in the surface.
2. Unit spheres get smaller in high dimensions
todo
This is very weird and requires non-trivial math to show. Wikepdia
Good twitter post talking about this
Drake came up with a good explanation which is explained here
3. Spheres “spill out” in higher dimensions
4. Randomly chosen vectors in high-dimensional spaces are almost all orthogonal
The most intuitive explanation (in my opinion) is the probabilistic one. Two vectors are orthogonal if their dot product is 0.
$$ \langle x,y \rangle = \sum_{i=1}^n x_iy_i $$
Each $x_i$ and $y_i$ is randomly distributed from $[-1,1]$ which means that $\mathbb{E}[x_i y_i] = 0$ and the variance is proportional to $\frac{1}{n}$. This means that spread decreases with $n$.
When sampling only 2 or 3 times, the odds that you get a dot product close to 0 is not high, but because of the central limit theorem, sampling a lot means you almost always get really close to the mean.
5. Local minima are rare
todo