Fréchet embeddings of negative type metrics

Sanjeev Arora^{∗}  James R. Lee^{†}  Assaf Naor ^{‡}

Abstract We show that every n-point metric of negative type (in particular, every n-point subset of L_{1}) admits a Fréchet embedding into Euclidean space with distortion O (\sqrt{log n} · log log n), a result which is tight up to the O(log log n) factor, even for Euclidean metrics. This strengthens our recent work on the Euclidean distortion of metrics of negative into Euclidean space.

1 Introduction

Let (X, d_{X}) and (Y_{,}d_{Y}) be finite metric spaces. Given an injection f : X ↪ Y, the distortion of f is defined as:

dist(f) ∥f∥_{Lip} · ∥f^{−1}∥_{Lip} = sup_{\begin{matrix}x,y∈X \\ x≠Y \end{matrix}} \frac{d_{Y} (f(x), f(y))}{d_{X}(x, y)} · sup_{\begin{matrix}x,y∈X \\ x≠Y \end{matrix}} \frac{d_{X}(x, y)}{d_{Y} (f(x), f(y))}.

The least distortion with which X may be embedded into Y is denoted by c_{Y} (X), i.e.

c_{Y} (X) inf{dist(f) : f : X ↪ Y }.

For p ≥ 1 we also use the notation c_{p}(X) c_{L_{p}}(X). The parameter c_{2}(X) is called the Euclidean distortion of X.

Bourgain’s fundamental embedding theorem [6] states that:

|X| = n ⟹ c_{2}(X) = O(log n).  (1)

But, Bourgain’s proof of (1) contains more information. A Fréchet embedding of (X, d_{X}) is a probability distribution μ over all non-empty subsets of X. If A is a random subset distributed according to μ, then we associate, to every x ∈ X, the real-valued random variable F_{μ}(x) = d(x, A).

Thus, for every x, y ∈ X and every p > 0,

∥F_{μ}(x) − F_{μ}(y)∥_{p} = (𝔼_{μ} |d_{X}(x, A) − d_{X}(y, A)|^{p})^{1/p} .

In [6] Bourgain constructs a Fréchet embedding μ such that for every x, y ∈ X,

∥F_{μ}(x) − F_{μ}(y)∥_{∞} ≤ d_{X}(x, y) ≤ O(log n) · ∥F_{μ}(x) − F_{μ}(y)∥_{1}.  (2)

∗Supported by David and Lucile Packard Fellowship and NSF grant CCR-0205594. Princeton University.

arora@cs.princeton.edu

†Supported by NSF grant CCR-0121555 and an NSF Graduate Research Fellowship. U. C. Berkeley.

jrl@cs.berkeley.edu

‡Microsoft Research. anaor@microsoft.com

Observe that (2) implies (1), and that the left-hand inequality in (2) holds automatically, since by the triangle inequality, the mapping F_{μ} is pointwise 1-Lipschitz. This fundamental property of Bourgain’s embedding is crucial for certain applications—for example it is used in the design of approximation algorithms for vertex separators [9]. From an analytic point of view, the “mixed norm” inequality (2) is natural since it can be viewed as a (non-linear) Dvoretzky-Rogers type embedding (see [8, 10]).

Unfortunately, it isn’t always possible to construct Fréchet embeddings. For example, in [16] it is shown that if N is a 1/\sqrt{d} net on the unit d-dimensional Euclidean sphere, then for every Fréchet embedding F_{μ} : N → L_{2}(μ),

dist(F_{μ}) = Ω (\sqrt{d}) = Ω (\sqrt{\frac{log |N |}{log log |N |}}) .

Thus, we cannot expect to have a Fréchet embedding for any n-point Euclidean metric with Euclidean distortion significantly better than \sqrt{log n}. In the context of metric Ramsey (non-linear Dvoretzky) embeddings [5], it was shown in [4] that Fréchet embeddings cannot be used to obtain the results of [5] (we refer to these papers for more details). In [17] it was shown that any n-point weighted planar graph (equipped with the shortest-path metric) embeds into L_{2} with distortion O (\sqrt{log n}). The embedding of [17] is not a Fréchet embedding, and it required significantly more work to prove in [13] that Fréchet embeddings exist with the same distortion guarantee.

Recall that (X, d_{X}) is said to be a metric space of negative type if the metric space (X, \sqrt{d_{X}}) embeds isometrically into Euclidean space. The space L_{1} has negative type, and metrics of negative type also occur as relaxations of certain semidefinite programs (see e.g. [11]). It is known [12] that there are metrics of negative type that require arbitrarily large distortion in any embedding into L_{1}. In [1] the present authors proved that if (X, d_{X}) is an n-point metric space of negative type then c_{2}(X) = O (\sqrt{log n} · log log n). This result is optimal up to the iterated logarithm, and is used in [1] to obtain the best know approximation algorithm for the Sparsest Cut problem with general demands (see the discussion in [1] for background on this topic). On the other hand, the best known bound for Fréchet embeddings of negative type metrics is O(log n)^{3/4} [7].

The embedding of [1] is not a Fréchet embedding. The argument of [1] is modular and general, as it presents a gluing technique for certain ensembles of Lipschitz mappings. The resulting “glued” mapping is not Fréchet, even if the original ensemble consists of Fréchet embeddings. While this general gluing procedure is of independent interest, it is natural to ask whether it is also possible to obtain a Fréchet embedding with the same distortion guarantee. In this paper we show that this is indeed the case, by proving the following theorem

Theorem 1.1. Let (X, d_{X}) be an n-point metric space of negative type. Then there exists a probability measure μ over random subsets ∅ ≠ A ⊆ X such that for every x, y ∈ X,

(𝔼_{μ} |d(x, A) − d(y, A)|^{2})^{1/2} = Ω (\frac{d_{X}(x, y)}{\sqrt{log n} · log log n}) .

We remark that this bound is new even for the special case when X is an n-point submetric of some Euclidean space. The proof of Theorem 1.1 is different, and substantially more involved than the proof in [1]. We believe that it is worthwhile to establish that Fréchet embeddings are achievable in this case. Such maps are interesting due to the algorithmic and combinatorial applications of Fréchet embeddings in [9], in addition to the new structural information contained in Theorem 1.1. Moreover, the proof techniques used here are different than in [1], and are independently interesting.

We end this introduction by stating some interesting open problems related to Fréchet embeddings. Our result suggests (together with the results of [13]) that Fréchet embeddings may be universal for large enough distortions. More precisely, we have the following question.

Question 1. Does every n-point metric space (X, d_{X}) admits a Fréchet embedding into L_{2} with distortion O (max\{c_{2}(X), \sqrt{log n}\})?

Observe that \sqrt{log n} is a natural barrier here due to the result of [16]. If this (speculative) bound is indeed true, then it would yield a method of producing good Fréchet embeddings from general embeddings (and it would show that Theorem 1.1 follows from [1]).

Finally, it is not known whether every n-point metric of negative type admits a Fréchet embedding as in the statement of Theorem 1.1 with the 2-norm replaced by the 1-norm.

Question 2. Does every n-point metric space of negative type admit a Fréchet embedding into L_{1} with distortion O(\sqrt{log n} log log n)?

If true, this would yield the best known approximation algorithm for the minimum-weight vertex separator problem (see [9]). In fact, the best upper bound known to hold is Bourgain’s bound of O(log n). This question is open even for the shortest-path metrics of planar graphs, and its resolution has implications for the theory of vertex-capacitated flows in such families.

2 Preliminaries

We recall the following definition from [1]. Let (X, d) be an n-point metric space.

Definition 2.1 (Random zero-sets). Given Δ, ζ > 0, and p ∈ (0, 1) we say that X admits a random zero set at scale Δ which is ζ-spreading with probability p if there is a distribution μ over subsets Z ⊆ X such that for every x, y ∈ X with d(x, y) ≥ Δ,

μ \{Z ⊆ X : y ∈ Z and d(x, Z) ≥ \frac{Δ}{ζ}\} ≥ p.

We denote by ζ(X; p) the least ζ > 0 such that for every Δ > 0, X admits a random zero set at scale Δ which is ζ-spreading with probability p. Finally, given k ≤ n we define

ζ_{k}(X; p) = max_{\begin{matrix}Y ⊆X \\ |Y |≤k \end{matrix}} ζ(Y; p).

As noted in [1], a concatenation of the results of [2], [14], and [7], shows that there exists a universal constant p ∈ (0, 1) such that for every n-point metric space (X, d) of negative type, ζ(X; p) = O (\sqrt{log n}).

We now recall the related notion of padded decomposability. Given a partition P of X and x ∈ X we denote by P (x) ∈ P the unique element of P to which x belongs. In what follows we sometimes refer to P (x) as the cluster of x. Following [13] we define the modulus of padded decomposability of X, denoted α_{X}, as the least constant α > 0 such that for every Δ > 0 there is a distribution ν over partitions of X with the following properties.

1. For all P ∈ supp(ν) and all C ∈ P we have that diam(C) < Δ.

2. For every x ∈ X we have that

ν\{P : B(x, Δ/α) ⊆ P (x)\} ≥ \frac{1}{2}.

As observed in [13], the results of [15, 3] imply that α_{X} = O(log |X|), and this will be used in our proof. Moreover, it is shown in [1] (motivated by an argument in [17]) that it is always the case that ζ(X; 1/8) ≤ α_{X}.

We conclude this section with the following elementary probabilistic lemma.

Lemma 2.2 (Sampling lemma). Suppose that k, n ∈ ℕ, 1 ≤ k ≤ n. Let X be an n-point set and let X̃_{k} be chosen uniformly at random from all k-point subsets of X. Then

1. For every A ⊆ X, Pr[X̃_{k} ∩ A = ∅] ≤ e^{−k|A|/n}.

2. For every A, B ⊆ X such that A ∩ B = ∅,

(a) Pr[X̃_{k} ∩ A = ∅ | X̃_{k} ∩ B ≠ ∅] ≤ Pr[X̃_{k−1} ∩ A = ∅] ≤ e^{(1−k)|A|/n}

(b) Pr[X̃_{k} ∩ A = ∅ | X̃_{k} ∩ B = ∅] ≤ e^{−k|A|/n}.

Proof. The proof of (1) is an easy calculation. To prove 2(a), note that choosing X̃_{k} uniformly subject to X̃_{k} ∩ B ≠ ∅ is the same as first choosing z ∈ B uniformly at random, then choosing a uniform k − 1 point subset S ⊆ X \ {z} and returning S ∪ {z}.

3 Proof of Theorem 1.1

The main technical result of this paper is contained in the following lemma.

Lemma 3.1 (Enhanced descent). Let (X, d) be an n-point metric space and fix p ≤ 1/8, K ≥ 2 and ζ ≥ ζ_{K}(X; p). For every m ∈ ℤ, define

S_{m}(K) = \{x ∈ X : |B (x, 2^{m+5}α_{X})| ≤ \frac{K}{16} · |B (x, \frac{2^{m−9}}{ζ} )|\} .

Then there exists a distribution σ over random subsets A ⊆ X such that for all m ∈ ℤ, x ∈ S_{m}(K) and y ∈ X with d(x, y) ∈ [2^{m−1}, 2^{m}],

𝔼_{σ}|d(x, A) − d(y, A)|^{2} ≥ \frac{p^{5}}{O(log n log log n)} · \frac{d(x, y)^{2}}{ζ^{2}} · log \frac{|B(x, 2^{m+5}α_{X})|}{|B(x, 2^{m+3}/ζ)|}.  (3)

Before proving Lemma 3.1 we show how it implies Theorem 1.1. The argument below actually yields more general results. For example if we assume that ζ_{k}(X; p) = O(log k)^{θ} for some p ∈ (0, 1/8), θ ≥ \frac{1}{2} and all k ≤ n then we achieve a Fréchet embedding which achieves

c_{2}(X) = O_{p} ((log n)^{θ}\sqrt{log α_{X} log log n}) = O_{p} ((log n)^{θ} log log n) ,

where O_{p}(·) may contain an implicit constant which depends only on p.

Proof of Lemma 3.1 ⟹ Theorem 1.1. As noted above, there exists a universal constant p ∈ (0, 1) such that for every metric space (Y, d) of negative type, ζ(Y; p) = O (\sqrt{log |Y |}). Combining this with Lemma 3.1 and the fact that α_{X} = O(log n) we obtain the following statement. There exists a constant C > 0 such that for every K ≥ 2 there exists a distribution μ_{K} over random subsets A_{K} ⊆ X satisfying the following condition. Define

S′_{m}(K) = \{u ∈ X : |B (u, 2^{m+5}α_{X})| ≤ K · |B (u, \frac{2^{m}}{C\sqrt{log K}} )|\} .

Then for all m ∈ ℤ, x ∈ S′_{m}(K) and y ∈ X such that d(x, y) ∈ [2^{m−1}, 2^{m}],

𝔼_{μ_{K}} |d(x, A_{K}) − d(y, A_{K})|^{2} ≥ \frac{d(x, y)^{2}}{C log K log n log log n} · log \frac{|B(x, 2^{m+5}α_{X})|}{|B(x, C2^{m}/\sqrt{log K})|}.

Observe that for every m ∈ ℤ, S′_{m}(n) = X. Hence, defining K_{0} = n and K_{j+1} = K_{j}^{1/C^{4}}, as long as K_{j} ≥ 2, we obtain random subsets U_{0}, U_{1}, …, U_{j} ⊆ X (where U_{j} = A_{K_{j}}) satisfying, for all x ∈ S_{m}(K_{j}) \ S_{m}(K_{j+1}) and y ∈ X such that d(x, y) ∈ [2^{m−1}, 2^{m}],

𝔼 |d(x, U_{j}) − d(y, U_{j})|^{2} ≥ \frac{d(x, y)^{2}}{C log K_{j} log n log log n} · log \frac{|B(x, 2^{m+5}α_{X})|}{|B(x, C2^{m}/\sqrt{log K_{j}})|}
= \frac{d(x, y)^{2}}{C log K_{j} log n log log n} · log \frac{|B(x, 2^{m+5}α_{X})|}{|B (x, C2^{m}/\sqrt{log K_{j+1}^{C^{4}}})|}

= \frac{d(x, y)^{2}}{C log K_{j} log n log log n} · log \frac{|B(x, 2^{m+5}α_{X})|}{|B(x, 2^{m}/(C\sqrt{log K_{j+1}}))|}
≥ \frac{d(x, y)^{2}}{C log K_{j} log n log log n} · log K_{j+1} = \frac{d(x, y)^{2}}{C^{5} log n log log n}.

This procedure ends after N steps, where N ≤ \frac{log log n}{log C}. Every x ∈ S_{m}(K_{N}) satisfies

|B(x, 2^{m+5}α_{X})| ≤ 2^{C^{4}}|B(x, 2^{m+1}/C)|.

By a result of [13] (for a simple proof, see [1, Claim 4.6]) there is a distribution over random subsets U_{N+1} ⊆ X such that for every x, y ∈ S_{m}(K_{N}),

𝔼 |d(x, U_{N+1}) − d(y, U_{N+1})|^{2} ≥ \frac{d(x, y)^{2}}{O(log n)}.

Now consider the distribution μ over random subsets U ⊆ X, defined as follows. First, pick a value j ∈ {0, 1, …, N +1} uniformly at random, then choose a random subset from the distribution of U_{j}. For every x, y ∈ X choose m ∈ ℤ such that d(x, y) ∈ [2^{m−1}, 2^{m}]. If x, y ∈ S_{m}(K_{N}) then

𝔼_{μ} |d(x, U) − d(y, U)|^{2} ≥ \frac{𝔼 |d(x, U_{N+1}) − d(y, U_{N+1})|^{2}}{N + 1} ≥ \frac{d(x, y)^{2}}{O(N log n)}.

Otherwise, there is j ∈ {0, …, N − 1} such that x ∈ S_{m}(K_{j}) \ S_{m}(K_{j+1}), in which case

𝔼_{μ} |d(x, U) − d(y, U)|^{2} ≥ \frac{𝔼 |d(x, U_{j+1}) − d(y, U_{j+1})|^{2}}{N + 1} ≥ \frac{d(x, y)^{2}}{O(N log n log log n)}.

Recalling that N = O(log log n) completes the proof.

3.1 Proof of Lemma 3.1: Enhanced descent

We begin with a simple definition.

Definition 3.2. For every x ∈ X and t > 0 define

κ(x, t) = max{κ ∈ ℤ : |B(x, 2^{κ})| < 2^{t}}.  (4)

The following simple lemma says that the values of κ(·, ·) cannot change too rapidly when moving between nearby points. This fact will be used several times in the ensuing arguments, and played a similar role in [13].

Lemma 3.3 (Smoothness). For x ∈ X, let i ∈ ℤ and m, t ∈ ℤ^{+} be such that |B(x, 2^{i+m−1})| ≤ 2^{t} ≤ |B(x, 2^{i+m})|. Then every z ∈ X for which d(x, z) ≤ 2^{min{m,m+i−2}} satisfies:

κ(z, t) ∈ {m + i − 3, m + i − 2, m + i − 1, m + i, m + i + 1}.

Proof. By definition,

|B(z, 2^{κ(z,t)})| < 2^{t} ≤ |B(x, 2^{κ(z,t)+1})|.

For the upper bound, we have

|B(x, 2^{κ(z,t)} − 2^{m−s})| ≤ |B(z, 2^{κ(z,t)})| < 2^{t} ≤ |B(x, 2^{i+m})|,

implying that 2^{κ(z,t)} − 2^{m−s} < 2^{i+m}, which yields 2^{κ(z,t)} < 2^{m+1+i}. For the lower bound, we have

|B(x, 2^{κ(z,t)+1} + 2^{m−s})| ≥ |B(z, 2^{κ(z,t)+1})| ≥ 2^{t} ≥ |B(x, 2^{m+i−1})|.

We conclude that 2^{κ(z,t)+1} + 2^{m−s} ≥ 2^{m+i−1}, which implies that 2^{κ(z,t)+1} ≥ 2^{m+i−2}.

Notation. We introduce some notation which will be used in the forthcoming proofs. Write α = α_{X}, and for every j ∈ ℤ let P_{j} denote a random partition of X satisfying the following.

1. For all C ∈ P_{j} we have that diam(C) ≤ 2^{j+4}α.

2. For every x ∈ X we have that ν\{P : B(x, 2^{j+4}) ⊆ P_{j}(x)\} ≥ \frac{1}{2}.

We also fix p ∈ (0, 1/8) and for every k ≤ n let ζ_{k} = ζ_{k}(X; p). For S ⊆ X let Ψ_{j}(S) denote a random zero set of S at scale 2^{j−3} which is ζ_{|S|}-spreading with probability p. For each C ⊆ X let C̃ be a uniformly random subset of C of size min{K, |C|}.

The Fréchet-type embeddings. The embeddings we produce will be of Fréchet-type, i.e. every coordinate f_{i} : X → ℝ will be of the form f_{i}(x) = d(x, U) for some U ⊆ X. Let I = [− log_{2} ζ_{K} + 3, log_{2} α + 6] ∩ ℤ and J = {0, 1, …, ⌈log_{2} n⌉}. For each i ∈ I and t ∈ J, we describe a distribution W_{t}^{i} on sets. Our random embedding consists of mapping x to f(x) = (d(x, W_{t}^{i}) : i ∈ I, t ∈ J). Such a mapping is clearly Lipschitz with constant \sqrt{|I| · |J|} = O(\sqrt{log n · log α}) (here we use the fact that ζ_{K} ≤ α).

Let {σ_{m}}_{m∈ℤ} be a sequence of random variables taking each of the values {0, 1, 2} with probability \frac{1}{3}, which are independent of all the other random variables appearing in this proof. (In general, the reader should assume that samplings from various distributions are independent of one another.) We define the random subset W_{t}^{i} as follows.

x ∈ W_{t}^{i} ⟺ \begin{cases}x ∈ X & if σ_{κ(x,t)−i} = 0, \\ x ∈ Ψ_{κ(x,t)−i} \binom{}{P_{κ(x,t)−i}(x)} & if σ_{κ(x,t)−i} = 1, \\ x ∈ { \atop P_{κ(x,t)−i}(x)} & if σ_{κ(x,t)−i} = 2. \end{cases}

For the rest of the proof, let m be any integer, fix x, y ∈ X such that d(x, y) ∈ [2^{m−1}, 2^{m}], and assume that x ∈ S_{m}(K). Let s_{i} = log_{2} |B(x, 2^{i+m})|, with s_{min I} and s_{max I} corresponding to the smallest and largest i ∈ I. The next claim follows from the “smoothness” of Lemma 3.3.

Claim 3.4. For i ∈ I and all t ∈ ℤ ∩ [s_{i−1}, s_{i}], every w ∈ B(x, 2^{m}/ζ_{K}) satisfies

m − 3 ≤ κ(w, t) − i ≤ m + 1.

Now we define

N(x) |{(i, t) : i ∈ I, t ∈ [s_{i−1}, s_{i}] ∩ ℤ}| = |{t : t ∈ [s_{min I}, s_{max I}] ∩ ℤ}|.

Observe that

N(x) ≥ log_{2} \frac{|B(x, 2^{m+5}α)|}{|B(x, 2^{m+3}/ζ_{K})|}.

We are going to get a contribution to ||f(x) − f(y)||_{2}^{2} from the sets {W_{t}^{i}} where t ∈ ℤ ∩ [s_{i−1}, s_{i}] for some i ∈ I. The number of such pairs is N(x). Thus clearly we get the desired lower bound (3) if we can prove that for these values of i and t, we have

𝔼 |d(x, W_{t}^{i}) − d(y, W_{t}^{i})|^{2} ≥ (\frac{p}{64})^{5} · \frac{2^{2m}}{ζ_{K}} .  (5)

To prove (5) we fix i ∈ I, t ∈ [s_{i−1}, s_{i}] ∩ ℤ and let

M = {m − 3, m − 2, m − 1, m, m + 1}

be the range of values from Claim 3.4.

3.1.1 Partitions and padding

For any j ∈ M we have that diam(P_{j}(x)) ≤ 2^{j+4}α ≤ 2^{m+5}α, so B(x, 2^{m+5}α) ⊇ P_{j}(x). Since x ∈ S_{m}(K), it follows that |P_{j}(x)| ≤ \frac{K}{16}|B(x, 2^{m−9}/ζ_{K})|. Recall that for j ∈ M the random partition P_{j} satisfies

Pr[d(x, X \ P_{j}(x)) ≥ 2^{m+1}] ≥ Pr[d(x, X \ P_{j}(x) ≥ 2^{j+4}] ≥ \frac{1}{2}.

Define the event

E_{pad}^{j} = {d(x, X \ P_{j}(x)) ≥ 2^{m+1}},

and let

E_{pad} = ⋂_{j∈M} E_{pad}^{j}.

Note that, by independence, we have Pr[E_{pad}] ≥ 2^{−5}.

Suppose that E_{pad}^{j} occurs, then since d(x, y) ≤ 2^{m}, we have y ∈ P_{j}(x), implying P_{j}(x) = P_{y}(x). Furthermore, since

B(x, 2^{m−9}/ζ_{K}) ⊆ P_{j}(x),

when we sample down P_{j}(x) to { \atop P_{j}(x)}, a set of size at most K, Lemma 2.2, part (1), ensures that

Pr[{ \atop P_{j}(x)} ∩ B(x, 2^{m−9}/ζ_{K}) = ∅] ≤ e^{−15}.

To this end, we denote

E_{hit}^{j} = \{{ \atop P_{j}(x)} ∩ B(x, 2^{m−9}/ζ_{K}) ≠ ∅\} ,

and we define E_{hit} = ⋂_{j∈M} E_{hit}^{j}. Since the events {E_{hit}^{j}}_{j∈M} are independent even after conditioning on E_{pad}, the preceding discussion yields the following lemma.

Lemma 3.5. Pr (E_{hit} ∩ E_{pad}) ≥ 2^{−5}(1 − 5e^{−15}) > 2^{−6}.

3.1.2 Obtaining a separation

We introduce the following events which mark different “phases” of the embedding. For ℓ ∈ {1, 2}, let

E_{ℓ}^{σ} = {σ_{j} = ℓ for all j ∈ M} .

Note that Pr[E_{ℓ}^{σ}] ≥ 3^{−5} for each ℓ ∈ {1, 2}. Now we study the distance from x to W_{t}^{i} in phase 1.

Claim 3.6. If E_{1}^{σ} ∩ E_{pad} occurs, then

d(x, W_{t}^{i}) ≥ min \{\frac{2^{m}}{ζ_{K}} , min_{j∈M} \{d(x, Ψ_{j}({ \atop P_{j}(x)}))\}\} .  (6)

Proof. Fix a point w ∈ B(x, 2^{m}/ζ_{K}), and let j = κ(w, t) − i. By Claim 3.4, j ∈ M, hence E_{pad} implies that w ∈ P_{j}(x). Since E_{1}^{σ} occurs, we have w ∈ W_{t}^{i} if and only if w ∈ Ψ_{j}({ \atop P_{j}(x)}).

If E_{pad} ∩ E_{hit} occurs, then for each j ∈ M, there exists a point w_{j} ∈ { \atop P_{j}(x)} such that d(x, w_{j}) ≤ 2^{m−9}/ζ_{K}. So to get a lower bound on d(x, W_{t}^{i}), we can restrict our attention to {w_{j}}_{j∈M}.

Claim 3.7. If E_{hit} ∩ E_{pad} ∩ E_{1}^{σ} occurs and

d (w_{j}, Ψ_{j} \binom{}{P_{j}(x)}) ≥ ε

for every j ∈ M, then

d(x, W_{i}^{t}) ≥ min \{\frac{2^{m}}{ζ_{K}} , ε − \frac{2^{m−9}}{ζ_{K}} \} .

Proof. For every j ∈ M,

d (x, Ψ_{j} \binom{}{P_{j}(x)}) ≥ d (w_{j}, Ψ_{j} \binom{}{P_{j}(x)}) − d(x, w_{j}) ≥ ε − \frac{2^{m−9}}{ζ_{K}} .

Now apply Claim 3.6.

There are two types of points y ∈ X which occur in the argument that follows. As a warmup, we first dispense with the easy type.

Type I: There exists z ∈ B(y, 2^{m−7}/ζ_{K}) for which κ(z, t) − i ∉ M.

Fix this z and let j′ = κ(z, t) − i. Assume that E_{hit} ∩ E_{pad} ∩ E_{1}^{σ} occurs, as well as the independent event σ_{j′} = 0. Note that using Lemma 3.5 along with independence, the probability of this event is at least q = 2^{−6} · 3^{−5} · (1/3).

Now, applying the definition of ζ_{K} to the sets { \atop P_{j}(x)} = { \atop P_{j}(w_{j})} for j ∈ M, we conclude that there is an event E_{zero} which occurs with probability at least p^{5}, and such that for every j ∈ M,

d (w_{j}, Ψ_{j} \binom{}{P_{j}(x)}) ≥ \frac{2^{j−3}}{ζ_{K}} ≥ \frac{2^{m−6}}{ζ_{K}} .

Applying Claim 3.7 with ε = 2^{m−6}/ζ_{K}, we conclude that, in this case,

d(x, W_{t}^{i}) ≥ \frac{5 · 2^{m−9}}{ζ_{K}} .

Since σ_{j′} = 0, we have z ∈ W_{t}^{i}, hence with probability at least q · p^{5} ≥ (p/16)^{5}, we have

|d(x, W_{t}^{i}) − d(y, W_{t}^{i})| ≥ \frac{5 · 2^{m−9}}{ζ_{K}} − d(y, z) ≥ \frac{2^{m−9}}{ζ_{K}} .

This completes the analysis of Type I points.

3.1.3 A case analysis on the fate of y

We now analyze the complement of the set of Type I points.

Type II: For all z ∈ B(y, 2^{m−7}/ζ_{K}), κ(z, t) − i ∈ M.

First, we define the following key event.

E_{close} = \{∃j ∈ M, ∃z ∈ { \atop P_{j}(y)} such that d(y, z) ≤ \frac{2^{m−7}}{ζ_{K}} and κ(z, t) − i = j\} .  (7)

Also, let E_{far} = ¬E_{close}.

These two events concern the distance of y to the various sample sets. Since we do not make the assumption that y ∈ S_{m}(K), we cannot argue that a random sample point lands near y with non-negligible probability, thus we must handle both possibilities E_{close} and E_{far}. This is the main purpose of the two phases, i.e. the events E_{ℓ}^{σ} for ℓ ∈ {1, 2}. Thus the proof now breaks down into two sub-cases corresponding to the occurrences of E_{close} and E_{far}, respectively.

Claim 3.8 (The close case). Conditioned on the event E_{hit} ∩ E_{pad} ∩ E_{1}^{σ} ∩ E_{close} occurring, with probability at least p^{5},

|d(x, W_{t}^{i}) − d(y, W_{t}^{i})| ≥ \frac{2^{m−9}}{ζ_{K}} .

Proof. If the event E_{close} ∩ E_{pad} occurs, then there exists some j_{0} ∈ M and z ∈ { \atop P_{j_{0}}(x)} = { \atop P_{j_{0}}(y)} such that d(y, z) ≤ 2^{m−7}/ζ_{K} and κ(z, t) − 1 = j_{0}. Additionally, if E_{pad} ∩ E_{hit} occurs, then for every j ∈ M there is w_{j} ∈ { \atop P_{j}(x)} with d(w_{j}, x) ≤ 2^{m−9}/ζ_{K}. It follows that, for every j ∈ M,

d(w_{j}, z) ≥ d(x, y) − d(x, w_{j}) − d(y, z) ≥ 2^{m−1} − \frac{5 · 2^{m−9}}{ζ_{K}} ≥ 2^{m−2} ≥ 2^{j−3}.

Hence applying the definition of ζ_{K} to the sets { \atop P_{j}(x)} for j ∈ M, we conclude that there is an event E_{zero} with probability at least p^{5}, independent of E_{hit}, E_{pad}, E_{close} and E_{1}^{σ}, such that if the event E_{hit} ∩ E_{pad} ∩ E_{close} ∩ E_{1}^{σ} ∩ E_{zero} occurs then z ∈ Ψ_{j_{0}} \binom{}{P_{j_{0}}(y)}, and for every j ∈ M,

d (w_{j}, Ψ_{j} \binom{}{P_{j}(x)}) ≥ \frac{2^{j−3}}{ζ_{K}} ≥ \frac{2^{m−6}}{ζ_{K}} .

Applying Claim 3.7, it follows that d(x, W_{t}^{i}) ≥ \frac{5·2^{m−9}}{ζ_{K}}. Furthermore, since z ∈ Ψ_{j_{0}} \binom{}{P_{j_{0}}(y)} and E_{1}^{σ} occurs, we have σ_{j_{0}} = 1, hence z ∈ W_{t}^{i}. It follows that

|d(x, W_{t}^{i}) − d(y, W_{t}^{i})| ≥ \frac{5 · 2^{m−9}}{ζ_{K}} − d(y, z) ≥ \frac{2^{m−9}}{ζ_{K}} ,

completing the proof.

We now analyze the probability of the previous event.

Lemma 3.9. Pr[E_{hit} ∩ E_{pad} ∩ E_{1}^{σ} | E_{close}] ≥ 2^{−6} · 3^{−5}.

Proof. Since

Pr[E_{hit} ∩ E_{pad} ∩ E_{1}^{σ} | E_{close}] = 3^{−5} · Pr[E_{hit} ∩ E_{pad} | E_{close}] = 2^{−5} · 3^{−5} · Pr[E_{hit} | E_{pad}, E_{close}],

we need only argue that Pr[E_{hit} | E_{pad}, E_{close}] ≥ \frac{1}{2}. But this follows by applying Lemma 2.2, part 2(a), to the sets X = P_{j}(x), A = B(x, 2^{m−9}/ζ_{K}), B = B(y, 2^{m−7}/ζ_{K}), and concluding that

Pr[¬E_{hit}^{j} | E_{pad}, E_{close}] ≤ e^{(1−15K)/K} ≤ e^{−14}.

Thus Pr[E_{hit} | E_{pad}, E_{close}] ≥ 1 − 5e^{−14} ≥ \frac{1}{2}.

Now we proceed to analyze the case when E_{far} occurs. By Claim 3.4, every w ∈ B(x, 2^{m−9}/ζ_{K}) satisfies κ(w, t) − i ∈ M. By the pigeonhole principle, some j^{∗} ∈ M must occur as the value of κ(w, t) − i in at least a \frac{1}{5}th of them. Together with the growth condition implied by x ∈ S_{m}(K), we conclude that

|\{w ∈ B(x, 2^{m−9}/ζ_{K}) : κ(w, t) − i = j^{∗}\}| ≥ \frac{16}{5K} |B(x, 2^{m+5}α)| ≥ \frac{3}{K} |B(x, 2^{m+5}α)|.

Define the event E_{hit}^{∗} to be

\{∃w ∈ { \atop P_{j^{∗}}(x)} ∩ B(x, 2^{m−9}/ζ_{K}) with κ(w, t) − i = j^{∗}\},

and observe that by Lemma 2.2, part (1), Pr[E_{hit}^{∗}] ≥ 1 − e^{−3}.

Claim 3.10 (The far case). If E_{pad} ∩ E_{far} ∩ E_{2}^{σ} ∩ E_{hit}^{∗} occurs, then

|d(x, W_{t}^{i}) − d(y, W_{t}^{i})| ≥ \frac{2^{m−9}}{ζ_{K}} .

Proof. Assume that the event E_{pad} ∩ E_{far} ∩ E_{2}^{σ} ∩ E_{hit}^{∗} occurs, and let w ∈ { \atop P_{j^{∗}}(x)} ∩ B(x, 2^{m−9}/ζ_{K}) be the point guaranteed by E_{hit}^{∗}. Since σ_{j} = 2, we have w ∈ W_{t}^{i}, so that d(x, W_{t}^{i}) ≤ 2^{m−9}/ζ_{K}.

On the other hand, we claim that d(y, W_{t}^{i}) ≥ 2^{m−7}/ζ_{K}. Indeed, first note that E_{pad} implies that for all j ∈ M, d(y, X\P_{j}(y)) ≥ 2^{m}. Suppose that z ∈ W_{t}^{i} and d(y, z) ≤ 2^{m−7}/ζ_{K}. Let j′ = κ(z, t)−i. In this case, we have j′ ∈ M, hence σ_{j′} = 2, and this implies that z ∈ { \atop P_{j′}(z)} = { \atop P_{j′}(y)}. But in this case, E_{far} implies that d(y, z) > 2^{m−7}/ζ_{K}, yielding a contradiction. It follows that

|d(x, W_{t}^{i}) − d(y, W_{t}^{i})| ≥ \frac{2^{m−7}}{ζ_{K}} − \frac{2^{m−9}}{ζ_{K}} ≥ \frac{2^{m−9}}{ζ_{K}} .

Lemma 3.11. Pr[E_{pad} ∩ E_{2}^{σ} ∩ E_{hit}^{∗} | E_{far}] ≥ 2^{−5} · 3^{−5} · (1 − e^{−3}).

Proof.

Pr[E_{pad} ∩ E_{2}^{σ} ∩ E_{hit}^{∗} | E_{far}] = 3^{−5} · 2^{−5} · Pr[E_{hit}^{∗} | E_{far}, E_{pad}] ≥ Pr[E_{hit}^{∗} | E_{pad}] ≥ 3^{−5} · 2^{−5} · (1 − e^{−3}).

The penultimate inequality follows from the fact that conditioning on E_{far} cannot decrease the probability of E_{hit}^{∗}, as in Lemma 2.2, part 2(b).

To finish with the analysis of the Type II points, we apply Claim 3.8 together with Lemma 3.9 and Claim 3.10 with Lemma 3.11 to conclude that

𝔼|d(x, W_{t}^{i}) − d(y, W_{t}^{i})|^{2} ≥ (Pr[E_{good} ∩ E_{close} ∩ E_{1}^{σ} ∩ E_{zero}] + Pr[E_{pad} ∩ E_{far} ∩ E_{2}^{σ} ∩ E_{hit}^{∗}]) \frac{2^{2m−18}}{ζ_{K}^{2}}

= (Pr[E_{close}] Pr[E_{good} ∩ E_{1}^{σ} ∩ E_{zero} | E_{close}] + Pr[E_{far}] Pr[E_{pad} ∩ E_{2}^{σ} ∩ E_{hit}^{∗} | E_{far}]) \frac{2^{2m−18}}{ζ_{K}^{2}}
≥ \frac{1}{2} min\{2^{−6} · 3^{−5} · p^{5}, 2^{−5} · 3^{−5} · (1 − e^{−3})\}\frac{2^{2m−18}}{ζ_{K}^{2}}
≥ (\frac{p}{64})^{5} \frac{2^{2m}}{ζ_{K}^{2}} .

Since we have proved that (3) holds for both Type I points and Type II points, the proof is complete.

References

[1] S. Arora, J. R. Lee, and A. Naor. Euclidean distortion and the Sparsest Cut. Manuscript, 2004.

[2] S. Arora, S. Rao, and U. Vazirani. Expander flows, geometric embeddings, and graph partitionings. In 36th Annual Symposium on the Theory of Computing, pages 222–231, 2004.

[3] Y. Bartal. Probabilistic approximations of metric space and its algorithmic application. In 37th Annual Symposium on Foundations of Computer Science, pages 183–193, Oct. 1996.

[4] Y. Bartal, N. Linial, M. Mendel, and A. Naor. Limitations to Fréchet’s metric embedding method. Israel J. Math. To appear.

[5] Y. Bartal, N. Linial, M. Mendel, and A. Naor. On metric Ramsey-type phenomena. Ann. Math. To appear.

[6] J. Bourgain. On Lipschitz embedding of finite metric spaces in Hilbert space. Israel J. Math., 52(1-2):46–52, 1985.

[7] S. Chawla, A. Gupta, and H. Räcke. Embeddings of negative-type metrics and an improved approximation to generalized sparsest cut. In Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 102–111, Vancouver, 2005.

[8] A. Dvoretzky and C. A. Rogers. Absolute and unconditional convergence in normed linear spaces. Proc. Nat. Acad. Sci. U. S. A., 36:192–197, 1950.

[9] U. Feige, M. Hajiaghayi, and J. R. Lee. Improved approximation algorithms for minimumweight vertex separators. In STOC ’05: Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, pages 563–572, New York, NY, USA, 2005. ACM Press.

[10] A. A. Giannopoulos. A proportional Dvoretzky-Rogers factorization result. Proc. Amer. Math. Soc., 124(1):233–241, 1996.

[11] M. X. Goemans. Semidefinite programming and combinatorial optimization. Mathematical Programming, 49:143–161, 1997.

[12] S. Khot and N. Vishnoi. The unique games conjecture, integrality gap for cut problems and embeddability of negative type metrics into ℓ_{1}. In Proceedings of the 46th Annual IEEE Conference on Foundations of Computer Science, 2005. To appear.

[13] R. Krauthgamer, J. R. Lee, M. Mendel, and A. Naor. Measured descent: A new embedding method for finite metrics. Geom. Funct. Anal., 2004. To appear.

[14] J. R. Lee. On distance scales, embeddings, and efficient relaxations of the cut cone. In Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 92– 101, Vancouver, 2005.

[15] N. Linial and M. Saks. Low diameter graph decompositions. Combinatorica, 13(4):441–454, 1993.

[16] J. Matoušek and Y. Rabinovich. On dominated l_{1} metrics. Israel J. Math., 123:285–301, 2001.

[17] S. Rao. Small distortion and volume preserving embeddings for planar and Euclidean metrics. In Proceedings of the 15th Annual Symposium on Computational Geometry, pages 300–306, New York, 1999.