A fascinating counterintuitive phenomenon in high dimensions

Machine learning works in high dimensional spaces. These spaces exhibit many counterintuitive phenomena often called the Curse of Dimensionality. In this post, we explore such a fascinating counterintuitive phenomenon that arises in high dimensions. Let’s dive in!

I found about this paradox in Richard Hamming’s Learning to Learn lecture series. One of my favorite quotes from the series is-

"In Science, you shouldn't do what you know; In Engineering, you shouldn't do what you don't know."

The Fun Counterintuitive Phenomenon

Scroll down to see the visualisation of this. Let’s consider a d-dimensional space with a $d$-dimensional box centred at the origin. Its sides have length 4 (stretching from -2 to 2). So its corners are at $(\pm 2, \pm 2, \ldots, \pm 2)$. We add $2^d$ balls of radius 1 with centres at $(\pm 1, \pm 1, \ldots, \pm 1)$. These corner balls touch the sides of the box. Now we add the largest possible ball in the space between the $2^d$ balls.

What is the radius of this central ball? The center of a corner ball sits at $(\pm 1, \pm 1, \ldots, \pm 1)$, which is exactly $\sqrt{d}$ distance away from the origin. Since those corner balls have a radius of 1 and our central ball touches them, its radius is $\sqrt{d} - 1$. Let’s visualise this in 2D, 3D, and higher dimensions.

2D: Four balls in a square

Picture four unit(with radius 1) balls in a 4x4 square. The central ball has a radius of $\sqrt{2} - 1 \approx 0.41$. It sits comfortably in the middle, touching the four corner balls.

3D: Eight balls in a cube

In 3 dimensions, we have eight unit balls packed into a 4x4x4 cube. The central ball gets larger with a radius of $\sqrt{3} - 1 \approx 0.73$. It is still well within the box, touching the eight corner balls.

The Problem in Higher Dimensions

What happens as we keep adding dimensions?

At $d = 9$, the central ball’s radius hits exactly 2. It now touches the walls of the box.

But at $d \geq 10$, things get wild. The central ball’s radius is $> 2$. The ball that we squeezed between the corner balls is now bulging outside the original box!

How can a ball, squeezed between other balls in a box, grow larger than the box itself?

This is the paradox! Try to grasp this intuitively before checking the explanation below.

An intuitive explanation

Let's see what happens when we walk on the cube from its closest point to the origin to its furthest point. Let's take the closest point to the origin as $\vec{x}_0 =(2, 0, 0, \ldots, 0)$ and the furthest point as $\vec{x}_1=(2, 2, 2, \ldots, 2)$. Now if we walk on the cube from $\vec{x}_0$ to $\vec{x}_1$ along a straight line, the path $\vec{x}(t)$ is given by:
$$ \begin{aligned} \vec{x}(t) &= \vec{x}_0 + t(\vec{x}_1 - \vec{x}_0) \\ &= (2, 0, \ldots, 0) + t\big((2, 2, \ldots, 2) - (2, 0, \ldots, 0)\big) \\ &= (2, 2t, 2t, \ldots, 2t) \quad \text{for } t \in [0, 1] \end{aligned} $$ The distance $\|\vec{x}(t)\|$ between point on the cube and the origin is: $$ \|\vec{x}(t)\| = \sqrt{(2, 2t, 2t, \ldots, 2t)} = 2\sqrt{1 + (d-1)t^2} $$ The distance increases from 2 to $2\sqrt{d}$ as t goes from 0 to 1. The corner of the cube is $2\sqrt{d}$ units far away from the origin while the nearest point on the cube is only 2 units away. This is shown in the below plot of distance of trajectory $\vec{x}(t)$ from origin vs t for d=9. [Desmos link].

The corner ball with radius 1 has centre at $(\pm 1, \pm 1, \ldots, \pm 1)$ and is $\sqrt{d}$ units far away from the origin. Since the central ball has to be large enough to touch it, it will eventually get larger than radius 2 thereafter bulging outside the cube.

Finally, a 2D visualisation of N-dimensional cube by 3Blue1Brown showing the large difference in distance of its closest and furthest points from origin is shown below.