Past exam of the mathematics course of the University of Cambridge / 2021 / iii / Paper 155 / 4

The Johnson–Lindenstrauss lemma says that for $0<\epsilon <1$, every set of $N$ points in a Hilbert space admits a linear map into ${\ell }_2^m$, where $m\le C{\epsilon }^{-2}\log N$, such that every pairwise distance is multiplied by a factor in $[1-\epsilon ,1+\epsilon ]$.

Let $S$ be a maximal $\delta$-separated subset of the unit sphere $S_E$. Maximality makes it a $\delta$-net. The translates $s+(\delta /2)B_E$, $s\in S$, have disjoint interiors and lie in $(1+\delta /2)B_E$. Comparing $n$-dimensional volumes givesso

Put $M=\Vert T\Vert$. For every $x\in S_E$, choose $s\in S$ with $\Vert x-s\Vert \le \delta$. Thenand taking the supremum givesThe reverse triangle inequality givesThus $T$ is injective and the net estimate for a linear operator yields

For a standard normal $Y$, completing the square givesWith $\beta =\sqrt{2/\pi }$, setNow $H(0)=H^{\prime }(0)=0$. Its second derivative is bounded above on $[0,1]$, so Taylor's theorem gives $H(u)\le C{u}^2$ there. For $u\ge 1$, the elementary bound $\Phi (u)\le 1$ givesThis proves the first subgaussian concentration of the absolute Gaussian average estimate. The second estimate is supplied in the question.

For fixed $x\ne 0$, rotational invariance of a Gaussian vector giveswhere the $Y_i$ are independent standard normals. HenceFor the upper tail, the Chernoff bound and the preceding moment estimate giveChoosing $u=\beta \delta /(2C)$ gives $e^{-c{\delta }^{2}k}$; the supplied negative-moment bound gives the same lower-tail estimate. Therefore

Fix $\epsilon >0$ and choose $0<\delta <1/3$ so thatTake a $\delta$-net of $S^{n-1}$ with at most $(3/\delta {)}^n$ points. If $k\ge C_{\epsilon }n$, the union bound and the concentration estimate show that with positive probability the random map satisfies the required inequalities simultaneously on the net. The net estimate then proves the Almost-isometric Gaussian embedding from l2 into l1 with distortion below $1+\epsilon$.

For the final claim, first apply the Bourgain embedding theorem to the given $n$-point metric space, obtaining distortion $O(\log n)$ in Euclidean dimension $O((\log n{)}^2)$. Apply the Johnson–Lindenstrauss lemma to its $n$ image points, reducing the dimension to $m=O(\log n)$ at constant additional distortion. Finally apply the preceding Gaussian construction with $k=O(m)=O(\log n)$. The composition proves the Low-dimensional L1 embedding of a finite metric space: