4
$\begingroup$

This is a reference request. There is a large body of work, I'm familiar with, that describes the existence of bi-Hölder embeddings of finite metric spaces into Euclidean space (such as this snowflaking business in Assouad's theorem).

My question is: Given a finite metric space $(X,d_X)$ are there known results outlining a (concrete) randomized algorithm for generating a bi-Hölder embedding of $f:(X,d_X)\rightarrow \ell_2^n$ into some suitably high-dimensional Euclidean space $\ell_2^n$ which can be computed in random-polynomial time (or better) and estimates of the Hölder coefficients $C$ and $\alpha$,i.e.: $$ C^{-1/\alpha}\|f^{-1}(x_1)-f^{-1}(x_2)\|^{1/\alpha}\leq d_X(x_1,x_2)\leq C\|f(x_1)-f(x_2)\|^{\alpha} $$

Note: There are of abstract existence results and characterizations for metric spaces for which this is possible, but here I look for something concrete and implementable.

$\endgroup$
2
  • $\begingroup$ You write Lipschitz in the title and Hölder in the main text. Also every embedding is bilipschitz (hence bihölder) so I expect you fix beforehand constants and the output should be with respect to these constants regardless of the input metric space? Or input both the metric space and the constants? $\endgroup$
    – YCor
    Jan 8, 2021 at 9:52
  • $\begingroup$ Is this relevant? arxiv.org/abs/1811.03591 $\endgroup$
    – Clement C.
    Jan 20, 2021 at 3:15

1 Answer 1

2
$\begingroup$

The thing about Assouad's theorem is that the distortion of the embedding provided depends on the metric dimension of the space aka the doubling constant. If you take a Hamming cube which is a set $\{0,1\}^n$ considered with $L_1$ metric and fix some $1/2 < a < 1$ then for any embedding $f:\{0,1\}^n \rightarrow L_2$ the following holds $$\sup_{x \neq y \in \{0,1\}^d} \frac{||f(x) - f(y)||}{d_X(x,y)^a}\sup_{x \neq y \in \{0,1\}^d} \frac{d_X(x,y)^a}{||f(x) - f(y)||} \ge C_1n^{C_2},$$ where $C_1=C_1(a) > 0, C_2=C_2(a) > 0$ are absolute constants depending only on $a$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.