Curse of dimensionality

From Wikipedia, the free encyclopedia

The curse of dimensionality is a term coined by Richard Bellman to describe the problem caused by the exponential increase in volume associated with adding extra dimensions to a (mathematical) space.

For example, 100 evenly-spaced sample points suffice to sample a unit interval with no more than 0.01 distance between points; an equivalent sampling of a 10-dimensional unit hypercube with a lattice with a spacing of 0.01 between adjacent points would require 10²⁰ sample points: thus, in some sense, the 10-dimensional hypercube can be said to be a factor of 10¹⁸ "larger" than the unit interval. (Adapted from an example by R. E. Bellman, see below.)

Another way to envisage the "vastness" of high-dimensional Euclidean space is to compare the size of the unit sphere with the unit cube as the dimension of the space increases: as the dimension increases, the unit sphere becomes an insignificant volume relative to that of the unit cube; thus, in some sense, nearly all of the high-dimensional space is "far away" from the centre, or, to put it another way, the high-dimensional unit space can be said to consist almost entirely of the "corners" of the hypercube, with almost no "middle". (This is an important intution for understanding the chi-squared distribution.)

[edit] The curse of dimensionality in machine learning

The curse of dimensionality is a significant obstacle in machine learning problems that involve learning from few data samples in a high-dimensional feature space.