# Bi-Hölder embeddings of finite metric spaces

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.

• 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?
– YCor
Jan 8 at 9:52
• Is this relevant? arxiv.org/abs/1811.03591 Jan 20 at 3:15

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