Bourgain's Theorem for a Union of Euclidean Metric Spaces

Introduction

We consider the problem of embedding a union of Euclidean metric spaces into Euclidean space with low distortion. Formally, let $(X,d)$ be a metric space, such that $X$ is a union of $k$ sets $U_1,\ldots,U_k$ and each $U_i$ can be embedded isometrically into Euclidean space. Our goal is to find the smallest distortion $D_k$, such that the union $U_1\cup\cdots\cup U_k$ embeds into $\ell_2$ with distortion $D_k$. When every $U_i$ is a single point this is exactly the setting of Bourgain’s Theorem [4], which states that every $n$-point metric space can be embedded into Euclidean space with distortion $O(\log n)$. More generally, our question belongs to the study of local-global properties of metric embeddings initiated by Arora, Lovasz, Newman, Rabani, Rabinovich, and Vempala [1] (see also [6]), and asks whether the distortion of $X$ is governed only by $k$.

The special case $k=2$ was asked by Assaf Naor and settled by Makarychev and Makarychev [21], who showed that a union of two Euclidean sets embeds into $\ell_2$ with distortion at most 8.93. They then posed the problem for general $k$ as an open question [21 Question 6]. On one hand, iterating their result gives an upper bound of $D_k\le2^{O(k)}$. On the other hand, when each $U_i$ is a single point we have the classical lower bound of $D_k=\Omega(\log k)$ for Bourgain’s Theorem [19, 2].

In this work, we show that a union of $k$ Euclidean sets can be embedded into Euclidean space with distortion $D_k=O(k^{1.128}\log k)$, an exponential improvement over the previous bound, with no dependence on the number of points in $X$ or any $U_i$. Given the additional property that every $U_i$ stays Euclidean after adjoining any other two points from $X$, we can further establish that the distortion of embedding $X$ is $O(\log k)$, thus, matching the lower bound. Finally, if each $U_i$ remains Euclidean after adjoining any one other point from $X$, then we can obtain distortion of $O(k^{0.895}\log k)$.

Our approach contains two reductions that may be of independent interest. First, the distortion of a union of Euclidean sets is determined, up to an $O(\log k)$ factor, by how well Lipschitz maps on the individual sets extend to the whole space. Second, bounding these Lipschitz extension constants is equivalent to constructing good Euclidean metric sparsifiers.

Model and Main Results

Distortion. We say that a metric space $(X,d)$ embeds in $\ell_2$ with distortion $D$ if there is a function $f:X\to\ell_2$, such that for every $x,y\in X$:

Then, the distortion $c_2(X)$ of $(X,d)$ is the smallest such scalar $D$.

Euclidean Classes. In a metric space $(X,d)$, a subset $V\subseteq X$ is Euclidean in $X$ if it embeds isometrically into $\ell_2$. Moreover, we say a subset $V\subseteq X$ is $h$-strongly Euclidean in $X$ if, for every $h$-element subset $S\subseteq X$, the set $V\cup S$ embeds isometrically into $\ell_2$. That is, an $h$-strongly Euclidean set is a Euclidean set that remains Euclidean if we add $h$ arbitrarily chosen points.

The parameter $h$ interpolates between the condition that each $U_i$ is Euclidean ($h=0$) and that $X$ is Euclidean itself ($h=|X|$). In the spirit of local-to-global phenomena [1, 6], one can ask how large $h$ has to be before the distortion of $X$ becomes the optimal $\Theta(\log k)$. Our first main result shows that $h=2$ is already sufficient.

Observe that when each $U_i$ consists of a single point, Theorem 1.1 recovers Bourgain’s Theorem [4]. Because an $h$-strongly Euclidean set is 2-strongly Euclidean for every $h\ge2$, the same bound holds for unions of $h$-strongly Euclidean sets with $h\ge3$. Therefore, what remains are, indeed, only unions of Euclidean sets and unions of 1-strongly Euclidean sets. In the sections that follow we first develop the proof of Theorem 1.1, and later adapt what is useful to the Euclidean and 1-strongly Euclidean settings.

In the general case of a union of $k$ Euclidean sets we obtain the following subquadratic upper bound on the distortion.

For the case of 1-strongly Euclidean sets, we get the following sublinear distortion.

Technical Overview

Union of 2-strongly Euclidean sets. In § 2, we prove Theorem 1.1 in two steps:

1. For each $U_i$ we construct a $D$-terminal embedding, a 1-Lipschitz map $\varphi_i:X\to\ell_2$ that contracts distances between $U_i$ and every point of $X$ by at most a factor of $D$. This is where we use the 2-strongly Euclidean property of the sets $U_i$.

2. We combine the $k$ terminal embeddings into a single embedding for $X$. In the combined embedding, each point uses only the terminal embedding of the set closest to it, and we sample subcollections of the sets as in the algorithmic proof of Bourgain’s Theorem [19].

Overall, this yields an embedding of $X$ into $\ell_2$ with distortion $O(\log k)$. We note that our notion of terminal embedding is slightly different from the one considered by [8] because they do not require the maps to be Lipschitz on the whole space, as we do here.

From distortion to Lipschitz extension constants. Only the first step above depends on the sets being 2-strongly Euclidean, while combining terminal embeddings works for any union of Euclidean sets as long as each set admits a terminal embedding. In § 3, we show that any $L$-Lipschitz map $X\to\ell_2$ that does not contract distances on $U_i$ can be augmented into an $O(L)$-terminal embedding for $U_i$ (Lemma 3.1). So now the question becomes how well an isometry of $U_i$ extends to a Lipschitz map on all of $X$. This is captured by the Lipschitz extension constant $e(U_i)$, the least $\Lambda\ge1$ such that every Lipschitz map $f:(U_i,d)\to\ell_2$ extends to a Lipschitz map $F:(X,d)\to\ell_2$ with $\operatorname{Lip}(F)\le\Lambda\operatorname{Lip}(f)$. Indeed, since $U_i$ is Euclidean, by Kirszbraun’s Theorem [14] it suffices to extend an isometry of $U_i$ in order to bound $e(U_i)$. The formal result connecting distortion to Lipschitz extension constants is the following.

Lipschitz extension constants for Euclidean and 1-strongly Euclidean sets. In § 4, we bound the Lipschitz extension constants using metric sparsifiers [20]. Given a weighted graph $G$ on $X$ and a set of terminals $A\subseteq X$, a metric sparsifier of $G$ is a weighted graph $H$ on $A$ alone, such that for every metric $\rho$ on $A$ the cost of $H$ on $\rho$ approximates, up to a factor $Q$ called the quality, the least cost of $G$ over all extensions of $\rho$ to $X$. We take $A=U_i$ and measure cost by the quadratic energy $E_G(d^2)=\sum_{x<y}g_{xy}d(x,y)^2$, while only allowing extensions that are Euclidean on every $U_j$. In § 4.1, we show that in this setting the best sparsifier quality for every $G$ is exactly the square of the Lipschitz extension constant, where both quantities are taken uniformly over all metrics on $X$ that are Euclidean on every $U_j$ (Theorem 4.2). Bounding $e_{\max}$ thus reduces to constructing a good metric sparsifier.

The following upper bounds, combined with Theorem 1.4, give Theorems 1.2 and 1.3 for finite $X$. We take care of the finiteness assumption in Section C.

Lemma 1.5. Let $(X,d)$ be a finite metric space, such that $X=U_1\cup\cdots\cup U_k$. If each $U_i$ is Euclidean in $X$, then $e_{\max}=O(k^{1.128})$. If each $U_i$ is 1-strongly Euclidean in $X$, then $e_{\max}=O(k^{0.895})$.

In the construction for Lemma 1.5 we bound the quality of the canonical sparsifier for $U_i$ by adding the other sets back one at a time. We show that adding one Euclidean set costs a constant factor in the Lipschitz constant, and averaging the extensions over the set added last decreases the factor at the step with $r$ sets down to $1+\eta/r$ (Lemma 4.8). The product of these factors is $O(k^\eta)$, where the exponent $\eta$ is determined by the best trade-off between the growth on pairs of points inside the added set and on pairs crossing it, giving $\eta_0=1.1275\ldots<1.128$ for Euclidean sets and $\eta_1 = 0.8941\ldots< 0.895$ for 1-strongly Euclidean sets (§ 4.5). We leave the improved upper bound for the case $k = 2$ to Section B.

Lower bounds on Lipschitz extension constants. Theorem 1.4 bounds the distortion with the maximal Lipschitz extension constant $e_{\max}$ up to a factor of $O(\log k)$. Meanwhile, the analysis of Theorem 1.1 shows that $e_{\max}$ is an absolute constant for unions of 2-strongly Euclidean sets. What happens for unions of Euclidean sets, or of 1-strongly Euclidean sets? We find that the extension constant can be $\Omega(\sqrt{\log k})$ for some unions of Euclidean sets, and $\Omega(\sqrt[4]{\log k})$ for 1-strongly Euclidean. The lower bounds we obtain here do not improve on the general $\Omega(\log k)$ lower bound for distortion. They do show, however, that the reduction to Lipschitz extensions cannot by itself give $O(\log k)$ for unions of Euclidean sets.