Curse of Dimensionality
As dimensions grow, data grows sparse and distances lose meaning, undermining distance-based methods and demanding more data.
Why high dimensions bite
The curse of dimensionality is a cluster of counterintuitive effects that appear as the number of features grows. Volume expands so fast that any realistic dataset becomes sparse: points sit far apart, and the data you have covers a vanishing fraction of the space. Intuitions built in two or three dimensions stop holding.
Distances stop discriminating
In high dimensions, the distance from a point to its nearest neighbor and to its farthest neighbor become nearly equal. Since 'nearest' loses meaning, methods that rely on distances degrade: k-NN, k-means, and RBF kernels all suffer. Contrast fades and everything looks equidistant.
- Sparsity: the data needed to cover the space grows exponentially with dimensions.
- Distance concentration: near and far distances converge, weakening similarity.
- Overfitting risk: many features versus few samples lets models fit noise.
- Compute and storage grow with dimension.
How to fight it
- Dimensionality reduction: PCA, UMAP to compress to informative dimensions.
- Feature selection: keep only features that carry signal.
- Regularization: constrain the model so it cannot exploit the extra freedom.
- Domain features: replace many raw signals with a few meaningful quantities.
A useful counterpoint
High-dimensional data often lies near a much lower-dimensional manifold, so its intrinsic dimension is smaller than its feature count. This is why PCA, UMAP, and manifold methods work, and why deep networks succeed on images and text despite enormous nominal dimensionality. The curse is real, but structure in the data is the escape from it.