The Curse of Dimensionality

What is the Curse of Dimensionality?

When feature dimension $d$ grows large (e.g. $d = 10,000$ in text embeddings or gene data), geometry in $\mathbb{R}^d$ behaves in non-intuitive, counter-intuitive ways.

  1D Space (Line): 10 bins        2D Space (Grid): 10x10 = 100 bins    3D Space (Cube): 10^3 = 1000 bins
  ├─┼─┼─┼─┼─┼─┼─┼─┼─┤              ┌───┬───┬───┐                         ┌───┬───┐
                                   ├───┼───┼───┤                         │   │   │ /
                                   └───┴───┴───┘                         └───┴───┘

For $d = 100$ dimensions, dividing each feature axis into 10 regions requires $10^{100}$ grid cells to maintain sample coverage density!

Because datasets have at most millions of rows, high-dimensional spaces are almost entirely empty vacuum.

The 3 Geometric Illusions of High Dimensions

1. Distance Concentration (Equidistance)

Beyer et al. (1999) proved that in high dimensions, the distance between any two randomly chosen points converges to nearly the same value:

$$\lim_{d \to \infty} \frac{\text{dist}{\max} - \text{dist}{\min}}{\text{dist}_{\min}} = 0$$

If every data point is equally far away from every other point:

• k-Nearest Neighbors (k-NN) fails because "nearest" is no closer than "random".
• k-Means Clustering fails because distance metrics lose discriminative power.

2. Hypersphere Crust Concentration

The volume of a $d$-dimensional sphere of radius $r$ is $V(r) \propto r^d$.

Consider an outer shell between radius $0.99$ and $1.00$:

$$\text{Volume Ratio} = 1 - (0.99)^d$$

• For $d = 2$: Shell contains $2%$ of volume.
• For $d = 500$: Shell contains $99.3%$ of volume!

Almost all data mass concentrates in a razor-thin outer crust near the boundary.

3. Orthogonality of Random Vectors

Two random vectors drawn independently in high-dimensional space are almost guaranteed to be 90 degrees orthogonal ($\cos(\theta) \approx 0$).

Solutions to the Curse

1. Dimensionality Reduction: Project data onto low-dimensional manifolds ($k \ll d$) using PCA, t-SNE, UMAP, or Autoencoders.
2. Cosine Similarity over Euclidean: Cosine similarity handles high-dimensional directional alignment better than $L_2$ Euclidean distance.
3. L1 Regularization (Lasso): Forces sparse feature selection, dropping uninformative noise dimensions.

Say this out loud

The Curse of Dimensionality describes how high-dimensional space becomes exponentially sparse. Euclidean distances concentrate so that all points become nearly equidistant, breaking algorithms like k-NN and k-means. Volume concentrates entirely in the outer crust of hyperspheres. We solve the curse using PCA, UMAP, or autoencoders to project data onto lower-dimensional manifolds.

Follow-ups to expect

• What is the Manifold Hypothesis? The assumption that real-world high-dimensional data (like 1024x1024 images) lies on or near a lower-dimensional smooth manifold embedded within high-dimensional space.
• Why do Deep Neural Networks survive the Curse of Dimensionality? Deep networks automatically learn hierarchical feature representations, uncovering low-dimensional manifold structures directly from raw high-dimensional inputs.