Introduction

High dimensional spaces behave in many ways that are counter-intuitive to us. Of course, that is bound to happen as we are creatures that inhabit a 3D space and what we see around us shape our intuition. However, there is immense utility, particularly in the craft of data sciences and machine learning, in being able to manipulate these properties to our advantage. This stems from the fact that our data gathering and processing ability has exploded in the recent decades.

We deal with feature spaces that are high dimensional and algorithms that are designed to work in such spaces.

Richard Bellman, a computer scientist, coined the phrase ‘curse of dimensionality’ as he was confronted with the failure of certain algorithms in translating their predictive power to higher dimensions. The failure can be computational, i.e, the inability to scale in a way that is computationally feasible. The inability can also be poor performance in terms of accuracy of the model/algorithm.

Weird stuff that happens in high dimensional spaces

1. Two random vectors are almost always orthogonal

Now this is something that should concern us, as it goes against everything we would expect. But as it turns out, high dimensional spaces are so vast and weird, if you pick two random vectors, the angle between them will almost always be 90, in a high dimensional space.

Let $\mathbf{a}$ and $\mathbf{b}$ be two independent random unit vectors in $n$-dimensional space. We want to understand why their angle is usually close to $90^\circ$ when $n$ is large.

Want to reproduce the experiment? The animated Python demo is available in the public repository: Random directions become orthogonal. Clone it, install the two dependencies, and run the script to watch the angle distribution tighten around $90^\circ$ as the dimension increases.

Angle and dot product

For any two vectors,

$$\mathbf{a} \cdot \mathbf{b} = \lVert\mathbf{a}\rVert\lVert\mathbf{b}\rVert\cos\theta.$$

Because $\mathbf{a}$ and $\mathbf{b}$ are unit vectors,

$$\lVert\mathbf{a}\rVert = \lVert\mathbf{b}\rVert = 1.$$

Therefore,

$$\cos\theta = \mathbf{a} \cdot \mathbf{b}.$$

So instead of studying the angle directly, we study the dot product. If $\mathbf{a} \cdot \mathbf{b} = 0$, then $\theta = 90^\circ$. If $\mathbf{a} \cdot \mathbf{b}$ is close to $0$, then $\theta$ is close to $90^\circ$.

Rotate one vector to a simple position

Because the directions are uniformly random, no direction is special. We may imagine rotating the entire coordinate system so that

$$\mathbf{a} = (1, 0, 0, \ldots, 0).$$

Rotating everything does not change the angle between $\mathbf{a}$ and $\mathbf{b}$. Write

$$\mathbf{b} = (b_1, b_2, \ldots, b_n).$$

Then

$$\mathbf{a} \cdot \mathbf{b} = (1, 0, \ldots, 0) \cdot (b_1, b_2, \ldots, b_n) = b_1.$$

Therefore,

$$\cos\theta = b_1.$$

The problem has become: what does one coordinate of a random unit vector look like?

Why its average is zero

The vector $\mathbf{b}$ is equally likely to point in any direction. Therefore, its first coordinate $b_1$ is equally likely to be positive or negative: values such as $0.2$ and $-0.2$ are equally likely. These positive and negative values cancel on average, so

$$\mathbb{E}[b_1] = 0.$$

Since $\cos\theta = b_1$,

$$\mathbb{E}[\cos\theta] = 0.$$

This means the cosine is centered around zero.

Why its variance is $1/n$

Because $\mathbf{b}$ is a unit vector,

$$b_1^2 + b_2^2 + \cdots + b_n^2 = 1.$$

All coordinates behave in the same way because no coordinate direction is special. So, on average, each squared coordinate contributes the same amount to the total $1$. There are $n$ coordinates, so each contributes $1/n$:

$$\mathbb{E}[b_1^2] = \frac{1}{n}.$$

Since the mean of $b_1$ is zero,

$$\operatorname{Var}(b_1) = \mathbb{E}[b_1^2] = \frac{1}{n}.$$

Thus,

$$\operatorname{Var}(\cos\theta) = \frac{1}{n} \qquad\text{and}\qquad \operatorname{SD}(\cos\theta) = \frac{1}{\sqrt{n}}.$$

This tells us the typical size of $\cos\theta$. For example, when $n = 100$, $1/\sqrt{n} = 0.1$; when $n = 10{,}000$, $1/\sqrt{n} = 0.01$. As the dimension grows, the cosine becomes more tightly concentrated around zero.

2. All points live on the surface

3. The shrinking Hypersphere
4. Everyone is far away but equally far away
5. The spiky hypercube

A demonstration of the failure of distance based algorithms

[Demonstrate how KNN fails in high dimensions] [Demonstrate how DBSCAN fails in high dimensions]

Why is high-dimensionality a curse

Two major causes for this can be described as follows:

1. Distance concentration
2. Manifold effect

Distance concentration is the phenomenon due to which the distances between any two points tend to the same value in high dimensions. This makes algorithms that use conventional distance metrics perform poorly.

Manifold effect is a cause but also at the same time a blessing. High dimensional data often does not occupy the entire space, but lives on a lower dimensional manifold embedded in the high dimensional space. This could mean that certain algorithms that utilise distance metrics as they come might not be able to capture important relationships in the data. However, the same property also is a blessing because now we do not have to deal with the immense empty spaces in high dimensions which would have made the our other algorithms infeasible as well.

Tangents

1. Learning in high dimensions always amounts to extrapolation
2. The impact of noise, or more importantly the Signal-To-Noise Ratio

Dealing with the curse of dimensionality

None of this means high dimensional data is unusable, only that the tools have to change with the geometry.

The most direct fix is to reduce the dimension before doing anything else. Methods like PCA, UMAP, or a trained autoencoder project the data onto the lower dimensional manifold it actually occupies, which is exactly the structure that made the empty space a problem in the first place. Feature selection does something similar by simply removing coordinates that add noise without adding signal.

Where the dimension has to stay high, it helps to pick algorithms that were never built around raw distance. Tree-based models split on one feature at a time rather than comparing distances across all of them, so they are far less sensitive to distance concentration. Cosine similarity is a smaller version of the same idea: because it measures the angle between vectors rather than their distance, it sidesteps the very effect we found in the first section, since it is the angle, not the magnitude, that keeps carrying signal as dimension grows.

Finally, more data helps less than it sounds like it should. The sample size needed to cover a space densely grows exponentially with dimension, so in practice we lean on regularization and strong priors to compensate for data that will never be dense enough to fill the space it occupies.