Low-dimensional L1 embedding of a finite metric space
= Low-dimensional L1 embedding of a finite metric space
{c}
{title2=$X\hookrightarrow\ell_1^{O(\log n)}$}
Every $n$-point metric space embeds into $\ell_1^{O(\log n)}$ with distortion $O(\log n)$. Apply the <Bourgain embedding theorem>, reduce its Euclidean dimension to $O(\log n)$ with the <Johnson–Lindenstrauss lemma>, and use an <Almost-isometric Gaussian embedding from l2 into l1>.