Bi-Hölder embeddings of finite metric spaces

Question

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.

Answer 1

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