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 at 9:52
  • $\begingroup$ Is this relevant? arxiv.org/abs/1811.03591 $\endgroup$
    – Clement C.
    Jan 20 at 3:15
1
$\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, privacy policy and cookie policy

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