Low Dimensional Embeddings of Ultrametrics

Yair Bartal^{∗}  Nathan Linial^{†}  Manor Mendel^{‡}  Assaf Naor

May 20, 2003

Abstract In this note we show that every n-point ultrametric embeds with constant distortion in ℓ_{p}^{O(log n)} for every ∞ ≥ p ≥ 1. More precisely, we consider a special type of ultrametric with hierarchical structure called a k-hierarchically well-separated tree (k-HST). We show that any k-HST can be embedded with distortion at most 1 + O(1/k) in ℓ_{p}^{O(k^{2} log n)}. These facts have implications to embeddings of finite metric spaces in low dimensional ℓ_{p} spaces in the context of metric Ramsey-type theorems.

1 Introduction

An ultrametric is a metric space (X, d) such that for every x, y, z ∈ X,

d(x, z) ≤ max{d(x, y), d(y, z)}.

A more restricted class of finite metrics with an inherently hierarchical structure is that of k-hierarchically well-separated trees, defined as follows:

Definition 1. [1] For k ≥ 1, a k-hierarchically well-separated tree (k-HST) is a metric space whose elements are the leaves of a rooted finite tree T. To each vertex u ∈ T there is associated a label Δ(u) ≥ 0 such that Δ(u) = 0 iff u is a leaf of T. It is required that if a vertex u is a child of a vertex v then Δ(u) ≤ Δ(v)/k . The distance between two leaves x, y ∈ T is defined as Δ(lca(x, y)), where lca(x, y) is the least common ancestor of x and y in T.

The notion of 1-HST coincides with that of an ultrametric. Any k-HST is also a 1-HST, i.e., an ultrametric. However, for every k > 1 the class of k-HST is a proper subclass of ultrametrics. Ultrametrics and k-HSTs have played a key role in recent work on embeddings of finite metric spaces [2, 3, 4, 5].

Let f : X → Y be an embedding of the metric space (X, d_{X}) into the metric space (Y, d_{Y}). We define the distortion of f by

dist(f) = 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))}.

We denote by c_{Y} (X) the least distortion with which X may be embedded in Y. When c_{Y} (X) ≤ α we say that X α-embeds into Y. When there is a bijection f between two metric spaces X and Y with dist(f) ≤ α we say that X and Y are α-equivalent.

The following proposition provides a comparison between ultrametrics and k-HSTs.

∗Supported in part by a grant from the Israeli National Science Foundation

†Supported in part by a grant from the Israeli National Science Foundation

‡Supported in part by the Landau Center.

Proposition 1 ([2]). For any k > 1, any ultrametric is k-equivalent to a k-HST.

A basic property of ultrametrics is:

Proposition 2 ([8]). Any ultrametric is isometrically embeddable in ℓ_{2}.

Since ℓ_{2} isometrically embeds into L_{p} for every 1 ≤ p ≤ ∞, a similar result follows for embeddings in ℓ_{p}. Moreover, a careful analysis the proof of the above proposition yields an isometric embedding of any n-point HST into ℓ_{p}^{O(n)}.

Here we consider the dimension for which ultrametrics and k-HST spaces embed with a given distortion in ℓ_{p}, 1 ≤ p ≤ ∞. For ℓ_{2} this is answered by the Johnson-Lindenstrauss dimension reduction lemma [7] which states that for every ϵ > 0, any n-point metric space in ℓ_{2} can be (1+ϵ)-embedded in ℓ_{2}^{O(log n/ϵ^{2})}. Using [6], it follows that any set of n points in ℓ_{2} can

be embedded with constant distortion into ℓ_{p}^{O(log n)} for 1 ≤ p ≤ 2 and into ℓ_{p}^{O(\sqrt{p}(log n)^{p/2})} for p > 2. The main result of this note improves the the upper bound on the dimension required to embed n-point ultrametrics into ℓ_{p}, p > 2, and gives additional structural information on the problem for embeddings into low dimensional ℓ_{p} spaces for 1 ≤ p ≤ 2. Moreover, we show that any n-point k-HST can be embedded in ℓ_{p} with constant distortion and dimension logarithmic in n. Furthermore, the distortion approaches 1 as k grows.

Proposition 3. Fix an integer k > 5. Then for any 1 ≤ p < ∞, any k-HST can be (\frac{k+1}{k−5})-

embedded in ℓ_{p}^{h} with h = ⌈C(1 + k/p)^{2} log D⌉, where D is the maximal out-degree of a vertex in the tree defining the k-HST, and C > 0 is a universal constant.

Proposition 3 is proved in Section 2. Combining Proposition 1 and Proposition 3 we obtain:

Corollary 4. For any 1 ≤ p ≤ ∞, any n point ultrametric can be O(1)-embedded into ℓ_{p}^{O(log n)}.

We also show how to apply this lemma to the metric Ramsey-type problems. A metric Ramsey-type theorem states that a given metric space contains a large subset which can be embedded with small distortion in some “well-structured” family of metric spaces (e.g. Euclidean metrics). This can be formulated using the following notion.

Definition 2. Let M be some class of metric spaces. Denote by R_{M}(α, n) the largest integer m such that any n-point metric space has a subset of size m that α-embeds into a member of M. When M = {ℓ_{p}}, we use R_{p} rather than R_{ℓ_{p}}.

In [4] it is shown that for every 1 ≤ p ≤ ∞ and α > 2, R_{p}(α, n) ≥ n^{1−O(\frac{log α}{α})} and for

every 0 < ε < 1, R_{p}(2 + ε, n) ≥ n^{Ω( \frac{ε}{log(2/ε)} )}. We refer to [4] and the references therein for a comprehensive description metric Ramsey problems and their history. Using Lemma 3, we prove the following variant of the result of [4] in which there is control on the dimension in the metric Ramsey problem for ℓ_{p}, p ≥ 1. This application was our original motivation for studying low-dimensional embeddings of ultrametrics.

Theorem 1. The following assertions hold:

1. There exist absolute constants c, C > 0 such that for all 1 ≤ p ≤ ∞ and for every α > 2,

R_{ℓ_{p}^{d}}(α, n) ≥ n^{1−C \frac{log α}{α}} , where d = ⌈c log n⌉ .

2. There are absolute constants C, c > 0 such that for every 0 < ϵ < 1, 1 ≤ p < ∞ and every integer n,

R_{ℓ_{p}^{d}}(2 + ϵ, n) ≥ n^{\frac{cϵ}{log(2/ϵ)}} , where d = ⌈C \frac{ε⌈(εp)^{−2}⌉}{log(2/ϵ)} log n⌉ .

2 Embedding HSTs in low dimensional ℓ_{p} spaces

We follow Definition 1, and associate with any k-HST, the tree T defining the HST. An internal vertex in T with out-degree 1 is said to be degenerate. If u is non-degenerate, then Δ(u) is the diameter of the sub-space induced on the subtree rooted by u. Degenerate nodes do not influence the metric on T ’s leaves, hence we may assume that all internal nodes are nondegenerate. In particular for an HST X, diam(X) = Δ(root(T)), where T is the tree defining X.

We make use of the following standard construction of codes, the proof of which is included for the sake of completeness. In what follows, for w, v ∈ {0, 1}^{h}, w ⊕ v denotes the point-wise addition modulo 2 of v and w.

Lemma 5. For any h ∈ ℕ, and τ ∈ (0, 1), there exists K ⊂ {0, 1}^{h} such that the Hamming distance between any two distinct elements of K is in the range [(1 − τ)h/2, (1 + τ)h/2] and |K| ≥ ⌊e^{hτ^{2}/8}⌋.

Proof. Let w, v ∈ {0, 1}^{h} be random elements. Then by Chernoff bound, the probability that w⊕v has less than (1−δ)h/2 1’s is at most e^{−δ^{2}h/4}. Similarly, the probability it has more than (1 + δ)h/2 1’s is also at most e^{−δ^{2}h/4}. Given m random elements w_{1}, …, w_{m} ∈ {0, 1}^{h}, the probability that the distance between any two of them isn’t in the range [(1−δ)h/2, (1+δ)h/2] is at most \binom{m}{2}2e^{−δ^{2}h/4} < m^{2}e^{−δ^{2}h/4}. Thus, choosing m = ⌊e^{δ^{2}h/8}⌋ implies that with a positive probability the subset K = {w_{1}, …, w_{m}} has the required properties.

Proof of Lemma 3. Let u be the root of the tree defining X and X_{1}, …, X_{s} be the leaf sets of subtrees rooted at the children of u. Note that s ≤ D. For p < ∞, let τ = (1 + k/p)^{−1}/6. Set h = ⌈8τ^{−2} log s⌉, so that e^{hτ^{2}/8} ≥ s. By Lemma 5 there exists K ⊂ {0, 1}^{h} with all Hamming distances in the range [(1 − τ)h/2, (1 + τ)h/2] and |K| ≥ s. Choose s distinct c_{1}, …, c_{s} ∈ K. By switching to c_{1} ⊕ c_{1}, c_{2} ⊕ c_{1}, …, c_{s} ⊕ c_{1} we may assume that c_{1} = 0, in which case for 1 ≤ i ≤ s, ∥c_{i}∥_{1} ≤ \frac{1+τ}{2} h.

Assume inductively that for each i we have an embedding ϕ_{i} : X_{i} → ℓ_{p}^{h}, such that:

• For all x, y ∈ X_{i}, \frac{k−5}{k+1}d_{X_{i}}(x, y) ≤ ∥ϕ_{i}(x) − ϕ_{i}(y)∥_{p} ≤ d_{X_{i}}(x, y).

• For every x ∈ X_{i}, ∥ϕ_{i}(x)∥_{p} ≤ diam(X_{i}).

Let λ = (\frac{1+τ}{2} h)^{−1/p} \frac{k−2}{k}, and let Δ = diam(X). Define an embedding ϕ : X → ℓ_{p}^{h} of X as follows: for x ∈ X_{i},

ϕ(x) = ϕ_{i}(x) + λΔc_{i}.

Then:

∥ϕ(x)∥_{p} ≤ ∥ϕ_{i}(x)∥_{p} + λΔ∥c_{i}∥_{p} ≤ diam(X_{i}) + (\frac{1 + τ}{2} h)^{−1/p} \frac{k − 2}{k}Δ∥c_{i}∥_{1}^{1/p}
≤ \frac{Δ}{k} + \frac{k − 2}{k}Δ < Δ.

For x, y ∈ X_{i}, ∥ϕ(x) − ϕ(y)∥_{p} = ∥ϕ_{i}(x) − ϕ_{i}(y)∥_{p}, so by the induction hypothesis:

\frac{k − 5}{k + 1}d_{X}(x, y) ≤ ∥ϕ(x) − ϕ(y)∥_{p} ≤ d_{X}(x, y).

For x ∈ X_{i}, y ∈ X_{j} and i ≠ j, we have d_{X}(x, y) = Δ. Now

∥ϕ(x) − ϕ(y)∥_{p} ≤ λΔ∥c_{i} − c_{j}∥_{p} + ∥ϕ_{i}(x)∥_{p} + ∥ϕ_{j}(x)∥_{p}
≤ λΔ∥c_{i} − c_{j}∥_{1}^{1/p} + diam(X_{i}) + diam(X_{j})
≤ (\frac{1 + τ}{2} h)^{−1/p} \frac{k − 2}{k}Δ (\frac{1 + τ}{2} h)^{1/p} + \frac{2}{k} Δ = Δ = d_{X}(x, y),

and

∥ϕ(x) − ϕ(y)∥_{p} ≥ λΔ∥c_{i} − c_{j}∥_{p} − ∥ϕ_{i}(x)∥_{p} − ∥ϕ_{j}(x)∥_{p}
≥ λΔ∥c_{i} − c_{j}∥_{1}^{1/p} − diam(X_{i}) − diam(X_{j})
≥ (\frac{1 + τ}{2} h)^{−1/p} \frac{k − 2}{k}Δ (\frac{1 − τ}{2} h)^{1/p} − \frac{2}{k} Δ
≥ ((\frac{1 − τ}{1 + τ} )^{1/p} \frac{k − 2}{k} − \frac{2}{k} ) Δ
≥ (\frac{k}{k + 1} · \frac{k − 2}{k} − \frac{2}{k} ) Δ ≥ \frac{k − 5}{k + 1}d_{X}(x, y).

The last inequality holds for k > 5 and the preceding derivation follows from the definition of τ:

(\frac{1 − τ}{1 + τ} )^{1/p} ≥ (1 + 3τ)^{−1/p} ≥ (1 + 6τ/p)^{−1} = (1 + (1 + k/p)^{−1}/p)^{−1} ≥ (1 + 1/k)^{−1}.

3 Implications

Denote by UM the class of all ultrametrics. We will need the following theorem:

Theorem 2 ([4]). The following assertions hold for every integer n:

1. There exists an absolute constant C′ > 0 such that for every α > 2,

R_{UM}(α, n) ≥ n^{1−C′ \frac{log α}{α}} .

2. There is an absolute constant c > 0 such that for any k ≥ 1 and 0 < ϵ < 1, for any

integer n:

R_{k-HST}(2 + ϵ, n) ≥ n^{\frac{cϵ}{log(2k/ϵ)}} .

Proposition 2 implies similar bounds for R_{2}(α, n). We next show how to extend those results for embedding into ℓ_{p}^{O(log n)} by using Lemma 3.

Proof of Theorem 1. We begin with the first claim of the theorem. Let C′ > 0 be the constant at the first assertion in Theorem 2, and let β be a universal constant such that any n-point ultrametric β embeds in ℓ_{p}^{O(log n)} (Corollary 4). We choose C = βC′, so that C \frac{log α}{α} ≥ C′ \frac{log(α/β)}{α/β}. From Theorem 2 we deduce that

R_{UM}(α/β, n) ≥ n^{1−C′ \frac{log(α/β)}{α/β}} ≥ n^{1−C \frac{log α}{α}} .

The subset described by this statement is (α/β)-equivalent to an ultrametric and so, by Corollary 4, it is α-embeddable in ℓ_{p}^{O(log n)}.

We next consider the second statement in the theorem. Let δ = ϵ/4 and k = ⌊5 + 6/δ⌋,

then by Theorem 2, there exists c′ > 0 such that R_{k-HST}(2 + δ, n) ≥ n^{\frac{c′δ}{log(2/δ)}} . Let M be an arbitrary metric space. For an appropriate choice of c this means that M contains a subset Y of size m = ⌈n^{\frac{cϵ}{log(2/ϵ)}} ⌉ that is (2 + δ)-equivalent to some k-HST X. By Proposition 3 and our choice of k, there exists some constant C′ > 0 such that X can be (1 + δ)-embedded in ℓ_{p}^{d}, where

d = ⌈C′⌈(δp)^{−2}⌉ log m⌉ = ⌈C \frac{ϵ⌈(ϵp)^{−2}⌉}{log(2/ϵ)} log n⌉ ,

for an appropriate choice of C. Therefore Y is (2 + δ)(1 + δ) ≤ (2 + ϵ)-embedded in ℓ_{p}^{d}.

References

[1] Y. Bartal. Probabilistic approximation of metric spaces and its algorithmic applications. In 37th Annual Symposium on Foundations of Computer Science, pages 184–193, 1996.

[2] Y. Bartal. On approximating arbitrary metrics by tree metrics. In Proceedings of the 30th Annual ACM Symposium on Theory of Computing, pages 183–193, 1998.

[3] Y. Bartal, B. Bollobás, and M. Mendel. Ramsey-type theorems for metric spaces with applications to online problems, 2002. A preliminary version appeared in FOCS ’01.

[4] Y. Bartal, N. Linial, M. Mendel, and A. Naor. On Metric Ramsey-type Phenomena. In Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 2003.

[5] Jittat Fakcharoenphol, Satish Rao, and Kunal Talwar. A tight bound on approximating arbitrary metrics by tree metrics. In Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 2003.

[6] T. Figiel, J. Lindenstrauss, and V. D. Milman. The dimension of almost spherical sections of convex bodies. Acta Math., 139(1-2):53–94, 1977.

[7] W. B. Johnson and J. Lindenstrauss. Extensions of Lipschitz mappings into a Hilbert space. In Conference in modern analysis and probability (New Haven, Conn., 1982), pages 189–206. Amer. Math. Soc., Providence, RI, 1984.

[8] Alex J. Lemin. Isometric embedding of ultrametric (non-Archimedean) spaces in Hilbert space and Lebesgue space. In p-adic functional analysis (Ioannina, 2000), volume 222 of Lecture Notes in Pure and Appl. Math., pages 203–218. Dekker, New York, 2001.

Yair Bartal, Institute of Computer Science, Hebrew University, Jerusalem 91904, Israel. yair@cs.huji.ac.il

Nathan Linial, Institute of Computer Science, Hebrew University, Jerusalem 91904, Israel. nati@cs.huji.ac.il

Manor Mendel, Institute of Computer Science, Hebrew University, Jerusalem 91904, Israel. mendelma@cs.huji.ac.il

Assaf Naor, Theory Group, Microsoft Research, One Microsoft Way 113/2131, Redmond WA 98052-6399, USA. anaor@microsoft.com