Tamanna Hossain-Kay

Weird Stuff in High Dimensions

Tamanna Hossain-Kay / 2021-11-28


We’re usually putzing around in a 3 dimensional space, perceiving the 4th dimension of time as something we’re moving forward through. Attempts to explain our reality, however, have intriguingly and disturbingly given rise to the possibility of higher dimensions. Superstring Theory, for example, posits 10 dimensions to provide a unifying framework between general relativity and quantum mechanics. M-Theory, on the other hand, posits 11 dimensions, and Bosonic String Theory a daunting 26 dimensions! In machine learning we work in even higher dimensions to model data. For example, Google’s BERT projects words on to 768 or 1024 dimensional spaces in order to model human language.

What do these higher dimensions “look like”? The short answer is that to beings such as ourselves, i.e., mostly 3D with some limited 4D perception: very weird! Visualizing these higher dimensions in the traditional sense doesn’t seem possible for us, but we can still get insight into these spaces through mathematics. Frustratingly, many of these insights break from our usual 2D or 3D intuitions. As Thomas Banchoff wrote, “All of us are slaves to the prejudices of our own dimension.”

Read on to mathematically “see” some weird stuff in high dimensions.

Sources: This post is compiled using notes from CMU, Cornell, and UC Davis with some additional figures and exposition for my own understanding.

Warmup
Sphere
Cube
Gaussians

Warmup

Consider a ddimensional unit square. If were to place n points inside the square such that each coordinate for each point is drawn uniformly at random from the interval [0,1], what can we say about the distribution of distances between points?

Our usual intuition might be that the points will be spread out somewhat evenly. This holds true in our familiar 2D and 3D spaces. However, something different happens in higher dimensions.

Consider that the distance between any two points X=(xi,,xd) and Y=(y1,,yd) is defined as ,

D=|XY|=i=1d(xiyi)2

where for each dimension i{1,,d},

xii.i.dUnif(0,1)yii.i.dUnif(0,1)

Then (xiyi)2 are i.i.d random variables for all i, and D2 is a summation of independent random variables.

So in high dimensions, the Law of Large Numbers applies and D2 converges to its expected value. The distances are then concentrated around a mean! However, in lower dimensions (like the 2D and 3D we’re perceptually accustomed to), D2 is pre-convergence and the distances are still spread out.

Sphere

Consider a d dimensional sphere of unit radius centered at the origin: {(x1,x2,,xd):i=1dxi21}

Compute surface area and volume
Volume goes to zero
Volume is near the equator
Volume is a narrow annulus

Compute surface area and volume

The surface area A(d) and the volume V(d) of a unit-radius sphere in d dimensions are given by A(d)=2πd2Γ(d2) and V(d)=πd2d2Γ(d2) where Γ is the Gamma functions.

Proof

Cartesian Coordinates

First, lets recall that in 3-dimensions a sphere of radius a is defined as x2+y2+z2=a2. In order to compute its volume we consider the region x2+y2+z2a2.

Thus, the volume of the sphere can be computed as:

V(3)=aaa2x2a2x2a2x2y2a2x2y21dzdydx Extending this formula to a d-dimensional sphere of radius 1 gives:

V(d)=111x121x121x12xd121x12xd12 dxd dxd1dx1

Polar Coordinates

In 3-dimensions, a sphere of radius a is defined as all points where 0ϕπ, 0θ2π, and 0ra. Then the volume of the sphere can be computed as,

V(3)=0π02π0ar2sin(ϕ)drdθdϕ Using the concept of a solid angle to further simplify the integral by allowing us to write it over a coordinate free ‘direction’. Let dΩ=sin(ϕ)dθdϕ be the surface area of the infinitismal piece of the solid angle S3 of the sphere.

Then,

V(3)=S3r=0ar2dΩdr Extending this formula to a d-dimensional sphere of unit radius gives:

V(d)=Sdr=01rd1 dr dΩ=(Sd dΩ)(r=01rd1 dr)(Variables are independent)=1dSd dΩ=1dA(d)(i)

Source: Mathemathinking

A Trick

Consider a different problem: I(d)= def e(x12+x22++xd2)dxddx2 dx1

This can be computed in both Cartesian and Polar coordinates. They will be equated to solve our problem.

Cartesian: I(d)=e(x12+x22++xd2)dxddx2 dx1=[e(x1)2 dx1]d(independent coordinates across same range)=(π)d=πd2 Polar: I(d)=e(x12+x22++xd2)dxddx2 dx1=Sder2rd1 dr dΩ(Definition of sphere+ change to polar)=(Sd dΩ)(er2rd1 dr)(Independent variables)=A(d)20ettd1212t dt (Let t=r20, so r=t, dr=12t dt ) =A(d)0ettd21 dt=A(d)Γ(d2)(Definition of Γ function).

Then by equating the solution for I(d) in cartesian and polar coordinates,

A(d)=2πd2Γ(d2)

Finally, using equation (i),

V(d)=πd2d2Γ(d2)

More generally, the surface area and volume equations for a dsphere of radius r are,

Ar(d)=2πd2Γ(d2)rd1=A(d)rd1andVr(d)=πd2Γ(d2+1)rd=V(d)rd

Volume goes to zero

By Stirling’s Formula, Γ(d2)2πd/2(d/2e)d2=4πd(d2e)d2

So, the denominator of V(d) grows faster than its numerator since dd2 grows much faster than πd2,. Thus,

V(d)0 as d

Volume is near the equator

Most of the volume of the sphere is near the equator.

Without loss of generality, pick any of the d poles of the sphere as the North Pole, say the pole along x1. Then the North Pole is x1=1.

Define the equator as the (d1) dimensional sphere: {x||x∣≤1,x1=0}. This is formed by the intersection of the x1=0 plane with the dsphere. It has volume V(d1). Note that, in 3-dimensions this is (familiarly) a circle.

The equator divides the sphere into two hemispheres, or d-dimensional half spheres, one upper and one lower.

Consider a plane x1=ϵ slightly above the x1=0 plane, for some ϵ>0. Less than 2ε(d1)ed12ε2 fraction of the volume in the upper hemisphere lies above the x1=ϵ plane. This value drops exponentially with ϵ2 as ϵ increases and d goes to infinity. Same is true for volume below x1=ϵ in the lower hemisphere.

Proof

Without loss of generality we will show the bound for the upper hemisphere.

Define the region T as the portion of the sphere above the x1=ϵ plane: T={x||x∣≤1,x1ε}. Then,

Upper bound on proportion of volume above ϵ= Upper bound of Vol(T) Lower bound of Vol( hemisphere )= Upper bound of Vol(T) Lower bound of 12Vol(d)

Slice in the T region of the dsphere’s upper hemisphere.

Vol(T)=ϵ1ΔV dx1(ΔV is a cross-sectional slice )=ϵ1V(d1)rd1 dx1(Volume of (d1) dimensional sphere of radius r)=V(d1)ϵ1(1x1)d12 dx1(r=1x12)V(d1)ϵ1ex12d12 dx1(Lemma 1)V(d1)ϵex12d12 dx1(ex12d120x1[ϵ,])V(d1)ϵx1ϵex12d12 dx1(x1ϵ1x1[ϵ,])=V(d1)2ϵd12ϵex12d12 d(x12d12)(Subst: u=x12d12;du=2d12x1dx1)=V(d1)ϵ(d1)ex12d12|ϵ=1ϵ(d1)ed12ϵ2V(d1) 12V(d)=01V(d1)rd1 dx1=V(d1)01(1x12)d12 dx1V(d1)01d1(1x12)d12 dx1V(d1)01d1(1d12x12)dx1( Lemma 2)V(d1)01d1(1d121d1)dx1(t21d1x1[0,1d1])=V(d1)01d112=12d1V(d1)

Thus,

Upper bound on proportion of volume above ϵ=1ϵ(d1)ed12ϵ2V(d1)12d1V(d1)=2ε(d1)ed12ε2

Volume is a narrow annulus

Most of the volume of there sphere is concentrated near its boundary. Hence, if you peel a high-dimensional orange, then there is almost nothing left! (Source: UC Davis)

The ratio of the volume of a dsphere of radius 1ϵ to one with unit raduis is,

V1ϵ(d)V1(d)=(1ε)dV(d)V(d)=(1ε)d This ratio 0 as d. So in high dimensions, all of the volume of the sphere is concentrated in a narrow annulus at the surface.

Cube

Consider a ddimensional cube with unit-length sides centered at the origin.

This is in interesting contrast to what we saw of the ddimensional sphere of unit radius we saw earlier where,

The relationship between the unit-length hypercube and unit-radius hypersphere as d increases is shown below.

Illustration of the relationship between the sphere and the cube in 2, 4, and d-dimensions.(Source: CMU with minor edit)

Other weird stuff

H={xi=1dxi=d2}
(Source: CMU)

Gaussians