Embedding from $L^\infty$ space to $L^2$ space

Question

I have a set $X$ of $n$ points in a $poly(n)$-dimensional $L^\infty$ space. Does there exist a way to map the points into $poly(n)$-dimensional $L^2$ space so that the distances between points in $X$ are approximately preserved?

Formally, let $S_1$ be the original $L^\infty$ space with $dim(S_1) = O(n^k)$ ($k$ is known and fixed), let $X$ be a subset of $S_1$ with $|X|=n$, and let $\epsilon \in (0,1)$ be some fixed number. Does there exist an $L^2$ space $S_2$ with $dim(S_2) = poly(n)$ and $\phi\colon S_1 \to S_2$ such that $\|\phi(x) - \phi(y)\|_2 = (1 \pm \epsilon) \|x-y\|_\infty$ for all $x,y \in X$?

Answer 1

The answer is unfortunately negative in general, by combining the following two well-known facts:

• Every metric space on $n$ points embeds isometrically into $(n-1)$-dimensional $L^\infty$.
• Embedding the metric of an $n$-vertex expander into $L_2$ requires distortion $\Omega(\log n)$.