Introduction
In data science, when we increase the number of dimensions of the vector space in which the data is located, we observe a mixed impact on the relationships between the data.
On one hand, we observe a beneficial effect that results directly from the weak law of large numbers. On the other hand, increasing the dimensions of the vector space can have surprising negative effects.
We will start by presenting the beneficial aspects, then in a second part we will address what is commonly called the "curse of dimensionality".
The Benefits of Dimensionality
Let us consider a sample of random variables that are independent and identically distributed (i.i.d.). As we increase the number of observations, we see that the empirical mean (i.e., the observed mean) tends to approach the expected value (the theoretical mean).
This result follows directly from the weak law of large numbers.
Let $N$ be independent random variables $\{X_i\}_{i=1}^N$ that are identically distributed such that $X_i \sim p_X$ for all $i = 1, 2, \ldots, N$, where $\mathbb{E}[X_i] = \mu$ and $\mathrm{Var}[X_i] = \sigma^2 < \infty$. The weak law of large numbers guarantees that the empirical mean $\bar{X}_N = \frac{1}{N} \sum_{i=1}^N X_i$ converges to the expected value:
$$ \lim_{N \to \infty} P_X(|\bar{X}_N - \mu| < \epsilon) = 1 \quad \forall \epsilon > 0 $$
In other words, given a distribution $p_X$, the empirical mean $\bar{X}_N$ provides a realistic estimate of the mean $\mu$, and the quality of this estimate improves as $N \to \infty$.
This is further detailed by the central limit theorem, which states that the standardized error $Z_N$ is distributed according to a normal distribution centered at zero, whose variance is inversely proportional to $N$.
The central limit theorem (CLT) states that:
$$ Z_N = \sqrt{N} \frac{\bar{X}_N - \mu}{\sigma} \sim \mathcal{N}(0,1) $$
And since $Var(aX) = a^2 Var(X)$
$$ Var\left(\frac{Z_N}{\sqrt{N}}\right) = \frac{1}{N}Var\left(Z_N\right) = \frac{1}{N} $$
So,
$$ \frac{\bar{X}_N - \mu}{\sigma} = \frac{Z_N}{\sqrt{N}} \sim \mathcal{N}\left(0, \frac{1}{N}\right) $$
Which means that the emperical mean follows this distribution:
$$ \bar X_N \sim \mathcal N\left(\mu, \frac{\sigma^2}{N}\right) $$
Try entering a sample size between 2 and 5000, then observe the result: the empirical mean tends to get closer to the theoretical mean $\mu$!
Demonstration - mean convergence
We can see that as the number of draws increases, the empirical mean, shown in blue, tends to converge toward the theoretical mean, shown in red. The orange area represents the standard deviation of the empirical mean, which also decreases as the number of samples increases.
Note that the CLT implies that for a given number of samples, the blue curve has about 68% chance of landing within the orange zone.
Demonstration - relative standard deviation
We can observe here that, regardless of the distribution chosen, the standard deviation of the empirical mean decreases like $1/\sqrt{n}$.
Introduction
We have just seen that the precision of the empirical mean of an aggregate of i.i.d. random variables increases with the number of observed samples. However, we also observe an adverse phenomenon when the number of data dimensions increases. This phenomenon is called the curse of dimensionality.
The Curse of Dimensionality
If we consider the $l_p$ norm distance between all pairs of vectors in our set, we observe a phenomenon of concentration similar to that observed in the beneficial aspect. In fact, the sum in the $l_p$ norm acts as an aggregate. We can then show that the average distance increases faster than the variance, creating this concentration phenomenon.
Let $D$ be a metric space of dimension $D$ (for example, $(\mathbb R^D, L_p)$). A point $x_i$ in this space is a vector with $D$ components $x_i = \{x_1^1, \dots, x_i^D\}$ that can be modeled as a set of $D$ i.i.d. random variables:
$$X_i = \{X_1^1, \dots, X_i^D\}$$
where $X_i^j \sim f_X, j = 1, 2, \dots, D, f_X$ is a distribution in 1 dimension.
Let $\{ X_i \}_{i=1}^N$ be $N$ points of dimension $D$; the $L_p$ distance between $x_i$ and $x_j$ is defined by:
$$||x_i - x_j||_p = \left[ \sum_{k=1}^{D}{(x_i^k - x_j^k)} \right]^{1/p}, \text{for} \ 1 \leq p \lt \infty$$
and with the special case:
$$||x_i - x_j||_\infty = \lim_{p \to \infty} {\left[ \sum_{k=1}^{D}{(x_i^k - x_j^k)} \right]^{1/p}} = \max_{k=1,2,\dots,D} {\left(x_i^k - x_j^k \right)}$$
Note that the sum acts as an aggregation, and we expect that $||x_i - x_j||_p$ converges as $D \to \infty$.
Demonstrations
While the following demonstrations are all linked, be mindful that there are two generation buttons. This allows you to compare different sets of parameters, but if you want to sync all graphs make sure to press both buttons.
Demonstration - 2D projection of multidimensional vectors
Valeur :
Here, we select $N$ points in $D$ dimensions. We then choose a random point as the center and calculate the $L_p$ norm distance to all other points in the set.
Each point is then placed on a $2D$ circle where the radius represents the distance between the point and the center, and the angle is random.
The red ring represents a circle of radius $\mu$, which is the average distance between the central point and the other points. Because the visualization remains to scale, pay close attention to the axes : they expand as both the dimensionality and $\mu$ increase. At the same time, notice how the ring of points tightens. This show that altought distances increase, they concentrate around the mean.
Note that the angles here are for illustrative purposes only, they say nothing about the actual position of the points in $D$ dimensions. This is a trick that allows us to represent high-dimensional points in 2D.
Demonstration - Pairwise distances
Here, we randomly plot $N$ points of dimensions from 1 to 128, and then calculate the $L_p$ norm distance between each pair of points. We then represent the distance between the points as a histogram.
As the dimensionality increases, the histograms shift to the right but we don't yet observation a concentration phenomenon. The spread of absolute distances between every pair of points stays roughly the same. However, things change when you compare relative distances instead of absolute ones.
Demonstration - Normalized pairwise distances
Indeed, by normalizing the distances between points by dividing them by the average distance (or the maximum distance in the case of a uniform distribution), we observe that the width of the histograms decreases as the dimensionality increases.
As a result, the relative distances between points tend to cluster together in high dimensions. Thus, the points are all roughly the same distance apart from one another.
Demonstration - σ/μ goes to zero
We plot here the coefficient of variation, calculated using the formula: $\sigma/\mu$
The fact that this quantity tends to $0$ as $D \to \infty$ is mathematically consistent with the observations made in the previous proofs: The average distance between the points increases more rapidly than the standard deviation. Therefore, the relative distance between the points tends to concentrate around the average distance as $D$ increases.
In real life, this concentration phenomenon negatively impacts the effectiveness of machine learning algorithms that rely on the average distance between data points: kNN, classifiers, etc. That is why this phenomenon is referred to in the literature as "the curse of dimensionality".