the Johnson-Lindenstrauss lemma

The Johnson-Lindenstrauss lemma is the theoretical license for dimensionality reduction: it says that any finite set of points in a high-dimensional Euclidean space can be mapped into a space of dimension only logarithmic in the number of points, by a simple random linear map, while preserving all pairwise distances up to a small relative error. It is why algorithms can compress data from thousands of dimensions to dozens with provable, distance-preserving guarantees, and it is the cleanest application of the concentration of the norm.

The statement: for any set of N points x_1, ..., x_N in R^d and any tolerance eps in (0, 1), there is a linear map f: R^d -> R^k with target dimension k = O(eps^(-2) log N) such that for every pair, (1 - eps) ||x_i - x_j||^2 <= ||f(x_i) - f(x_j)||^2 <= (1 + eps) ||x_i - x_j||^2. The target dimension k depends only on N and eps — NOT on the original dimension d. The proof is pure concentration. Take f(x) = (1/sqrt(k)) G x where G is a k-by-d matrix of independent N(0,1) entries (or Rademacher, or sparse). For any fixed vector u, ||f(u)||^2 / ||u||^2 is an average of k independent squared standard Gaussians, a chi-squared/k variable with mean 1, which by Bernstein concentrates around 1 with P(distortion > eps) <= 2 exp(-c k eps^2). Choosing k ~ eps^(-2) log N makes this failure probability smaller than 1/N^2, and a union bound over the binom(N, 2) pairwise difference vectors guarantees all distances are preserved simultaneously with positive probability — so such a map exists (indeed a random one works with high probability).

JL is the foundation of randomized numerical linear algebra, sketching, locality-sensitive hashing, and fast approximate nearest neighbours; it makes random projection a principled preprocessing step rather than a heuristic. The honest caveats are sharp and important. First, the log N dependence is essentially optimal (Larsen-Nelson lower bound), so you cannot beat O(eps^(-2) log N) in general. Second, JL preserves PAIRWISE distances among a FIXED finite set, not the norm of every vector in a subspace — preserving an entire subspace requires the stronger subspace-embedding / restricted-isometry property, with k scaling in the subspace dimension. Third, the guarantee is on squared distances up to (1 +/- eps); it does not preserve angles or inner products to the same fidelity without restating the bound, and it does not preserve non-Euclidean (e.g. L_1) distances — there is no JL lemma for L_1.