A characterization of metric spaces admitting a bi-Lipschitz embedding into a Hilbert space?

Question

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?

Answer 1

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

Answer 2

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