Skip to article frontmatterSkip to article content
Site not loading correctly?

This may be due to an incorrect BASE_URL configuration. See the MyST Documentation for reference.

High Dimensional Data & The Curse of Dimensionality

English · فارسی

High Dimensional Data & The Curse of Dimensionality

Computer Science Dept, Ferdowsi University of Mashhad

Introduction

In modern data mining and machine learning, we often deal with data in very high-dimensional spaces (e.g., images, text embeddings, genomic data). A dataset is typically represented as an n×dn \times d matrix D\mathbf{D}.

Understanding the nature of high-dimensional space, or hyperspace, is very important because it does not behave like the more familiar geometry in two or three dimensions. This phenomenon is often referred to as the Curse of Dimensionality.

Key phenomena we will explore:

  1. Volume Concentration: The volume of a hypersphere vanishes relative to the hypercube.

  2. The Problem of Local Neighborhoods: Why “local” methods like k-NN fail (based on Elements of Statistical Learning).

  3. The Thin Shell: Most of the volume concentrates near the surface (measured on the sampling page).

  4. Orthogonality: Random vectors in high dimensions are nearly orthogonal.

  5. Gaussian Behavior: Points concentrate in a thin ring around radius d\sqrt{d} — also measured on the sampling page.


Geometry of Hyperspace: Cubes and Spheres

Let’s define the two most basic shapes in dd-dimensions.

The Hypercube

The data space is often viewed as a dd-dimensional hyper-rectangle or hypercube. For a hypercube Hd(l)H_d(l) with side length ll, the volume is:

Vol(Hd(l))=ld\text{Vol}(H_d(l)) = l^d

The Hypersphere

We write Bd(r)B_d(r) for the solid ball and Sd(r)S_d(r) for its surface. The distinction matters: the volume below is a property of the ball, and its boundary is a single layer of measure zero. The volume of the dd-dimensional ball of radius rr is:

Vol(Sd(r))=Kdrd=πd/2Γ(d2+1)rd\text{Vol}(S_d(r)) = K_d r^d = \frac{\pi^{d/2}}{\Gamma(\frac{d}{2}+1)} r^d

Where Γ\Gamma is the Gamma function.

Figure 6.4. Hypersphere inscribed inside a hypercube: in (a) two and (b) three dimensions

The Empty Center (The “Porcupine” Effect)

Consider the space enclosed within the largest hypersphere that can be accommodated within a hypercube of side length l=2rl=2r. The ratio of their volumes is:

lim⁡d→∞Vol(Sd(r))Vol(Hd(2r))=lim⁡d→∞πd/22dΓ(d2+1)→0\lim_{d \to \infty} \frac{\text{Vol}(S_d(r))}{\text{Vol}(H_d(2r))} = \lim_{d \to \infty} \frac{\pi^{d/2}}{2^d \Gamma(\frac{d}{2}+1)} \to 0

Implication: As dimensionality increases, the volume of the hypersphere becomes negligible compared to the hypercube. Most of the volume of the hypercube is in the corners, whereas the center is essentially empty.

Corners in High Dimension

Conceptual view of high-dimensional space: (a) two, (b) three, (c) four, and (d) higher dimensions. In d dimensions there are 2d2^d “corners” and 2d−12^{d−1} diagonals. The radius of the inscribed circle accurately reflects the difference between the volume of the hypercube and the inscribed hypersphere in dd dimensions.


Source
<Figure size 1000x600 with 1 Axes>

The Problem of Local Neighborhoods (k-NN)

One of the most significant manifestations of the curse of dimensionality affects “local” methods like k-Nearest Neighbors (k-NN).

Edge Length of Neighborhoods

Suppose we have inputs uniformly distributed in a pp-dimensional unit hypercube. We want to form a local neighborhood that captures a fraction rr of the observations. Since this corresponds to a fraction of the unit volume, the expected edge length ep(r)e_p(r) of this neighborhood is:

ep(r)=r1/pe_p(r) = r^{1/p}

FIGURE 2.6. The curse of dimensionality is well illustrated by a subcubical neighborhood for uniform data in a unit cube. The figure on the right shows the side-length of the subcube needed to capture a fraction r of the volume of the data, for different dimensions p. In ten dimensions we need to cover 80% of the range of each coordinate to capture 10% of the data

Let’s visualize this for different dimensions (pp) and fractions (rr).

Source
<Figure size 800x600 with 1 Axes>

Analysis: In 10 dimensions (p=10p=10), to capture just 10% (r=0.1r=0.1) of the data, we need to cover 80% of the range of each input variable. Such neighborhoods are no longer “local”. To find neighbors, we must look very far away.

Distance to Boundary

Another consequence is that sampling density is sparse. For NN data points in a pp-dimensional unit ball, the median distance from the origin to the closest data point is:

d(p,N)=(1−(12)1/N)1/pd(p,N) = \left(1 - \left(\tfrac{1}{2}\right)^{1/N}\right)^{1/p}

For N=500N=500 and p=10p=10, this distance is ≈0.52\approx 0.52, which is more than halfway to the boundary. Hence, most data points are closer to the boundary of the sample space than to any other data point. This makes prediction a problem of extrapolation rather than interpolation.



Orthogonality: Random Directions Are Nearly Perpendicular

Another counter-intuitive property: in high dimension every direction is nearly orthogonal to every other direction. Two vectors drawn at random are almost always almost perpendicular.

The diagonal of the cube versus an axis

Consider the diagonal vector in a hypercube 1=(1,1,…,1)T\mathbf{1} = (1, 1, \dots, 1)^T. The angle θd\theta_d between this diagonal and any coordinate axis e1=(1,0,…,0)T\mathbf{e}_1 = (1, 0, \dots, 0)^T is:

cos⁡θd=e1T1∣∣e1∣∣⋅∣∣1∣∣=11⋅d=1d\cos \theta_d = \frac{\mathbf{e}_1^T \mathbf{1}}{||\mathbf{e}_1|| \cdot ||\mathbf{1}||} = \frac{1}{1 \cdot \sqrt{d}} = \frac{1}{\sqrt{d}}

As d→∞d \to \infty, cos⁡θd→0\cos \theta_d \to 0, which means θd→90∘\theta_d \to 90^\circ. The diagonal is effectively orthogonal to the axes!

Furthermore, random vectors in high dimensions are nearly orthogonal to each other.

Source
Dot products of random pairs in 200-D:
Vector 0 . Vector 1 = -0.0227
Vector 0 . Vector 2 = 0.0015
Vector 0 . Vector 3 = 0.0229
Vector 1 . Vector 2 = -0.0327
Vector 1 . Vector 3 = 0.0843
Vector 2 . Vector 3 = 0.0176

Summary

  • High-dimensional space is empty in the center.

  • Volume is in the corners or a thin shell at the surface.

  • Neighbors are far away (breaking local methods like k-NN).

  • Random vectors are orthogonal.

The computations behind these statements — the shell volume, rejection sampling, uniform points on the sphere and inside the ball, and the Gaussian annulus — are on Sampling in High Dimensional Spaces.

References

  1. Zaki & Meira (2020), Chapter 6 (high-dimensional space).

  2. Blum, A., Hopcroft, J., & Kannan, R. (2020). Foundations of Data Science. Cambridge University Press.

  3. Hastie, T., Tibshirani, R., & Friedman, J. (2009). The Elements of Statistical Learning.

Exercises

  1. Compute the ratio of the volume of the unit ball to the volume of the cube [−1,1]d[-1,1]^d for d=2,10,100d=2,10,100. At which dimension does the ball hold less than 1%1\% of the cube?

  2. For two random unit vectors in Rd\mathbb{R}^d, show that E[cos⁡2θ]=1/d\mathbb{E}[\cos^2\theta]=1/d and plot the histogram of cos⁡θ\cos\theta for d=2d=2 and d=100d=100. What does the concentration mean for the words nearest and farthest?

  3. Compute the fraction of the ball’s volume in the shell 0.9≤r≤10.9\le r\le 1 as a function of dd, and explain the consequence for sampling points uniformly in a high-dimensional ball.

  4. Using the notebook’s neighbourhood argument, show that the edge length of a cube holding a fixed fraction pp of the points grows like p1/dp^{1/d}, and evaluate it for p=0.01p=0.01 and d=100d=100.

References
  1. Zaki, M. J., & Meira, W. (2020). Data Mining and Machine Learning: Fundamental Concepts and Algorithms (2nd ed.). Cambridge University Press. https://www.cambridge.org/9781108497367