Learn AI Create the Future — with Pranay
Main site

Dimensionality Reduction

The curse of dimensionality

As columns pile up, data points drift apart until everything is nearly the same distance from everything else — and models built on "near means similar" quietly stop working.

Read these first

On this page 5
  1. Why this matters
  2. How it works
  3. A real example you have seen
  4. Remember this
  5. What to learn next

One lesson, three depths. Pick the one that fits you today — you can switch any time.

Beginner — No maths. Plain English.

The curse of dimensionality: every column you add spreads your data thinner, until "nearby" points barely exist.

Say you dropped a coin in a corridor. Searching a corridor is quick — walk it once. Drop it in an open field instead and the search multiplies: length times width. Drop it somewhere in a ten-storey building — length times width times height — and you might never find it.

Each new direction to search multiplies the space. In data, every column is a direction. A table with 100 columns is a 100-direction space. Your few thousand rows rattle around inside it like a handful of coins lost in a universe.

Why this matters

Many models lean on one humble assumption: points that are close together are similar. Nearest-neighbour methods vote among close points. Clustering groups close points. Recommendation engines find users close to you.

The curse breaks the word "close". With few columns, some neighbours are genuinely near and others far, and the difference carries information. With hundreds of columns, a strange thing happens: everyone becomes roughly equally far from everyone else. Your nearest neighbour is barely nearer than your farthest one. A vote among "nearest" neighbours becomes a vote among strangers.

How it works

corridor (1 direction):   #####o####          neighbours are near
field    (2 directions):  points scatter      neighbours findable
building (3 directions):  scatter more        getting thin...
100 directions:           every point sits    "nearest" is almost
                          alone in its own    as far as "farthest"
                          empty corner

There is a second face of the curse: coverage. To see every combination of 2 values in each of 10 columns, you need over a thousand examples. For 20 columns, over a million. Real datasets never keep up. Most of a high-dimensional space therefore contains no data at all. Models are forced to guess about places they have never seen.

A real example you have seen

Finding a flat to rent with one filter — price — gives you plenty of choices near your ideal. Add filters: floor, facing, furnished, pet-friendly, near metro, balcony, parking. Seven filters in, zero flats match everything. Not because good flats vanished — because with enough conditions, nothing is close to your ideal point any more. Every extra column does that to your data.

Remember this

  • Each column is a new direction; space grows multiplicatively, data does not.
  • In high dimensions, distances bunch together: "nearest" stops meaning much.
  • This is why we compress columns — the whole point of this section.

What to learn next

Developer — Code and libraries.

Setup

bash
pip install numpy

Verified with NumPy 1.26.

Watching distance die

Take 500 random points. Measure the distance from the first point to all others, in more and more dimensions. Watch the gap between nearest and farthest collapse.

curse.py
import numpy as np

rng = np.random.default_rng(0)

print("dims   nearest   farthest   gap")
for d in [2, 10, 100, 1000, 10000]:
    points = rng.random((500, d))            # 500 random points in a d-dim box
    me = points[0]
    dist = np.linalg.norm(points[1:] - me, axis=1)
    near, far = dist.min(), dist.max()
    print(f"{d:5d}   {near:7.2f}   {far:8.2f}   {far/near:5.2f}x")
Output
dims   nearest   farthest   gap
    2      0.01       0.94   67.13x
   10      0.58       1.92    3.32x
  100      3.63       4.95    1.36x
 1000     12.29      13.62    1.11x
10000     40.14      41.43    1.03x

The walkthrough

Read the last column. In 2 dimensions, the farthest point is 67 times farther than the nearest — distance is dripping with information. By 100 dimensions the ratio is 1.36. By 10,000 it is 1.03: the nearest point is a rounding error nearer than the farthest. Any algorithm ranking these points by distance is now ranking noise.

Why it happens, in one sentence. Each dimension contributes an independent bit of squared distance; summing 10,000 of them averages away the luck, so all totals land near the same value — the same reason 10,000 coin flips reliably land near 50% heads.

This is random data — the worst case. Real data has structure: correlated columns, clusters, patterns. Structure means the effective number of independent directions is far below the column count, and that is precisely the escape hatch every method in this section exploits. PCA finds those few real directions.

Common mistakes

Trusting k-NN, k-means, or cosine similarity on hundreds of raw columns. They run without error and return confident nonsense, because near-equal distances still produce a ranking. If results look arbitrary, print the nearest/farthest ratio for your own data before blaming the model.

Believing more features always help. Each irrelevant column adds noise to every distance and dilutes the signal columns. Adding features has a real cost, which is why feature selection exists.

Confusing "many columns" with "cursed". 500 one-hot columns from a single categorical, or 784 pixels of digit images, have massive internal structure — their effective dimension is small. The curse bites in proportion to independent directions, not raw column count.

Extrapolating in high dimensions. With space mostly empty, most predictions are far from any training point. Check how far test points sit from training data before trusting a model's confidence there.

Try it yourself

Replace the random points with correlated data: points = rng.random((500, 1)) @ np.ones((1, d)) + rng.random((500, d)) * 0.1. All d columns, but one real direction plus noise. See how the ratios change.

What to learn next

Researcher — Mathematics and papers.

Origin and the volume argument

The phrase is Bellman's (1961, Adaptive Control Processes), coined for the exponential blow-up of grid-based dynamic programming. The geometric heart: a hypercube [0,1]^d has volume 1, while the inscribed ball's volume V_d(1/2) = (pi^{d/2} / Gamma(d/2 + 1)) * (1/2)^d tends to 0 as d grows. Almost all of a high-dimensional cube lies in its corners, far from the centre. Similarly, a shell of relative thickness epsilon holds fraction 1 - (1 - epsilon)^d of the ball's volume — nearly everything sits at the surface. Uniform high-dimensional data is all edges, no middle.

Distance concentration, precisely

Beyer, Goldstein, Ramakrishnan and Shaft (1999, When is "nearest neighbor" meaningful?, ICDT) prove: if the distance distribution satisfies Var(||X||/E||X||) -> 0 as d -> infinity — true for i.i.d. coordinates by the law of large numbers — then for any epsilon > 0, P(max dist <= (1 + epsilon) min dist) -> 1. The demo above is this theorem made visible. Aggarwal, Hinneburg and Keim (2001) sharpen the picture for L_p norms: relative contrast decays fastest for large p, making L1 preferable to L2, and fractional norms preferable still, in high-dimensional similarity search.

Sample complexity

For nonparametric estimation, minimax rates make the curse quantitative: estimating an s-smooth density or regression function in d dimensions has optimal L2 risk of order n^{-s/(2s + d)} (Stone, 1982). Halving the error at d = 20 with s = 2 requires roughly 2^{(2s+d)/(2s)} = 64 times the data. Without structural assumptions, sample requirements grow exponentially in d — the statistical, as opposed to geometric, face of the curse.

The escape: intrinsic dimension

Real data escapes because it does not fill its ambient space. The manifold hypothesis holds that natural data concentrates near a low-dimensional manifold embedded in R^d — empirically supported for images, speech and text embeddings. Estimators of intrinsic dimension (Levina and Bickel's MLE, 2004; two-NN, Facco et al., 2017) typically report single-digit to low-double-digit dimensions for data with thousands of ambient dimensions. Every method in this section is a bet on that gap: PCA bets the manifold is linear, kernel PCA and UMAP bet it is curved, random projections bet only that n points cannot fill many dimensions.

What to learn next