# 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:

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:

Where

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()
```

## 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

, 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.

## References

C.E. Shannon, A Mathematical Theory of Communication, The Bell System Technical Journal,Vol. 27 (948) 379β423, 623β656

## Are you ready to take smarter decision?

Otherwise you can always drop a comment…