1Model Evaluation & Metrics 2Train, Validation & Test Sets 3Cross-Validation 4Bias-Variance Tradeoff 5Learning Curves 6Class Imbalance & Resampling 7Feature Selection 8Curse of Dimensionality

Lensa ML

Curse of Dimensionality

Step 1 of 6: Volume Explosion

Hypercube surprise

Dimensions (d)2

Dimensions

Ball / cube

78.54%

Ball volume

3.142

In low dimensions, the inscribed ball fills a large share of the cube, and little volume sits in the corners.

Drag the dimension slider from 1 to 20 and watch the ball's share of its cube shrink. The unit ball's volume is π^(d/2) / Γ(d/2 + 1), while the cube with side 2 has volume 2^d, so their ratio falls faster than exponentially. At d = 10 the ball holds 0.25% of the cube, and at d = 20 about 0.0000025%. The same geometry makes high-dimensional Gaussians behave strangely: almost no samples land near the mean, and most sit in a thin shell at a distance of about √d from it.

Step 2 of 6: Distance Concentration

Everything is far away

Dimensions (d)2

Dimensions

Min dist

0.02

Max dist

1.09

Max / min

59.36

Distances are spread out: near and far points are easy to tell apart.

Drag the dimensions from 2 to 100 and watch the MAX / MIN card. For these 30 random points it falls from about 59 at d = 2 to 3 at d = 10 and 1.4 at d = 100. For points uniform in the unit cube, the typical distance grows like √(d/6), but its spread stays roughly constant, so the relative difference between near and far shrinks toward zero. Beyer et al. proved in 1999 that, under broad conditions, the ratio of farthest to nearest neighbor distance tends to 1 as d grows.

Step 3 of 6: Data Sparsity

You need exponentially more data

Dimensions (d)1

Dimensions

Data needed

Available

1,000

Density

100.00

With 1000 points there is at least one point per cell on average, so the space is covered.

Drag the dimensions from 1 to 10. Each axis is split into 10 bins, so covering the space at that resolution takes 10^d cells and at least that many points. With 1,000 points the cells are filled up to d = 3, and at d = 10 more than 99.9999% of them are empty. Real data escapes the worst of this because it is not uniform. Images, text, and sensor readings lie near a much lower-dimensional surface, the manifold hypothesis, which is why models can learn 784-pixel digits from 60,000 examples.

Step 4 of 6: k-NN in High Dimensions

Neighborhoods grow huge

Dimensions (d)2

Dimensions

Edge (k=5)

0.224

Share of each axis

22.4%

A small neighborhood holds 5 points, so k-NN's neighbors really are local.

Drag the dimensions from 2 to 30. The Edge card is the edge length of a sub-cube that holds 5 of 100 uniform points, e = (5/100)^(1/d). The neighborhood always holds 5% of the volume at every d, the same share of the data, but its edge must stretch from 0.22 of each axis at d = 2 to 0.74 at d = 10 and 0.91 at d = 30. Neighbors that far away no longer resemble the query, so k-NN's prediction drifts toward the global average.

Step 5 of 6: Irrelevant Features

Noise drowns out signal

Irrelevant features0

Relevant

Irrelevant

Total

Accuracy

98%

With only the two relevant features, the classes separate cleanly.

Drag the irrelevant features slider from 0 to 20. Two features carry the class signal, and every added one is pure noise. In Euclidean distance, each noise feature adds about the same amount to every pairwise distance, so after a handful of them the two informative coordinates make up a small share of the total. Distance-based models such as k-NN, k-means, and RBF-kernel SVMs suffer most. Tree ensembles and L1-regularized linear models cope better, because they can learn to ignore a feature entirely.

Step 6 of 6: Mitigation Strategies

Reducing dimensions

Target dimensions (after reduction)20

Original d

Target d

Acc before

60%

Acc after

60%

Still too many dimensions: most of them add noise without useful information.

Drag the target dimensions from 20 down to 2. Accuracy peaks in the shaded range and drops on both sides: too many dimensions keep noise, too few discard signal. The label names three families of fixes. PCA keeps the directions of largest variance, feature selection keeps a subset of the original columns, and autoencoders learn a nonlinear compression. The target dimension is usually chosen by cross-validating the whole pipeline, with the reduction fit inside each fold so the validation rows stay unseen.

What is the curse of dimensionality?

The curse of dimensionality is the set of problems that appear when data has many features: the volume of the space grows exponentially with the number of dimensions, so a fixed number of samples becomes sparse, and distances between points become nearly equal. The term was coined by Richard Bellman in the context of dynamic programming.

It matters wherever a model relies on distance or local density. k-nearest neighbors, k-means clustering, kernel methods, and anomaly detectors all degrade when many features carry little signal. Gene-expression studies with 20,000 genes and a few hundred patients, recommendation data with millions of sparse columns, and raw image pixels all face it. The standard responses are feature selection, dimensionality reduction such as PCA, regularization, and collecting more data.

Key ideas

Volume grows exponentially with dimension, so a fixed sample becomes sparse.
In high dimensions, almost all of a cube's volume lies in its corners.
Pairwise distances concentrate, so the nearest and farthest neighbors are nearly the same distance away.
k-NN neighborhoods must span most of each axis to hold even a few points.
Irrelevant features dilute distances and hurt distance-based models most.
Feature selection, dimensionality reduction, and regularization are the main remedies.

Common questions

Does the curse of dimensionality affect deep learning?

Less than the raw input size suggests. Neural networks learn their own low-dimensional representations, and natural data such as images lies near a low-dimensional manifold, so a 150,000-pixel image does not need 10^150,000 samples. The curse still shows up in nearest-neighbor search over embeddings, which is one reason vector databases use approximate methods and cosine similarity.

How many samples do I need per feature?

There is no universal rule. For linear models, a common heuristic is at least 10 to 20 samples per feature, while nonparametric methods like k-NN need far more because their data needs grow exponentially with dimension. Regularization and feature selection lower the requirement, and cross-validation shows whether a given dataset is enough.

Is there a blessing of dimensionality?

Yes. In more dimensions, classes are more often linearly separable, which is the idea behind kernel methods. Concentration of measure also makes random projections reliable: the Johnson-Lindenstrauss lemma says points can be projected to about log(n)/ε² dimensions while preserving pairwise distances within a factor of 1 ± ε.

Does using cosine similarity instead of Euclidean distance fix the problem?

Not fully. Cosine similarity removes the effect of vector length, which helps for text and embeddings, but similarities between random high-dimensional vectors still cluster tightly around zero. Aggarwal et al. found that metrics with smaller exponents, such as Manhattan distance, keep more contrast than Euclidean distance as dimension grows.

Related explainers

K-Nearest Neighbors — Classification by proximity and distance metrics
Dimensionality Reduction — PCA and t-SNE — seeing high-dimensional data
Feature Selection — Filter, wrapper, and embedded methods for choosing features
Norms & Distance Metrics — L1, L2, cosine similarity — measuring closeness in vector spaces
Regularization — Dropout, L1, and L2 — keeping models honest
K-Means Clustering — Unsupervised grouping by centroid distance

References

Last updated October 25, 2026