next up previous
Next: Bayes' Decision Theory [5+2* Up: MLA_Exercises_2007 Previous: Conditional Independence [2 P]

Curse of Dimensionality [2* P]

Consider a sphere of radius $ a$ in $ D$-dimensions together with a concentric hypercube of side $ 2a$, so that the sphere touches the hypercube at the centres of each of its sides. Show that

$\displaystyle \lim _{D \rightarrow \infty} \frac{\text{Volume of sphere}}{\text{Volume of cube}} \rightarrow 0.$    

Make use of Stirling's formula

$\displaystyle \Gamma(x+1) \simeq(2\pi)^{1/2}\exp^{-x}x^{x+1/2},$    

which is valid for $ x \gg 1$. Show also that the ratio of the distance from the centre of the hypercube to one of the corners, divided by the distance to one of the sides centers goes to $ \infty$ as $ D \rightarrow \infty$. From this results we see that, in a space of high dimensionality, most of the volume of a cube is concentrated in the large number of corners, which themselves become very long 'spikes'!

Haeusler Stefan 2007-12-03