8
$\begingroup$

Theorem (??) derived in this MO-post from Schoenberg's theorem yeilds a "bipartite" characterization of metric spaces that admit an isometric embedding into a Hilbert space. This Theorem (??) implies the following necessary condition of bi-Lipschitz embeddability into a Hilbert space.

Theorem. If a metric space $X$ admits a bi-Lipschitz embedding to a Hilbert space, then there exists a positive real constant $L$ such that the inequality $$\sum_{i<j}d^2(x_i^+,x_j^+)+\sum_{i<j}d^2(x_i^-,x_j^-)\le L\cdot \sum_{i,j}d^2(x_i^+,x_j^-)\quad\quad\quad(*)$$holds for any points $x_1^+,\dots,x_n^+,x_1^-,\dots,x_n^-\in X$.

Remark. The inequality $(*)$ in Theorem is not sufficient for the existence of a bi-Lipschitz embeding of $X$ to a Hilbert space. Indeed, the triangle inequality implies that for every metric $d$ on set $X$ the metric $\sqrt{d}$ satisfies the inequality $(*)$ with $L=2$. It is known that the unit ball $(B,d)$ of the Banach space $c_0$ does not admit a uniform embedding into a Hilbert space. Then the metric space $(B,\sqrt{d})$ satisfies the inequality $(*)$ (with $L=2$ but admits no bi-Lipschitz embedding to a Hilbert space.

Problem 1. Is there any nice geometric condition (or inequality) which is necessary and sufficient for the existence of a bi-Lipschitz embedding of a given metric space to a Hilbert space?

Problem 2. Is there a positive $\varepsilon$ such that each metric space $X$ satifying the inequality $(*)$ for $L=1+\varepsilon$ admits a bi-Lipschitz embedding to a Hilbert space?

$\endgroup$
  • $\begingroup$ So, as in your previous post, if (*) holds with L=1 then it is also a sufficient condition? In other words, is $\epsilon = 0$ a trivial answer to problem 2? $\endgroup$ – Behnam Esmayli Apr 17 '18 at 20:36
  • $\begingroup$ @BehnamEsmayli Yes, so I am asking about positive $\varepsilon$. $\endgroup$ – Taras Banakh Apr 18 '18 at 4:05
7
$\begingroup$

Schoenberg's criterion can be extended to bi-Lipschtiz embeddings. This is Corollary 3.5 in:

N. Linial, E. London, Y. Rabinovich, The geometry of graphs and some of its algorithmic applications. Combinatorica 15 (1995), no. 2, 215–245. (Also available here.) (MathSciNet review.)

$\endgroup$
  • $\begingroup$ "can be extended"... is a vague statement, and in any case this is just one possible extension. This is a criterion for existence of a embedding with some bound on the distortion. $\endgroup$ – YCor Apr 13 '18 at 14:56
  • $\begingroup$ @YCor Existence of an embedding with distortion $c\geq 1$ means existence of a bi-Lipschitz embedding $d(x,y)\geq |f(x)-f(y)|\geq c^{-1}d(x,y)$ into a Euclidean space. Corollary 3.5 provides a characterization in the case of finite metric spaces so it is a very good answer. $\endgroup$ – Piotr Hajlasz Apr 13 '18 at 15:12
  • $\begingroup$ @PiotrHajlasz I didn't say it's not a good answer, but (1) it would be a much better answer if it did more than quickly quoting a corollary (2) I'm suggesting that it's not "the" extension but "an" extension of Schoenberg's result. $\endgroup$ – YCor Apr 13 '18 at 15:40
  • 1
    $\begingroup$ @Manor-Mendel Thank your for your answer. I looked at Corollary 3.5 and see some resemblance with the inequality $(*)$. But Corollary 3.5 is more complicated comparing to Schoenberg characterization as instead of complex numbers $c_1,\dots,c_n$ it involves positive semidefinite matrices. Can this Corollary 3.5 reformulated in language of numbers $c_1,\dots,c_n$ (not matrices)? $\endgroup$ – Taras Banakh Apr 13 '18 at 16:24
  • 2
    $\begingroup$ @TarasBanakh. You are of course totally right, I was carried away. I deleted the additional incorrect characterization (which is equivalent to () above, as you mentioned). Incidentally, I think () is called "Enflo's generalized roundness", and it holds for any metric space with $L=2$ $\endgroup$ – Manor Mendel Apr 16 '18 at 1:28
4
$\begingroup$

One such characterization follows from Theorem 3.3 in my paper

Chávez-Domínguez, Javier Alejandro. Lipschitz factorization through subsets of Hilbert space. J. Math. Anal. Appl. 418 (2014), no. 1, 344–356. https://doi.org/10.1016/j.jmaa.2014.04.001 (Also available here).

which more generally characterizes maps between metric spaces which admit a Lipschitz factorization through a subset of a Hilbert space. For the particular case of interest here, the statement is as follows:

For a metric space $X$ and a constant $C \ge 1$, the following are equivalent:

  1. $X$ admits a bi-Lipschitz embedding into a Hilbert space with distortion $C$.
  2. Whenever $x_1,\dotsc,x_m, x'_1,\dotsc,x'_m$ and $y_1,\dotsc,y_n, y'_1,\dotsc,y'_n$ are points in $X$ and $\mu_1,\dotsc,\mu_m, \lambda_1,\dotsc,\lambda_n$ are real numbers satisfying the condition that for all Lipschitz functions $f:X \to \mathbb{R}$ one has $$\sum_{i=1}^n \lambda_i^2|f(y_i)-f(y'_i)|^2 \le \sum_{j=1}^m \mu_j^2|f(x_j)-f(x'_j)|^2,$$ it follows that $$\sum_{i=1}^n \lambda_i^2d(y_i,y'_i)^2 \le C^2 \sum_{j=1}^m \mu_j^2d(x_j,x'_j)^2.$$
$\endgroup$
  • $\begingroup$ Thank you for you answer. Replacing the real numbers $\lambda_i$, $\mu_j$ by rational numbers, then integer numbers and finally units, one can simplify your condition to the case $\lambda_i=\mu_j=1$ for all $i,j$. $\endgroup$ – Taras Banakh May 3 '18 at 3:43
  • $\begingroup$ How to check your condition 2 even on simlpest examples of 4-element metric spaces? $\endgroup$ – Taras Banakh May 3 '18 at 4:01
  • $\begingroup$ Lemma 3.2 in the paper gives an alternative characterization of the assumption in condition 2, although it involves matrices which is something you did not want. And even using that characterization, I must say that checking the condition on particular examples seems hard. $\endgroup$ – J. Alejandro Chávez-Domínguez May 7 '18 at 12:58

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.