Hacker News Reader

Comment by RiderOfGiraffes | Hacker News Reader

Lenstra-Lenstra-Lovasz:

http://en.wikipedia.org/wiki/Lenstra%E2%80%93Lenstra%E2%80%9...

High dimensional work is bloody hard, and this algorithm works amazingly well. I've spoken with Lenstra (one of them) and he's amazingly insightful on these things. He helped to crystalise my understanding of why high-dimensional spheres should be thought of as "spikey," rather than "round."

View on HN

Why are high dimensional spheres spikey?

Ah. I really should write that up. Far too long to explain in a comment here, far to interesting (to me!) to forget or ignore.

I'll write it up and submit it. Anyone who cares to email me can get an early version to read, and your feedback would be useful.

Please.

Thanks.

Please do. My guess would be similar to Zaak's: the n-dimensional volume of an n-dimensional hypersphere approaches 0 as n approaches infinity. (http://www.mathreference.com/ca-int,hsp.html). A hypersphere with radius 1 centered at the origin has to get out to 1 along each axis (e.g. x=1, y=z=0 for a 3 dimensional sphere), and in order for that not to contribute much volume, it has to be a narrow spike rather than a gradual curve.

I believe it's because in high dimensions, most of the "volume" is near the center, whereas in low dimensions, most of the volume is near the surface.

Not at all. The expected distance between the center of an n-ball and a random point in the ball is n/(n+1) times the radius.

Now, if you look at an n-sphere with respect to orthogonal axes, you find that moving along an axis you get out as far as (1, 0, ... 0) and moving "away" from the axes you only get to (1/sqrt(n), 1/sqrt(n), ... 1/sqrt(n)); but this isn't due to the sphere being spiky -- rather, it's because orthogonal axes are spiky.

Now written up here:

http://news.ycombinator.com/item?id=1846682

In response to requests, the write-up is now available here:

http://news.ycombinator.com/item?id=1846682

Reply on news.ycombinator.com