Comment by tel | Hacker News Reader

Comment by tel | Hacker News Reader

Parent Full thread

One should also take a close look at the formulas for volumes of unit-radius n-balls. For even numbers of dimensions it's

    pi^(n/2)/fact(n/2)

which behaves very interestingly[1]. It's equal to pi in two dimensions, peaks at the 4-dimensional ball (about 1.6 pi), then is driven to effectively zero by the time you get to 20 dimensions or so (value of ~8/1000 pi).

Again, however, the radius isn't changing. I don't think of unit balls as being spiky--they're still rotationally invariant in all d rotational degrees of freedom, so calling them spiky doesn't sit well with me.

Instead, imagine you lived on a line, only walking up and back along it forever. Then, one day, someone introduced you to the plane and then a volume. These are vastly larger than the space you were afforded by the line: exponential blowup.

It's also driven home by how the Lesbegue measure in d-dimensions assigns zero measure to all (d-1)-dimensional (or lesser) objects. Adding a dimension just makes space immensely larger.

And so pegging the size of our unit ball to its 1-dimensional parameter, the radius, causes its volume to vanish.

[1] Wolfram Alpha chart showing the volume of the n-sphere in units of pi http://www.wolframalpha.com/input/?i=pi%5E%28n%2F2-1%29%2FGa...

As a practical application of this, consider 1-d optimization using some kind of stochastic, "jumping" process. So long as the global minimum is in a kind of larger well then the information concerning it's location is "global" enough for the jumping process to work its way down there.

If the well the global minimum lives in is sufficiently small—if it is a sufficiently local event—then your stochastic search is bound to fail. At the limit, you have a discontinuity, a global minimum which literally has no global presence and is essentially impossible to find (you can show expected convergence times going to infinity as the minimum looks more and more discontinuous).

Fortunately, few processes are genuinely discontinuous and they usually have some kind of non-local "well of attraction". But in higher and higher dimensions, these wells can be made to appear nearly infinitely narrow.

All together this enforces the principle of the curse of dimensionality. High dimensionality hurts you in statistics and search unless every dimension is just chock full of signal.

Aha, right.. That helps me understand the link to optimisation. So the point of spheres getting "spiky" is that if you are searching for the inside of the sphere then you need to go into the spike which gets harder and harder to find as the dimension increases.

I think of it as the difference between playing air hockey (with no opponent) and darts. One of them is just a lot easier than the other.

You guys should swap nicks.

> which behaves very interestingly

Check out Bill Thurston's comment on why this is deeply misleading geometrically:

http://mathoverflow.net/questions/53119/volumes-of-n-balls-w...

As several commenters there point out, if you must choose a ratio, a more geometrically natural choice would be the ratio of the unit sphere to its circumscribed cube (which decreases monotonically) or to its inscribed cube (which increases monotonically).

As a demonstration of the non-intuitiveness of measures in high dimensions, I think this is still a decent example, no? I agree that n=5 [sic on my part above] isn't special, but seeing the Gamma function should be cause enough for worrying your intuition. It might be misleading, but I'd hope that it wouldn't beg the question of what's special about n=5, but instead what's wrong with your views about high dimensional space.

I agree with the comments on MathOverflow though.

http://begthequestion.info

> And so pegging the size of our unit ball to its 1-dimensional parameter, the radius, causes its volume to vanish.

There's some inherent flaw here - as 'pegging' the size of unit cube to its 1-dimensional parameter, the length, does not make the volume to vanish.

> It's also driven home by how the Lesbegue measure in d-dimensions assigns zero measure to all (d-1)-dimensional (or lesser) objects. Adding a dimension just makes space immensely larger.

> And so pegging the size of our unit ball to its 1-dimensional parameter, the radius, causes its volume to vanish.

Funny. I was just going to enter a comment how that was the most useful intuition in the whole thread.

But the cube isn't pegged like that at all. The cube is the set of points where any element of the coordinate vector has a magnitude less than a specified value, whereas the sphere is the set of points where the magnitude of the vector is less than a specified value. Hence the cube gets 'larger' as you make space itself larger by adding dimensions, but the sphere doesn't.

Definitely the best comment. By looking at it this way, the mystery almost vanishes!

They're totally different objects. Unit balls encode distance by being the set of points within some distance from the center. They are thus, loosely, parameterized by a 1-dimensional measure.

Unit cubes are constrained such that all of their measurements are unit length---something which ensures that their volume is constantly 1. They do this by getting spiky, as xyzzyx mentioned. The distance to cross them shrinks as the vertex distance grows.

So they start to look totally different in high dimensions, evidenced by the ball's vanishing measure.

As one last point about how the problem is caused by just how big high dimensional spaces are, remember that the n-dimensional unit sphere contains every d-dimensional unit sphere for d <= n.

The spheres are a strictly increasing sequence of sets, but the measures we call "volume" are growing even faster.

Reply on news.ycombinator.com