Measure Concentration and Geometric Functional Analysis

Let $X \sim N(0, I_d)$ and $f: \mathbb{R}^d \to \mathbb{R}$ be $L$-Lipschitz. Then for all $t > 0$:

$P(|f(X) - \mathbb{E}[f(X)]| \geq t) \leq 2\exp\left(-\frac{t^2}{2L^2}\right)$

The function $f(X)$ is sub-Gaussian with parameter $L$.

Each coordinate of $X$ contributes independently to $f(X)$, and the Lipschitz condition limits how much each coordinate can influence the output. The $d$ independent contributions each have bounded effect, and their sum concentrates by the same mechanism as a sum of bounded random variables. The dimension $d$ does not appear in the bound.

This single result has enormous consequences. It implies that the norm $\|X\|$ concentrates around $\sqrt{d}$, inner products $\langle X, Y \rangle$ concentrate around 0, and random projections preserve distances. Most of high-dimensional probability follows from applying this inequality to appropriately chosen Lipschitz functions.

The result requires Gaussianity (or more generally, a distribution satisfying a log-Sobolev inequality). For heavy-tailed distributions, Lipschitz functions do not concentrate at the Gaussian rate. The bound also requires $f$ to be globally Lipschitz; local Lipschitz conditions are not sufficient.

For any set of $n$ points $x_1, \ldots, x_n \in \mathbb{R}^d$ and any $\epsilon \in (0, 1)$, there exists a linear map $A: \mathbb{R}^d \to \mathbb{R}^k$ with $k = O(\log n / \epsilon^2)$ such that for all pairs $i, j$:

$(1 - \epsilon)\|x_i - x_j\|^2 \leq \|Ax_i - Ax_j\|^2 \leq (1 + \epsilon)\|x_i - x_j\|^2$

The map $A = \frac{1}{\sqrt{k}} \Pi$ where $\Pi$ is a $k \times d$ matrix with i.i.d. $N(0,1)$ entries works with high probability.

A random projection of a vector $x$ has squared norm that concentrates around $\|x\|^2$. This is because $\|Ax\|^2 = \frac{1}{k}\sum_{j=1}^k (\pi_j^T x)^2$ where each $\pi_j^T x \sim N(0, \|x\|^2)$. The sum of $k$ squared Gaussians concentrates around its mean by chi-squared concentration. Taking a union bound over all $\binom{n}{2}$ pairs gives the result.

This lemma says that $n$ points in arbitrarily high dimension can be embedded into $O(\log n)$ dimensions while approximately preserving all pairwise distances. The target dimension depends only on $n$ and $\epsilon$, not on the original dimension $d$. This is the theoretical foundation for random projection methods in dimensionality reduction, approximate nearest neighbor search, and compressed sensing.

The $O(\log n / \epsilon^2)$ target dimension is tight: there exist point sets requiring $\Omega(\log n / \epsilon^2)$ dimensions for any linear map. For $\epsilon$ very small, the target dimension can still be large. The lemma also only preserves Euclidean distances; other metrics require different techniques.

Let $X$ be uniformly distributed on $S^{d-1}$ and $f: S^{d-1} \to \mathbb{R}$ be $L$-Lipschitz. Let $M_f$ be the median of $f(X)$. Then:

$P(|f(X) - M_f| \geq t) \leq 2\exp\left(-\frac{(d-1)t^2}{2L^2}\right)$

The concentration improves with dimension: higher dimension means tighter concentration.

On a high-dimensional sphere, most of the surface area is concentrated near any equator. A Lipschitz function cannot vary much on this concentrated strip. The effective number of "independent directions" on the sphere is $d-1$, which is why the exponent contains $d-1$.

Levy's lemma makes precise the idea that high-dimensional spheres are "effectively one-dimensional" from the perspective of Lipschitz functions. Any continuous measurement on a high-dimensional sphere will give nearly the same value for almost every point. This is a key ingredient in proofs of the Johnson-Lindenstrauss lemma via spherical projections.

The bound degrades for non-Lipschitz functions. For discontinuous functions or functions with large Lipschitz constant relative to the sphere's radius, the concentration is useless. Also, the bound is vacuous for $d = 1$ (the circle), where no concentration occurs.