So, I'm toying with Shannon's capacity theorem, trying to graph out the "sphere hardening" effect that he cites as the basis of the principle. I can see, intuitively, how the whole notion that the volume of a sphere is concentrated in a thin shell works, but when I try to calculate actual numbers I start running into numerical difficulties at dimensions of around 150 or 200. Even with a 150-dimensional sphere, as the sphere radius increases, the transition in the cumulative probability function of a signal not being within the sphere vs. the signal being inside the sphere is fairly gradual. I want to make some visual aids that show the sphere hardening up as the dimensions get higher -- can anyone point me to math for calculating this that does not involve calculating the gamma function (which is what's blowing up in my face)? Thanks. (And yes, this is badly stated -- low blood sugar and a persistent cold means that right now my fingers are being directed by a large lump of trembling snot, not a cohesive collection of brain cells. Aim your "well asked question" gun at this posting and fire away -- I'll try to clarify as I go.) -- Tim Wescott Wescott Design Services http://www.wescottdesign.com I'm looking for work -- see my website!
Shannon and Sphere Hardening
Started by ●March 24, 2017
Reply by ●March 24, 20172017-03-24
On Fri, 24 Mar 2017 14:11:56 -0500, Tim Wescott <seemywebsite@myfooter.really> wrote:>So, I'm toying with Shannon's capacity theorem, trying to graph out the >"sphere hardening" effect that he cites as the basis of the principle. > >I can see, intuitively, how the whole notion that the volume of a sphere >is concentrated in a thin shell works, but when I try to calculate actual >numbers I start running into numerical difficulties at dimensions of >around 150 or 200. > >Even with a 150-dimensional sphere, as the sphere radius increases, the >transition in the cumulative probability function of a signal not being >within the sphere vs. the signal being inside the sphere is fairly >gradual. > >I want to make some visual aids that show the sphere hardening up as the >dimensions get higher -- can anyone point me to math for calculating this >that does not involve calculating the gamma function (which is what's >blowing up in my face)? > >Thanks. > >(And yes, this is badly stated -- low blood sugar and a persistent cold >means that right now my fingers are being directed by a large lump of >trembling snot, not a cohesive collection of brain cells. Aim your "well >asked question" gun at this posting and fire away -- I'll try to clarify >as I go.)What concepts are you trying to get across with this? Generally, it is possible to get a good working grasp of capacity and coding without bothering with sphere packing, although knowing that can also be useful. I'm of the opinion that just learning things like minimum distance for a simple binary code (and how that relates) can get the practical basics across more easily than delving into the theory of the limits. But, as usual, it does depend on what you're really trying to get across. --- This email has been checked for viruses by Avast antivirus software. https://www.avast.com/antivirus
Reply by ●March 24, 20172017-03-24
On Fri, 24 Mar 2017 22:49:01 +0000, eric.jacobsen wrote:> On Fri, 24 Mar 2017 14:11:56 -0500, Tim Wescott > <seemywebsite@myfooter.really> wrote: > >>So, I'm toying with Shannon's capacity theorem, trying to graph out the >>"sphere hardening" effect that he cites as the basis of the principle. >> >>I can see, intuitively, how the whole notion that the volume of a sphere >>is concentrated in a thin shell works, but when I try to calculate >>actual numbers I start running into numerical difficulties at dimensions >>of around 150 or 200. >> >>Even with a 150-dimensional sphere, as the sphere radius increases, the >>transition in the cumulative probability function of a signal not being >>within the sphere vs. the signal being inside the sphere is fairly >>gradual. >> >>I want to make some visual aids that show the sphere hardening up as the >>dimensions get higher -- can anyone point me to math for calculating >>this that does not involve calculating the gamma function (which is >>what's blowing up in my face)? >> >>Thanks. >> >>(And yes, this is badly stated -- low blood sugar and a persistent cold >>means that right now my fingers are being directed by a large lump of >>trembling snot, not a cohesive collection of brain cells. Aim your >>"well asked question" gun at this posting and fire away -- I'll try to >>clarify as I go.) > > What concepts are you trying to get across with this? Generally, it is > possible to get a good working grasp of capacity and coding without > bothering with sphere packing, although knowing that can also be useful. > I'm of the opinion that just learning things like minimum distance for > a simple binary code (and how that relates) can get the practical basics > across more easily than delving into the theory of the limits. > > But, as usual, it does depend on what you're really trying to get > across.I had a real "aha" moment when I finally absorbed the sphere-hardening idea from Shannon's paper. I'm looking for a visual way to share that with others. -- Tim Wescott Control systems, embedded software and circuit design I'm looking for work! See my website if you're interested http://www.wescottdesign.com
Reply by ●March 24, 20172017-03-24
Tim Wescott <tim@seemywebsite.com> wrote:>I had a real "aha" moment when I finally absorbed the sphere-hardening >idea from Shannon's paper. I'm looking for a visual way to share that >with others.Yeah, if there's no picture, I don't believe. it. :-) S.
Reply by ●March 24, 20172017-03-24
Tim Wescott <seemywebsite@myfooter.really> writes:> [...]Tim, Have you seen this? https://www-ee.stanford.edu/~hellman/playground/hyperspheres/hyper04.html -- Randy Yates, DSP/Embedded Firmware Developer Digital Signal Labs http://www.digitalsignallabs.com
Reply by ●March 25, 20172017-03-25
On 24.03.2017 22:11, Tim Wescott wrote:> So, I'm toying with Shannon's capacity theorem, trying to graph out the > "sphere hardening" effect that he cites as the basis of the principle. > > I can see, intuitively, how the whole notion that the volume of a sphere > is concentrated in a thin shell works, but when I try to calculate actual > numbers I start running into numerical difficulties at dimensions of > around 150 or 200. > > Even with a 150-dimensional sphere, as the sphere radius increases, the > transition in the cumulative probability function of a signal not being > within the sphere vs. the signal being inside the sphere is fairly > gradual. > > I want to make some visual aids that show the sphere hardening up as the > dimensions get higher -- can anyone point me to math for calculating this > that does not involve calculating the gamma function (which is what's > blowing up in my face)? > > Thanks. > > (And yes, this is badly stated -- low blood sugar and a persistent cold > means that right now my fingers are being directed by a large lump of > trembling snot, not a cohesive collection of brain cells. Aim your "well > asked question" gun at this posting and fire away -- I'll try to clarify > as I go.) >Tim, although I'm lazy and haven't followed the derivation you are looking at, however, I also doesn't seem to grasp your problems. With the risk of stating the obvious, here's how I would approach it. Suppose you have an N-dimensional sphere of radius r, and want to know how much of its volume is concentrated in the outer shell lying between, say, radii (1-alpha)*r and r, where alpha is small. You know that the volume of an N-dimensional sphere of radius r is given by V_N = C_N * r^N, where C_N is some function of N. But since you only need to know the fraction of the total volume occupied by the outer shell, you don't even need to know C_N, because it's canceled off (along with r): [ V_N(r) - V_N((1-alpha)*r) ] / V_N(r) = 1 - (1-alpha)^n Which could be further simplified, assuming alpha << 1, as 1 - exp(-alpha*N). I've plotted the fraction of the outer shell volume to the total sphere volume for alpha = 0.01, just to see the approximation is fair: http://i.imgur.com/nkyaPh4.png Regards, Gene
Reply by ●March 25, 20172017-03-25
On Sat, 25 Mar 2017 14:13:51 +0300, Evgeny Filatov wrote:> On 24.03.2017 22:11, Tim Wescott wrote: >> So, I'm toying with Shannon's capacity theorem, trying to graph out the >> "sphere hardening" effect that he cites as the basis of the principle. >> >> I can see, intuitively, how the whole notion that the volume of a >> sphere is concentrated in a thin shell works, but when I try to >> calculate actual numbers I start running into numerical difficulties at >> dimensions of around 150 or 200. >> >> Even with a 150-dimensional sphere, as the sphere radius increases, the >> transition in the cumulative probability function of a signal not being >> within the sphere vs. the signal being inside the sphere is fairly >> gradual. >> >> I want to make some visual aids that show the sphere hardening up as >> the dimensions get higher -- can anyone point me to math for >> calculating this that does not involve calculating the gamma function >> (which is what's blowing up in my face)? >> >> Thanks. >> >> (And yes, this is badly stated -- low blood sugar and a persistent cold >> means that right now my fingers are being directed by a large lump of >> trembling snot, not a cohesive collection of brain cells. Aim your >> "well asked question" gun at this posting and fire away -- I'll try to >> clarify as I go.) >> >> > Tim, although I'm lazy and haven't followed the derivation you are > looking at, however, I also doesn't seem to grasp your problems. With > the risk of stating the obvious, here's how I would approach it. > > Suppose you have an N-dimensional sphere of radius r, and want to know > how much of its volume is concentrated in the outer shell lying between, > say, radii (1-alpha)*r and r, where alpha is small. > > You know that the volume of an N-dimensional sphere of radius r is given > by V_N = C_N * r^N, where C_N is some function of N. But since you only > need to know the fraction of the total volume occupied by the outer > shell, you don't even need to know C_N, because it's canceled off (along > with r): > > [ V_N(r) - V_N((1-alpha)*r) ] / V_N(r) = 1 - (1-alpha)^n > > Which could be further simplified, assuming alpha << 1, as 1 - > exp(-alpha*N). > > I've plotted the fraction of the outer shell volume to the total sphere > volume for alpha = 0.01, just to see the approximation is fair: > > http://i.imgur.com/nkyaPh4.pngActually, where Shannon's argument gets lazy is in sticking with the volume argument: I'm trying to plot the cumulative probability density per radius, or at least an approximation. The "volume concentrating" property is valid, and the fact that the cumulative probability function "hardens" with increasing dimension seems to be true, but Shannon's argument about the link between the volume being concentrated on the edge and the cumulative probability function hardening is just hand-waving -- at least in his 1948 paper. -- Tim Wescott Control systems, embedded software and circuit design I'm looking for work! See my website if you're interested http://www.wescottdesign.com
Reply by ●March 25, 20172017-03-25
On Sat, 25 Mar 2017 11:12:01 -0500, Tim Wescott <tim@seemywebsite.com> wrote:>On Sat, 25 Mar 2017 14:13:51 +0300, Evgeny Filatov wrote: > >> On 24.03.2017 22:11, Tim Wescott wrote: >>> So, I'm toying with Shannon's capacity theorem, trying to graph out the >>> "sphere hardening" effect that he cites as the basis of the principle. >>> >>> I can see, intuitively, how the whole notion that the volume of a >>> sphere is concentrated in a thin shell works, but when I try to >>> calculate actual numbers I start running into numerical difficulties at >>> dimensions of around 150 or 200. >>> >>> Even with a 150-dimensional sphere, as the sphere radius increases, the >>> transition in the cumulative probability function of a signal not being >>> within the sphere vs. the signal being inside the sphere is fairly >>> gradual. >>> >>> I want to make some visual aids that show the sphere hardening up as >>> the dimensions get higher -- can anyone point me to math for >>> calculating this that does not involve calculating the gamma function >>> (which is what's blowing up in my face)? >>> >>> Thanks. >>> >>> (And yes, this is badly stated -- low blood sugar and a persistent cold >>> means that right now my fingers are being directed by a large lump of >>> trembling snot, not a cohesive collection of brain cells. Aim your >>> "well asked question" gun at this posting and fire away -- I'll try to >>> clarify as I go.) >>> >>> >> Tim, although I'm lazy and haven't followed the derivation you are >> looking at, however, I also doesn't seem to grasp your problems. With >> the risk of stating the obvious, here's how I would approach it. >> >> Suppose you have an N-dimensional sphere of radius r, and want to know >> how much of its volume is concentrated in the outer shell lying between, >> say, radii (1-alpha)*r and r, where alpha is small. >> >> You know that the volume of an N-dimensional sphere of radius r is given >> by V_N = C_N * r^N, where C_N is some function of N. But since you only >> need to know the fraction of the total volume occupied by the outer >> shell, you don't even need to know C_N, because it's canceled off (along >> with r): >> >> [ V_N(r) - V_N((1-alpha)*r) ] / V_N(r) = 1 - (1-alpha)^n >> >> Which could be further simplified, assuming alpha << 1, as 1 - >> exp(-alpha*N). >> >> I've plotted the fraction of the outer shell volume to the total sphere >> volume for alpha = 0.01, just to see the approximation is fair: >> >> http://i.imgur.com/nkyaPh4.png > >Actually, where Shannon's argument gets lazy is in sticking with the >volume argument: I'm trying to plot the cumulative probability density >per radius, or at least an approximation. The "volume concentrating" >property is valid, and the fact that the cumulative probability function >"hardens" with increasing dimension seems to be true, but Shannon's >argument about the link between the volume being concentrated on the edge >and the cumulative probability function hardening is just hand-waving -- >at least in his 1948 paper.Heresy! ;) This sort of thing is partly why I personally like the practical approach better. --- This email has been checked for viruses by Avast antivirus software. https://www.avast.com/antivirus
Reply by ●March 25, 20172017-03-25
If you want to avoid the gamma functions, maybe you can just rely on the relationship between volume and surface area, which is simply S=n*V, assuming an n-dimensional ball (and its (n-1)-dimensional spherical surface) with radius 1. The volume in a very thin shell of thickness d is then roughly d*S = d*n*V, which is clearly going to be a bigger fraction of V the larger n gets. (see e.g. https://en.wikipedia.org/wiki/N-sphere#Volume_and_surface_area for derivation and other possibly useful formulas.) -Ethan
Reply by ●March 25, 20172017-03-25
Tim, Have you considered using the Gnu MP library to extend the dynamic range of your gamma function? Tim Wescott <seemywebsite@myfooter.really> writes:> So, I'm toying with Shannon's capacity theorem, trying to graph out the > "sphere hardening" effect that he cites as the basis of the principle. > > I can see, intuitively, how the whole notion that the volume of a sphere > is concentrated in a thin shell works, but when I try to calculate actual > numbers I start running into numerical difficulties at dimensions of > around 150 or 200. > > Even with a 150-dimensional sphere, as the sphere radius increases, the > transition in the cumulative probability function of a signal not being > within the sphere vs. the signal being inside the sphere is fairly > gradual. > > I want to make some visual aids that show the sphere hardening up as the > dimensions get higher -- can anyone point me to math for calculating this > that does not involve calculating the gamma function (which is what's > blowing up in my face)? > > Thanks. > > (And yes, this is badly stated -- low blood sugar and a persistent cold > means that right now my fingers are being directed by a large lump of > trembling snot, not a cohesive collection of brain cells. Aim your "well > asked question" gun at this posting and fire away -- I'll try to clarify > as I go.)-- Randy Yates, DSP/Embedded Firmware Developer Digital Signal Labs http://www.digitalsignallabs.com