5 ms·

Why are high-dimensional spheres "Spikey"?

RiderOfGiraffes 16y ago
This is in response to the comment here: http://news.ycombinator.com/item?id=1834508 http://news.ycombinator.com/item?id=1834508 My next item will be on the 1800 dimensional space problem I mention.
almost 16y ago
My brain feels kinda stretched from trying to visualize all that. Thanks :)
- RiderOfGiraffes 16y ago
  You're welcome. If it gets a couple more up-votes then it might make it to the front page for more people to get their brains stretched. I do also need to modify the page to point out that hyper-cubes are also spikey, and the hyper-spheres in the corners are sort of in the spikes. Thanks to cperciva for the added insight.
billswift 16y ago
>It's these contradictory intuitions that are simultaneously difficult and useful. You just need to pick the right one at the right time. I have heard it put that you actually need to learn to ignore your intuitions and follow the actual calculations to do higher-level math. Rather like Eliezer's "shut up and multiply" on Less Wrong. I have no personal opinion on that since I haven't learned any higher math, past first year calculus and discrete math, yet.
- ced 16y ago
  Many great mathematicians would disagree with that. I like this definition from a prof at Stanford: A proof is a nothing more than a clear, compelling argument. If it feels wrong, no matter how rigorous the math is, you still shouldn't blindly believe it. It's an opportunity to delve deeper, and either find a flaw in the proof (or your understanding thereof), or to educate your intuition.
  - pjscott 16y ago
    Exactly: intuitions can be changed, and if they're leading you astray then they should be. It's very important to have a solid set of intuitions, especially in fields like higher math that aren't easily intuitive.
- jerf 16y ago
  As a rationalist might point out, you can not go into a problem unbiased. You must make some hypotheses before you can test them; your initial hypothesis space can not be the space of all possible hypotheses or you can not get anywhere. "Shut up and calculate" works for the final part of the problem, but you need your "intuition" to get to the part where you know what to shut up and calculate about.
- jleader 16y ago
  I once heard Richard Feynman give a talk where he mentioned that in grad school he would challenge the pure mathematicians to give him their hardest, most abstract problems, and he'd often solve them by thinking up a physical analogy about which he could reason intuitively. So in his case it wasn't a matter of ignoring his intuitions, but finding the right intuition, that actually corresponded correctly with the math.
  - dwwoelfel 16y ago
    Are you sure you're remembering this right? In "The Pleasure of Finding Things Out" there is a story he tells about an ongoing challenge he had with the mathematicians. They would come to him with a theorem about topology, and he would tell them if it was true or false. That is much different from solving the theorems.
    - jleader 16y ago
      I assume you're right; my memory of a talk I heard almost 30 years ago is unlikely to be completely correct.
srean 16y ago
Related to this is the amusing phenomenon of concentration of measure. Take a ball of dimension d and distribute points uniformly at random by area. Take any patch with an area that is half of the total. A hemisphere is a valid choice. Consider its boundary. If you chose the northern(southern) hemisphere, this would be the equator. Strangely enough almost all points will lie within a distance of O(1/sqrt(d)) from that equator. As d grows this defines an incredibly thin band, but it contains almost all the points. What it means in terms of programming is that if you are searching for K points (chosen uniformly by someone else), you may as well just search over that thin band and you will find almost all of them there. That ratio can easily be in the high 90s. To give an intuition to why this happen, note that earth's equator is modestly larger than say a 60^degree north latitude. But as you crank up the dimension d this gap grows exponentially fast. So in comparison to equatorial circles, the other latitudes have almost no space at all, even when almost all of the smaller ones are taken together.
hfinney 16y ago
Let me offer a couple of other ways to view this. The most important point is that higher dimensional space is very roomy. There are many degrees of freedom, many directions. Take the first puzzle, the inner sphere that is bigger than the outer ones. One factor is that the 2 by 2 by ... by 2 packing isn't very efficient. It's not even the densest packing in 2 dimensions, less so in 3, and it gets dramatically less so as you go up. With 10 dimensions it is really inefficient so there is a lot of space in the middle. As far as the "cap" not having much volume: this wasn't explained very clearly, what he meant. Picture a circle with radius=1 centered at the origin, and then look at the piece cut off by y > 1/2 (hope that prints ok, I mean y greater than 0.5). That piece has a certain fraction of the total area. Now picture a sphere at the origin, radius 1, and the cap cut off by y > 1/2. That cap will have a smaller fraction of the total volume. Going to higher dimensions, the fraction gets smaller and smaller. But rather than meaning the sphere is "spiky", this is a result of more degrees of freedom. There are many more caps in many more directions on a high dimensional sphere. So each cap has to have less of the volume. Spikiness is really an absurd way to think of it. With practice, I've developed some ability to visualize four dimensional space. Its overwhelming character, as I said, is that it is infinitely and somewhat frighteningly roomy. This would be even more so in higher dimensions.
- srean 16y ago
  +1 We find similar things intriguing http://news.ycombinator.com/item?id=1848275 http://news.ycombinator.com/item?id=1848275 :) Though this might seem esoteric, this phenomena has practical applications. In the vector space model of information retrieval, documents are modeled as points on a high-d sphere, where d is the size of the vocabulary. So unless one accounts for these effects, there will be fascinating surprises.
- RiderOfGiraffes 16y ago
  I hear what you say, and what you say is true. Having said that, for me, I don't think your observations really help to develop an intuition that helps when working in a higher dimensional space. My experience is that people know it's roomy, but don't appreciate the consequences. The early comment about there being 10^5400 "places to be" if you have 1000 in each direction for a 1800 dimensional space immediately conveys the idea that space is big, but it's the implications that tend to go missing. People still think of spheres are round, and that "smooth" means "like a landscape in 3D." So while your comments are true, and add usefully to the discussion, to me they don't really convey a helpful visualization.
jleader 16y ago
Someone once recommended "Infinite Dimensional Analysis: A Hitchhiker's Guide" by Aliprantis and Border, with the claim that "solving problems in high dimensions can be approximated by assuming infinite dimensions". I haven't yet summoned up the mathematical guts to dig into it myself.
- srean 16y ago
  Infinite dimensional analysis is essentially functional analysis. A crude analogy is that a function is an infinite dimensional vector [...f(0),f(0+epsilon),...] so on. Although extremely interesting in its own right, this approach however will not give you a handle on how the behavior changes as the dimensionality grows.
pontifier 16y ago
makes sense... on an 1800 dimension sphere as you move away from any orthogonal direction the other 1799 dimensions can only share what you lose in the original direction so they all add up to 1... well.. you know... pythagoras and all that.
pnp 16y ago
I recall a related fact from simple statistical mechanics: the volume of high-dimensional sphere is concentrated almost exclusively near its surface. This fact allowed some nasty calculation of volume in state space to be approximated by the area of the hypersphere. IIRC, the basic notion is that volume is like r^n and area like n * r^(n-1). Quite different when n = 2, 3, ... and not so much at n = 10^23. I never thought of them as spikey but I get the picture now.
hfinney 16y ago
Greg Egan's novel Diaspora has some mind-bending scenes set in 5 dimensional space. Imagine orbiting a 5 dimensional planet and trying to scan the entire surface. The surface itself is 4 dimensional. Lots of area to search.

This is in response to the comment here: http://news.ycombinator.com/item?id=1834508 http://news.ycombinator.com/item?id=1834508 My next item will be on the 1800 dimensional space problem I mention.

almost 16y ago

My brain feels kinda stretched from trying to visualize all that. Thanks :)

RiderOfGiraffes 16y ago
You're welcome. If it gets a couple more up-votes then it might make it to the front page for more people to get their brains stretched. I do also need to modify the page to point out that hyper-cubes are also spikey, and the hyper-spheres in the corners are sort of in the spikes. Thanks to cperciva for the added insight.

billswift 16y ago

>It's these contradictory intuitions that are simultaneously difficult and useful. You just need to pick the right one at the right time. I have heard it put that you actually need to learn to ignore your intuitions and follow the actual calculations to do higher-level math. Rather like Eliezer's "shut up and multiply" on Less Wrong. I have no personal opinion on that since I haven't learned any higher math, past first year calculus and discrete math, yet.

ced 16y ago
Many great mathematicians would disagree with that. I like this definition from a prof at Stanford: A proof is a nothing more than a clear, compelling argument. If it feels wrong, no matter how rigorous the math is, you still shouldn't blindly believe it. It's an opportunity to delve deeper, and either find a flaw in the proof (or your understanding thereof), or to educate your intuition.
- pjscott 16y ago
  Exactly: intuitions can be changed, and if they're leading you astray then they should be. It's very important to have a solid set of intuitions, especially in fields like higher math that aren't easily intuitive.
jerf 16y ago
As a rationalist might point out, you can not go into a problem unbiased. You must make some hypotheses before you can test them; your initial hypothesis space can not be the space of all possible hypotheses or you can not get anywhere. "Shut up and calculate" works for the final part of the problem, but you need your "intuition" to get to the part where you know what to shut up and calculate about.
jleader 16y ago
I once heard Richard Feynman give a talk where he mentioned that in grad school he would challenge the pure mathematicians to give him their hardest, most abstract problems, and he'd often solve them by thinking up a physical analogy about which he could reason intuitively. So in his case it wasn't a matter of ignoring his intuitions, but finding the right intuition, that actually corresponded correctly with the math.
- dwwoelfel 16y ago
  Are you sure you're remembering this right? In "The Pleasure of Finding Things Out" there is a story he tells about an ongoing challenge he had with the mathematicians. They would come to him with a theorem about topology, and he would tell them if it was true or false. That is much different from solving the theorems.
  - jleader 16y ago
    I assume you're right; my memory of a talk I heard almost 30 years ago is unlikely to be completely correct.

srean 16y ago

Related to this is the amusing phenomenon of concentration of measure. Take a ball of dimension d and distribute points uniformly at random by area. Take any patch with an area that is half of the total. A hemisphere is a valid choice. Consider its boundary. If you chose the northern(southern) hemisphere, this would be the equator. Strangely enough almost all points will lie within a distance of O(1/sqrt(d)) from that equator. As d grows this defines an incredibly thin band, but it contains almost all the points. What it means in terms of programming is that if you are searching for K points (chosen uniformly by someone else), you may as well just search over that thin band and you will find almost all of them there. That ratio can easily be in the high 90s. To give an intuition to why this happen, note that earth's equator is modestly larger than say a 60^degree north latitude. But as you crank up the dimension d this gap grows exponentially fast. So in comparison to equatorial circles, the other latitudes have almost no space at all, even when almost all of the smaller ones are taken together.

hfinney 16y ago

Let me offer a couple of other ways to view this. The most important point is that higher dimensional space is very roomy. There are many degrees of freedom, many directions. Take the first puzzle, the inner sphere that is bigger than the outer ones. One factor is that the 2 by 2 by ... by 2 packing isn't very efficient. It's not even the densest packing in 2 dimensions, less so in 3, and it gets dramatically less so as you go up. With 10 dimensions it is really inefficient so there is a lot of space in the middle. As far as the "cap" not having much volume: this wasn't explained very clearly, what he meant. Picture a circle with radius=1 centered at the origin, and then look at the piece cut off by y > 1/2 (hope that prints ok, I mean y greater than 0.5). That piece has a certain fraction of the total area. Now picture a sphere at the origin, radius 1, and the cap cut off by y > 1/2. That cap will have a smaller fraction of the total volume. Going to higher dimensions, the fraction gets smaller and smaller. But rather than meaning the sphere is "spiky", this is a result of more degrees of freedom. There are many more caps in many more directions on a high dimensional sphere. So each cap has to have less of the volume. Spikiness is really an absurd way to think of it. With practice, I've developed some ability to visualize four dimensional space. Its overwhelming character, as I said, is that it is infinitely and somewhat frighteningly roomy. This would be even more so in higher dimensions.

srean 16y ago
+1 We find similar things intriguing http://news.ycombinator.com/item?id=1848275 http://news.ycombinator.com/item?id=1848275 :) Though this might seem esoteric, this phenomena has practical applications. In the vector space model of information retrieval, documents are modeled as points on a high-d sphere, where d is the size of the vocabulary. So unless one accounts for these effects, there will be fascinating surprises.
RiderOfGiraffes 16y ago
I hear what you say, and what you say is true. Having said that, for me, I don't think your observations really help to develop an intuition that helps when working in a higher dimensional space. My experience is that people know it's roomy, but don't appreciate the consequences. The early comment about there being 10^5400 "places to be" if you have 1000 in each direction for a 1800 dimensional space immediately conveys the idea that space is big, but it's the implications that tend to go missing. People still think of spheres are round, and that "smooth" means "like a landscape in 3D." So while your comments are true, and add usefully to the discussion, to me they don't really convey a helpful visualization.

jleader 16y ago

Someone once recommended "Infinite Dimensional Analysis: A Hitchhiker's Guide" by Aliprantis and Border, with the claim that "solving problems in high dimensions can be approximated by assuming infinite dimensions". I haven't yet summoned up the mathematical guts to dig into it myself.

srean 16y ago
Infinite dimensional analysis is essentially functional analysis. A crude analogy is that a function is an infinite dimensional vector [...f(0),f(0+epsilon),...] so on. Although extremely interesting in its own right, this approach however will not give you a handle on how the behavior changes as the dimensionality grows.

pontifier 16y ago

makes sense... on an 1800 dimension sphere as you move away from any orthogonal direction the other 1799 dimensions can only share what you lose in the original direction so they all add up to 1... well.. you know... pythagoras and all that.

pnp 16y ago

I recall a related fact from simple statistical mechanics: the volume of high-dimensional sphere is concentrated almost exclusively near its surface. This fact allowed some nasty calculation of volume in state space to be approximated by the area of the hypersphere. IIRC, the basic notion is that volume is like r^n and area like n * r^(n-1). Quite different when n = 2, 3, ... and not so much at n = 10^23. I never thought of them as spikey but I get the picture now.

hfinney 16y ago

Greg Egan's novel Diaspora has some mind-bending scenes set in 5 dimensional space. Imagine orbiting a 5 dimensional planet and trying to scan the entire surface. The surface itself is 4 dimensional. Lots of area to search.