1 · The curse of dimensionality
Why high-dimensional spaces break distance-based models — and how feature selection vs extraction fight back.
As dimensionality grows, distances concentrate, neighbourhoods empty out, and 'similar' loses meaning — dimensionality reduction fights back.
Without this:
Without grasping the curse, you'd dump every feature into every model and wonder why KNN, distance-based clustering, and density estimation silently fail.
Dimensionality refers to the number of input features in your dataset. A house might be described by 5 features (area, rooms, floors, age, zip code). A genome might use 500,000 SNP markers. A raw 64×64 image has 4,096 pixel dimensions. As d grows, something deeply counterintuitive happens: the geometry of space breaks down.
The curse of dimensionality is a family of related phenomena that make statistical estimation hard in high dimensions:
-
Volume concentrates at the edges — In a d-dimensional unit cube, the fraction of volume that lies within a distance ε of any face grows to 1 as d → ∞. Most of the mass of a high-dimensional cube lives in its corners, not its interior.
-
Distances concentrate — In high dimensions, the ratio of the maximum to minimum pairwise distance between random points converges to 1. Every point is roughly the same distance from every other point — "nearest neighbour" becomes meaningless.
-
Data density collapses — To maintain the same sample density as you had in d dimensions, you need exponentially more points. Going from 2D to 20D requires roughly 10¹⁸ times more data for equivalent coverage.
Two strategies to fight the curse:
| Strategy | Idea | Examples | |---|---|---| | Feature selection | Keep a subset of original features | SelectKBest, Lasso (L1), mutual information | | Feature extraction | Build new compressed features | PCA, t-SNE, autoencoders |
Selection keeps interpretability (you can name the chosen features). Extraction sacrifices interpretability for compression power — it combines information across all features, potentially capturing structure selection misses.
Python (in browser)
Pairwise distance histograms across dimensionalities — by d=1000 the spread has all but vanished.
Python runs entirely in your browser via Pyodide (~6 MB on first Run, cached after).
Python (in browser)
The unit ball collapses to near-zero volume relative to the unit cube.
Python runs entirely in your browser via Pyodide (~6 MB on first Run, cached after).
Python (in browser)
Selection vs extraction — PCA usually wins slightly because it captures shared variance across all features.
Python runs entirely in your browser via Pyodide (~6 MB on first Run, cached after).
Decision guide: when to select vs extract features.
In a 100-dimensional unit cube, where do most randomly sampled points live?
- As d grows, pairwise distances concentrate around a single value — nearest-neighbour and density-based algorithms silently degrade.
- The volume of a unit ball relative to a unit cube collapses to zero by d≈20 — high-dimensional spherical neighbourhoods capture almost no data.
- Feature selection keeps interpretable original features; feature extraction (PCA, autoencoders) builds new compressed axes — both reduce the effective dimensionality.
- PCA typically outperforms SelectKBest slightly on correlated data because it captures shared variance rather than ranking individual features.
- Always reduce dimensionality before applying KNN, RBF SVM, or GMM to datasets with d > 50.
Image classification (raw pixels are high-D), genomics (millions of SNPs per patient), NLP (word embeddings as a compression of vocabulary size 50k+ to 300-D). All start with some form of dimensionality reduction.
If you remove it: You'd train models in the original feature space and pay the curse on every prediction — poor generalisation, slow inference, and misleadingly small training errors.