1
$\begingroup$

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$?

$\endgroup$

1 Answer 1

3
$\begingroup$

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)$.
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.