The Johnson-Lindenstrauss Lemma [1]} was one of the first examples to exhibit this general phenomenon. It states that a subset \(T\)  of a Hilbert space, that is of cardinality \(n\) , can be embedded in \(\ell _2^m\)  for \(m=c(\varepsilon )\log n\) , with the embedding distorting mutual distances between all pairs of points in \(T\)  by at most a multiplicative factor of \(1 \pm \varepsilon \) . Moreover, the embedding is random—in the original proof of the Johnson-Lindenstrauss Lemma the embedding was a normalized orthogonal projection onto a subspace selected according to the Haar measure on a Grassmann manifold of the right dimension. That choice of a random embedding is by no means unique, and over the years many different random ensembles have been shown to be, with high probability, embeddings that satisfy the Johnson-Lindenstrauss Lemma.
