Suppose that $(X,\rho)$ is a compact doubling metric space. Does there necessarily exist an $\epsilon>0$ and a maximal $\epsilon$-net $\{x_i\}_{i=1}^n\subseteq X$ such that the map
$$
\begin{aligned}
\Phi:(X,\rho) & \rightarrow (\mathbb{R}^n,|\cdot|_2) \\
x&\mapsto \big(\rho(x,x_i)\big)_{i=1}^n
\end{aligned}
$$
is bi-Lipschitz? (A trivial upper-Lipschitz bound of $\sqrt{n}$ is clear but the lower-Lipschitz bound is far from obvious for me).
My question is rooted in the following observations.
Motivation/Intuition:
The motivation for my question is rooted in the following two observations.
-
The Assouad embedding theorem, see e.g. this paper for a recent formulation, shows that every doubling metric space admits a bi-Hölder embedding into a Euclidean space. Moreover, it is known that bi-Hölder is necessary, due to the global non-embeddability of the Heisenberg group, since the distortion of any closed ball diverges as the radius grows; this paper.
-
As remarked in this old MO post, in this paper of Katz and Katz (with un unpublished quantitative version found here) shows we know that there is a bi-Lipschitz embedding of any closed and connected Riemannian manifold $(M,g)$ into some Euclidean space $(\mathbb{R}^n,|\cdot|_2)$ given by
$$
\varphi:\,M\ni x\mapsto \big(\rho_g(x,x_i)\big)_{i=1}^n \in \mathbb{R}^n
$$
where $\{x_i\}_{i=1}^n$ is any maximal $\epsilon$-net for some sufficiently small $\epsilon>0$ and $\rho_g$ is the geodesic distance on $(M,g)$.
Clearly, compactness is needed here, since it is well-known that the hyperbolic plane cannot be bi-Lipschitz embedded into any Euclidean space. -
I comment that smoothness is not needed in (1) since the existence of $\Phi$ is obvious for any finite metric space.
Update:
Claim: Suppose that there exists some $0<\epsilon\le 1$ and a finite set $Y\subseteq X$ (depending on $\epsilon>0$) with the property that for every $x,z\in X$ there is some (possibly not unique) $y_{x,z}\in Y$ satisfying
$$
\epsilon \rho(x,z)\le |\rho(x,y_{x,z})-\rho(z,y_{x,z})|.
$$
Then, the map $\Phi(x)\mapsto (\rho(x,y))_{y\in Y}$ is a bi-Lipschitz embedding into the $|Y|$-dimensional Euclidean space.
Proof:
If this case, the finiteness of $Y$ implies that
$$
\epsilon \rho(x,z)\le |\rho(x,y_{x,z})-\rho(z,y_{x,z})|
\le \max_{y\in Y}\, |\rho(x,y)-\rho(z,y)|
\le \|\Phi(x)-\Phi(y)\|_2
\le |Y|^{1/2}\,\max_{y\in Y}\, |\rho(x,y)-\rho(z,y)| \le |Y|^{1/2}\rho(x,y)
$$
where I used the fact that $|Y|<\infty$ and $x\mapsto \rho(x,y)$ is $1$-Lipschitz for every $y\in Y$.
Updated Question:
So doesn't every $\epsilon$-packing do the trick and shouldn't any packing exist since packing numbers are upper-bounded by covering numbers, and in a doubling space all covering numbers are $O((\operatorname{diam}(X,\rho)\epsilon)^{-d})$ where $d$ is the doubling dimension of $(X,\rho)$ and $\operatorname{diam}(X,\rho)$ is its diameter?
In which case, why not take $\epsilon=1$? (Besides the fact that the distortion may be sub-optimal).
Thoughts: I guess the main challenge is to control the distortion and to show that one can get it to converge to $1$ as $\epsilon\downarrow 0$ (and this $n\uparrow \infty$ in general).
Best Answer
No. There are many compact, doubling metric spaces with no bi-Lipschitz embedding in a Hilbert space. Some examples: