High-Dimensional Geometry and Concentration of the Norm

Why a Gaussian vector lives on a thin shell, why random directions are nearly orthogonal, and why almost all of a sphere's volume sits near any equator.

High-Dim ProbabilityAdvanced⏱ 3 hours13 min readhigh dimensionnorm concentrationspherespherical caporthogonality

5 problems →

AssumesConcentration Inequalities

The norm of a random vector

PropositionThe expected norm of a Gaussian vector

Let $X \sim \Ncal(0,I_d)$ . Then $\E\norm{X}_2^2 = d$ exactly, and

\sqrt{d} - \frac{1}{\sqrt d} \;\le\; \sqrt{d-1} \;\le\;\E\norm{X}_2 \;\le\; \sqrt d, \qquad \Var\big(\norm{X}_2\big) \le 1 .

TheoremConcentration of the norm

Let $X = (X_1,\dots,X_d)$ have independent, mean-zero coordinates with $\E X_i^2 = 1$ and $\norm{X_i}_{\psi_2} \le K$ . Then there is an absolute constant $C$ with

\Big\| \norm{X}_2 - \sqrt d \Big\|_{\psi_2} \le CK^2 .

Equivalently, $\P\big(\big|\norm{X}_2 - \sqrt d\big| \ge t\big) \le 2\exp\big(-ct^2/K^4\big)$ for all $t \ge 0$ , with $c$ absolute. The bound does not depend on $d$ .

Key idea

Step 3 is where the dimension cancels. The squared norm has fluctuations of order $\sqrt d$ — that is the ordinary central-limit scaling for a sum of $d$ terms — and the square root map has derivative $1/(2\sqrt d)$ at the relevant point, so the fluctuations of the norm itself are of order $\sqrt d \cdot 1/\sqrt d = 1$ . Nothing deeper than the chain rule is happening, but the consequence is the defining phenomenon of the subject.

Run it: The norm of a Gaussian vectorThe distribution of ‖X‖₂ for X ~ N(0, I_d) as the dimension grows, against the √d prediction.

What this does not say

The theorem is about the norm, not about the coordinates. Each coordinate $X_i$ is a perfectly ordinary $\Ncal(0,1)$ variable, spread over the whole real line; nothing about it concentrates. The concentration is a property of the aggregate, and it requires independence across coordinates. Correlated coordinates — the normal case for real embeddings — can fail this badly: if all coordinates are equal, $\norm{X}_2 = \sqrt d|X_1|$ has fluctuations of order $\sqrt d$ .

Near-orthogonality

PropositionRandom directions are nearly orthogonal

Let $u, v$ be independent and uniform on the unit sphere $S^{d-1}$ . Then

\E\ip{u}{v} = 0, \qquad \Var\big(\ip{u}{v}\big) = \frac1d, \qquad \P\big(|\ip{u}{v}| \ge t\big) \le 2e^{-dt^2/2}.

Run it: Embedding geometry and retrievalCosine similarity between random unit vectors in R^d, and the separation available to a retriever.

Spheres, caps and shells

TheoremMeasure concentration on the sphere

Let $\sigma$ be the uniform probability measure on $S^{d-1}$ and fix a unit vector $\theta$ . For $t \in [0,1]$ ,

\sigma\big(\{u : \ip{u}{\theta} \ge t\}\big) \le e^{-dt^2/2}.

In particular, for $t = c/\sqrt d$ the cap still carries a constant fraction of the measure, while for $t$ fixed the fraction is exponentially small in $d$ .

PropositionVolume concentrates in a thin shell

Let $B^d$ be the unit ball in $\R^d$ and $\eps \in (0,1)$ . The fraction of the volume of $B^d$ lying at radius less than $1-\eps$ is exactly $(1-\eps)^d \le e^{-\eps d}$ . Consequently, all but an $e^{-\eps d}$ fraction of the volume lies in the shell of thickness $\eps$ at the boundary.

Taking $\eps = 5/d$ : over $99\%$ of the volume of the $d$ -dimensional unit ball lies within $5/d$ of the surface. In $\R^{1000}$ , that is the outermost half-percent of the radius.

HeuristicThe curse and the blessing are the same phenomenon

Heuristic — a reasoning shortcut that predicts the right answer in the regimes discussed here. It is not a proof and can fail outside them.

Concentration is usually introduced as the "curse of dimensionality" and separately as the reason random projections work. They are the same statement seen from two sides.

The pessimistic reading: if all pairwise distances between $n$ random points concentrate around the same value $\sqrt{2d}$ , then "nearest neighbour" carries almost no information — the nearest and the farthest point are within a $1 \pm O(\sqrt{\log n/d})$ factor of each other. This is the precise version of the failure of local methods discussed on the nearest neighbours page.

The optimistic reading: if every geometric quantity is this predictable, then a random linear map preserves it, because there is nothing left to vary. That is Johnson–Lindenstrauss.

What this does not say

Neither reading is a theorem about real data. Both assume the points are drawn independently from an isotropic distribution. Real data typically lies near a low-dimensional structure, in which case the relevant dimension is the intrinsic one and the concentration is correspondingly weaker. When nearest-neighbour search works well on a nominally $768$ -dimensional embedding, it is because the data is not isotropic in $\R^{768}$ — and quantifying that gap is an open practical problem, not a solved one.

Problems

Concentration of the norm — the transfer stepProof · Advanced · 30 min How many nearly-orthogonal directions fit in R^d?Proof · Advanced · 30 min Volume concentrates near the boundaryNumerical · Beginner · 15 min Simulate the measure of a spherical capCoding · Intermediate · 30 min Distance contrast in high dimensionProof · Advanced · 1 hour

References

BookRoman Vershynin (2018). High-Dimensional Probability: An Introduction with Applications in Data ScienceChapter 3 covers random vectors in high dimension. The proofs below are written independently.
Lecture notesKeith Ball (1997). An Elementary Introduction to Modern Convex GeometryThe classical source for the volume and spherical-cap computations.
BookAvrim Blum, John Hopcroft and Ravindran Kannan (2020). Foundations of Data ScienceChapter 2 gives an accessible account of high-dimensional geometry.

These works are cited as sources to read, not reproduced. All exposition, examples and problems on this site are written independently; where an argument is standard, the citation points to a canonical treatment.

Results stated on this page

TheoremConcentration of the norm of a sub-Gaussian vectorproof includedFor a vector with independent sub-Gaussian coordinates, the norm deviates from the square root of the dimension by an O(1) sub-Gaussian amount.
PropositionThe expected norm of a Gaussian vectorproof includedThe mean of the norm is the square root of the dimension up to a 1/d correction, and the variance is bounded by a constant.
PropositionRandom directions are nearly orthogonalproof includedThe inner product of two independent uniform directions is of order one over the square root of the dimension.
TheoremMeasure concentration on the sphereproof includedA spherical cap at distance t from the equator carries at most exp(-d t^2 / 2) of the sphere's measure.
PropositionVolume concentrates in a thin shellproof includedAlmost all of the volume of a high-dimensional ball lies within O(1/d) of its boundary.
HeuristicThe curse and blessing of dimensionalityThe same concentration that destroys local methods is what makes random projections and dot-product retrieval work.

Experiments

The norm of a Gaussian vector
The distribution of ‖X‖₂ for X ~ N(0, I_d) as the dimension grows, against the √d prediction.

Problems (5)

All problems