The Curse of Dimensionality

Introduction

Human beings are used to live in a 3 dimensional space, 4 dimensional is we also consider time. However, most of the mathematical reasoning we are able to carry out on paper is bound to the plane of a piece of paper or a computer screen. Those habits tend to bias our perception to low dimensional spaces and often impair us to really percieve dynamics of high dimensional spaces. Here, we try to provide a simple example of apparent anomalies where low dimensional intuition struggles to extend to high dimensions.

Goals

In this brief tutorial we provide a very simple representation of the bizarre features of multi-dimensional spaces.

Pre-requisites

This short article is very brief and designed to address a broad possible audience. Therefore, we assume the reader is at ease with the basics of algebra and geometry.

Method

Let’s imagine a 2-dimensional square of side 2 unit, centered on the origin of the axis. It basically consistes of 4 boxes, of side 2 units, one box each quadrant as depicted in the image below (black frame).

If we draw 4 circles of unitary radius in each quadrant (green) we have a small space left in the middle where we can inscribe a smaller circle (red).

In two dimensions the radius of the inner circles given by the semi-diagonal of the box, minus the radius of the unitary circle. It can be simply computed as:

𝑟 𝑖 = 12 + 12 ‾ ‾ ‾ ‾ ‾ ‾ ‾ \sqrt - 1 = 2 ‾ \sqrt - 1

In going from 2 to higher dimensions, we replace the circles with (hyper-)spheres and we can easily extend the above formula to higher dimensional space as:

𝑟 𝑖 = 𝑛 𝑑 𝑖 𝑚 ‾ ‾ ‾ ‾ \sqrt - 1

Where $n_{d i m}$

is the dimensionality of the space

import numpy as np
import matplotlib.pyplot as plt
%matplotlib inline


# plot box
plt.plot([-2,-2],[-2,2], 'k')
plt.plot([2,2],[-2,2], 'k')
plt.plot([-2,2],[2,2], 'k')
plt.plot([-2,2],[-2,-2], 'k')
plt.plot([-2,2],[0,0], 'k')
plt.plot([0,0],[-2,2], 'k')

# unitary circle
t = np.linspace(0,2*np.pi,64)
x0 = np.sin(t)
y0 = np.cos(t)

# plot support circles
plt.plot(1+x0,1+y0, 'g')
plt.plot(-1+x0,1+y0, 'g')
plt.plot(1+x0,-1+y0, 'g')
plt.plot(-1+x0,-1+y0, 'g')

# plot inscribed circle
dimensions = 2
s = np.sqrt(dimensions) -1
print ('Inner radius:', s)
plt.plot(s * x0, s * y0, 'r')

#plot diameters
q= s/np.sqrt(2)
plt.plot([-1,-q],[1,q], 'g')
plt.plot([0,-q],[0,q], 'r')

plt.tight_layout()  # Optional ... often improves the layout 
plt.show()

Inner radius: 0.41421356237309515

Results

As we can see from the table below, as soon as our space is 9-dimensional, the radius of the inner circle is as big as the full extension of the containing box.

Moreover, for 10+ dimensions, the inner inner hyper-sphere appears to have a radius bigger than the size of the containng box.

n-dimensions	internal radius
1	0.0000
2	0.4142
3	0.7321
4	1.0000
5	1.2361
6	1.4495
7	1.6458
8	1.8284
9	2.000
10	2.1623

Discussion

The results are very counter-intuitive, as low dimensional intuition would suggest that the inner circle will always be smaller than unit and the containing hyper-cube. Houwever, as we increase the dimensions, we also have an exponentially increasing number of hyper-spheres $n_{h s} = 2_{d i m}^{n}$

, while the inner space keeps increasing in size and it gets more and more “star-shaped”, finally allowing the inscription of very large hyper-spheres.

This simple example despite not having a rigorous mathematical explanation, offers a good reminder that increasing dimensionality usually brings in effects that are difficult to capture unsing low-dimensiona intuition and comes in handy when dealing with very high dimensional problems often incountered in Machine learning.

To note, Shannon leverages the growing surface to volume ratio of a multi-dimensional hyper-sphere to prove the convergence of his Information Theory in his 1948 paper.