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 intuition for understanding the chi-squared distribution.)

[edit] The curse of dimensionality in optimization and learning

The curse of dimensionality is a significant obstacle to solving dynamic optimization problems by numerical backwards induction when the dimension of the 'state variable' is large. It also complicates machine learning problems that involve learning a 'state-of-nature' (maybe infinite distribution) from a finite (low) number of data samples in a high-dimensional feature space and nearest neighbor search in high dimensional space.

[edit] See also

• Dynamic programming
• Bellman equation
• Backwards induction
• Quasi-random
• Combinatorial explosion
• Nearest neighbor search
• ε-Approximate Nearest Neighbor Search

[edit] References

• Bellman, R.E. 1957. Dynamic Programming. Princeton University Press, Princeton, NJ.
  • Republished 2003: Dover, ISBN 0486428095.
• Bellman, R.E. 1961. Adaptive Control Processes. Princeton University Press, Princeton, NJ.
• Powell, Warren B. 2007. Approximate Dynamic Programming: Solving the Curses of Dimensionality. Wiley, ISBN 0470171553.