Hypersphere Volume


abendstimmung, ball-shaped, cloudsIn our last article we looked at how the dimension of data space impacts Machine Learning algorithms.  This is often referred to as the curse of dimensionality.

At the heart of the article we discussed the fact that an hypersphere hyper-volume trends to zero as dimension increases.

Here I want to demonstrate how to find the hyper-volume of an hypersphere of dimension N.

The Math Reference Project gives a short & sweet demonstration.  I personally found it hard to follow.  Foundations of Data Science by John Hopcroft & Ravindran Kannan (chapter 2) starts a demonstration but does cut short.

I wanted to contribute a complete demonstration because I just love that type of mathematical problem.  It’s one of my many flaws.

Approach

countryside, grass, grasslandWe’ll use the Cartesian coordinates and the fact that the volume of an hypersphere of dimension N can be found by integrating the volume of an hypersphere of dimension N-1 with an infinitesimal thickness:

V_N(R) = \displaystyle\int_{-R}^R V_{N-1}(\sqrt{R^2-x^2}) dx

imageWe’ll find the volume for a few dimensions then we’ll generalize the result.

N=1

Well, V_1(R) = 2 R:  it’s a line.

N=2

We already know the result should be V_2(R) = \pi R^2, but let’s demonstrate it.

\begin{array}{lcl} V_2(R) &=& \displaystyle\int_{-R}^R V_1(\sqrt{R^2-x^2}) dx\\ &=& \displaystyle\int_{-R}^R 2 \sqrt{R^2-x^2} dx\\&=& 2 R^2 \displaystyle\int_{-R}^R \sqrt{1- (\frac {x}{R})^2} d \frac{x}{R}\\&=& 2 R^2 \displaystyle\int_{-\pi/2}^{\pi/2} \sqrt{1- \sin^2 \theta} \, d (\sin \theta) \text{ where } \sin \theta = \frac{x}{R}\\&=& 2 R^2 \displaystyle\int_{-\pi/2}^{\pi/2} \cos^2 \theta \, d \theta\\&=& 2 R^2 \cdot \frac{1}{2} [ \theta + \sin {2 \theta} ]_{-\pi/2}^{\pi/2}\\ &=& \pi R^2\end{array}

N=3

We know the result should be V_3(R) = \frac{4}{3} \pi R^3, but again, let’s demonstrate it.

\begin{array}{rcl}V_3(R) &=& \displaystyle\int_{-R}^R V_2(\sqrt{R^2-x^2}) dx\\&=& \displaystyle\int_{-R}^R \pi (\sqrt{R^2-x^2})^2 dx\\&=& \pi (2 R^3 - \displaystyle\int_{-R}^R x^2 dx)\\&=& \pi (2 R^3 - \frac{2 R^3}{3})\\&=& \frac{4}{3} \pi R^3\end{array}

N=4

Let’s find the hyper-volume of an hypersphere of dimension 4.

\begin{array}{rcl} V_4(R) &=& \displaystyle\int_{-R}^R V_3(\sqrt{R^2-x^2}) dx\\&=& \displaystyle\int_{-R}^R \frac{4}{3} \pi (\sqrt{R^2-x^2})^3 dx\\&=& \frac{4}{3} \pi R^4 \displaystyle\int_{-R}^R (1-(\frac{x}{R})^2)^\frac{3}{2} d(\frac{x}{R})\\&=& \frac{4}{3} \pi R^4 \displaystyle\int_{-\frac{\pi}{2}}^{\frac{\pi}{2}} (1-\sin^2 \theta)^\frac{3}{2} d(\sin \theta) \text{ where } \sin \theta = \frac{x}{R}\\&=& \frac{4}{3} \pi R^4 \displaystyle\int_{-\frac{\pi}{2}}^{\frac{\pi}{2}} \cos^3 \theta \cdot \cos \theta d \theta\\&=& \frac{4}{3} \pi R^4 \displaystyle\int_{-\frac{\pi}{2}}^{\frac{\pi}{2}} \cos^4 \theta d \theta\\&=& \frac{4}{3} \pi R^4 ([\frac{\cos^3 \theta \sin \theta}{4}]_{-\frac{\pi}{2}}^{\frac{\pi}{2}} + \frac{3}{4} \displaystyle\int_{-\frac{\pi}{2}}^{\frac{\pi}{2}} \cos^2 \theta d \theta)\\&=& \frac{4}{3} \pi R^4 (0 + \frac{3}{4} \frac{1}{2} [\theta + \sin 2 \theta]_{-\frac{\pi}{2}}^{\frac{\pi}{2}})\\&=& \frac{\pi^2}{2} R^4\end{array}

Generalization

Now we have quite some practice.  Let’s try to generalize the hypersphere volume formula.

First let’s assume the volume formula has the following form:

V_N(R) = K_N R^N

Where K_N is a constant (independent of R).  We’ll see that we only need to assume that form for the volumes of N-1 and less.  Since we already know it to be true for N <= 4, it isn’t a strong assumption.

With that, let’s proceed:

\begin{array}{rcl} V_N(R) &=& \displaystyle\int_{-R}^R V_{N-1}(\sqrt{R^2-x^2}) dx\\&=& K_{N-1} \displaystyle\int_{-R}^R (R^2-x^2)^\frac{N-1}{2} dx\\&=& K_{N-1} R^N \displaystyle\int_{-R}^R (1-(\frac{x}{R})^2)^\frac{N-1}{2} d(\frac{x}{R})\\&=& K_{N-1} R^N \displaystyle\int_{-\frac{\pi}{2}}^{\frac{\pi}{2}} \cos^{N-1} \theta \cdot \cos \theta d \theta \text{ where } \sin \theta = \frac{x}{R}\\&=& K_{N-1} R^N \displaystyle\int_{-\frac{\pi}{2}}^{\frac{\pi}{2}} \cos^N \theta d \theta\end{array}

We’re dealing with a recursion here, so let’s rewrite this equation in terms of two sets of constants:

\begin{array}{rcl}V_N(R) &=& K_N R^N = C_N K_{N-1} R^N \text{ where } C_N = \displaystyle\int_{-\frac{\pi}{2}}^{\frac{\pi}{2}} \cos^N \theta d \theta\\&\implies& K_N = C_N K_{N-1}\\&\implies& K_N = (\displaystyle\prod_{i=2}^N C_i) K_1 = 2 \displaystyle\prod_{i=2}^N C_i \text{ (since }K_1=2 \text{)}\end{array}

Let’s work on the set of constants C.  We know the first couple of values:

\begin{array}{rcl} C_0 &=& \pi \\ C_1 &=& 2 \\ C_2 &=& \frac{\pi}{2} \end{array}

We can also obtain a recursive expression.

C_N = \displaystyle\int_{-\frac{\pi}{2}}^{\frac{\pi}{2}} \cos^N \theta d \theta = \frac{N-1}{N} \displaystyle\int_{-\frac{\pi}{2}}^{\frac{\pi}{2}} \cos^{N-2} \theta d \theta \implies C_N = \frac{N-1}{N} C_{N-2}

If we observes that

\begin{array}{rcl} C_N C_{N-1} &=& \frac{N-1}{N} C_{N-2} \frac{N-2}{N-1} C_{N-3}\\&=& \frac{N-2}{N} C_{N-2} C_{N-3}\\&=& \frac{N-2}{N} \frac{N-4}{N-2} C_{N-4} C_{N-5}\\&=& \frac{N-4}{N} C_{N-4} C_{N-5}\\&=&\begin{cases} \frac{2}{N} C_2 C_1 & \text{if N is even} \\ \frac{1}{N} C_1 C_0 & \text{if N is odd} \end{cases}\\&=&\begin{cases} \frac{2 \pi}{N} & \text{if N is even} \\ \frac{2 \pi}{N} & \text{if N is odd} \end{cases}\\&=&\frac{2 \pi}{N}\end{array}

Then we can write

\begin{array}{lcl} K_N &=& 2 \displaystyle\prod_{i=2}^N C_i \\ &=& \begin{cases} 2 \cdot \frac{2 \pi}{N} \frac{2 \pi}{N-2} \dots \frac{2 \pi}{4} C_2 & \text{if N is even} \\ 2 \cdot \frac{2 \pi}{N} \frac{2 \pi}{N-2} \dots \frac{2 \pi}{3} & \text{if N is odd} \end{cases}\\ &=& \begin{cases} \pi \cdot \frac{2 \pi}{N} \frac{2 \pi}{N-2} \dots \frac{2 \pi}{4} & \text{if N is even} \\ 2 \cdot \frac{2 \pi}{N} \frac{2 \pi}{N-2} \dots \frac{2 \pi}{3} & \text{if N is odd} \end{cases}\end{array}

Therefore we found that

\begin{array}{lcl} V_N (R) &=& \begin{cases} \pi \cdot \frac{2 \pi}{N} \frac{2 \pi}{N-2} \dots \frac{2 \pi}{4} \cdot R^N & \text{if N is even} \\ 2 \cdot \frac{2 \pi}{N} \frac{2 \pi}{N-2} \dots \frac{2 \pi}{3} \cdot R^N & \text{if N is odd} \end{cases}\end{array}

Which gives us an explicit formula for the volume of an hypersphere in N dimensions.

Limit

Given the formula for K_N \text{ (and that } V_N(R) =K_N R^N, it is easy to it is a product of smaller and smaller terms.

As soon as N becomes bigger than 2 \pi (i.e. at N=6), the terms becomes smaller than 1 and therefore the products start to shrink.

This is why the hyper volume vanishes as N grows towards infinity.

Values

We can then compute values (for R=1):

Dimension Formula Value
1 2 2
2 \pi 3.141592654
3 \frac{4 \pi}{3} 4.188790205
4 \pi \cdot \frac{2 \pi}{4}=\frac{\pi^2}{2}

4.934802201

5 2 \cdot \frac{2 \pi}{5} \frac{2 \pi}{3}=\frac{8 \pi^2}{15}

5.263789014

6 \pi \cdot \frac{2 \pi}{6} \frac{2 \pi}{4}= \frac{\pi^3}{6} 5.16771278

which corresponds to what we gave in our last article.

Summary

We demonstrated how to find the hyper volume of an hyper sphere of dimension N and could rigorously find that the hyper volume vanishes as the dimension grows.

That result is counterintuitive and this is why we thought a mathematical proof was warranted.

Advertisements

One thought on “Hypersphere Volume

  1. Pingback: Hyperspheres & the curse of dimensionality | Vincent-Philippe Lauzon's blog

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s