1. Negative type metrics
We started studying distorsion of embeddings of finite metric spaces into -spaces. We discussed obstructions for a metric space to have small distorsion into -spaces. Today, we make steps in the direction of -embeddings.
Terminology: say a metric is an -metric if it is induced by a map to .
1.1. Negative type
Definition 1 Say a metric is of negative type iff is an -metric.
By Schoenberg’s criterion, a metric is of negative type if for all , the matrix is negative definite.
Proposition 2 -metrics -metrics negative type metrics.
We have seen problems which lead to minimizing linear functionals on the cone of -metrics. Exact minimization over negative type metrics is doable (SDP). So an approach is to project every negative type metric to -metrics, i.e. attempt to embed negative type metrics in and control distorsion.
Proof: Claim: is of negative type.
Indeed, Let be defined by
i.e. the square root of metric is an -metric.
Claim: embeds isometrically into .
Indeed, let denote the Gaussian measure on infinite dimensional Hilbert space . If is a Gaussian variable, is a function of only. In other words, when restricted to linear functions on , and norms are proportional.
Bartholdi: Could such an isometric embedding be given by a linear map ? Answer: No. The image cannot by rectifiable.
Bartholdi: Why aren’t you interested in rather than ? Answer: every finite -metric is also an -metric, but in a larger dimension (). A metric is an -metric iff its restriction to every finite subset is an -metric. This does not work for . For instance, does not bilipschitz embed in . So is the right space to look at.
1.2. The Goemans-Linial conjecture
Conjecture: Every metric space of negative type admits a bilipschitz embedding into .
This was motivated by approximation algorithms for SPARSEST CUT, see Robi Krauthgamer’s second course.
It turns out to be false. Counterexamples by Subhash Khot and Nisheeth Vishnoi, and later by Jeff Cheeger and Bruce Kleiner: they show that Heisenberg group in its Carnot metric does not bilipschitz embed into . Whereas Assaf Naor and I have found a left invariant metric on Heisenberg group, quasiisometric to the Carnot metric, which has negative type. An effective form of their theorem states
Theorem 3 (Cheeger, Kleiner, Naor) such that
Conversely, here is the best known upper bound on the distorsion of embeddings of -point metric spaces of negative type.
Theorem 4 (Arora, Lee, Naor)
Note that this implies that
which is nearly sharp. Let denote the class of metrics such that is a metric which embeds in with bounded distorsion. Then
Theorem 5 (Lee, Sidiropoulos)
1.3. Observable diameter in
Observable diameter have been previously defined in terms of maps to the real line. There is a generalization where the real line is replaced by an arbitrary metric space as a range. It is crucial, for various issues in computer science, to understand the observable diameter in of various classes of metric spaces. Since every compact metric measure space can be approximated by graphs with counting measure, it is related to the best constant in the Poincaré inequality for scalar functions on graphs.
For general finite metric spaces, the observable diameter in is exponential in . But for negative type metrics, there are bounds
In the Hilbert case, the story goes back to the 1960’s.
Theorem 6 (Enflo 1969) For all ,
This implies that the distorsion of every map of the cube to has distorsion .
Here comes the upper bound on the observable diameter.
Theorem 7 (Arora, Rao, Vazirani) If has negative type, then there exists a -Lipschitz function such that
Note one can replace negative type by : which admits a quasisymmetric embedding into Hilbert space.
1.4. From -observable diameter to -embeddings
Theorem 8 (Lee) Let have negative type. Let , let be an integer valued measure on pairs of points of at distance . Then there exists a -Lipschitz function and two sets , with measure that are separated by , i.e. for all , such that ,
In other words, there exists a map to which separates a certain proportion of pairs which are far apart in . Using it, Chawla, Gupta and Räcke have been able to improve Theorem 8 into a uniform distorsion bound.
Theorem 9 (Chawla, Gupta, Räcke) Let have negative type. Let . There exists a -Lipschitz map such that for all , with ,
In other words, has an -ensemble with .
Proof: Boosting: Order the pairs such that . Put uniform measure on them. Then modify recursively as follows. Apply Theorem 8 to get function . Set
and get function accordingly. Form the rescaled direct sum
One checks that every pair will be handled at some time .
We seem to be in bad shape: we have lost a factor of and still do not have a bilipschitz embedding in . Local dimension will save us.
1.5. Local dimension
Let be a finite metric space, and . Easily, one has
Idea: Replace by , which measures the dimension of at scale . Then glue scales together. The gluing is achieved by the following theorem.
Theorem 10 (Lee) Let be an -point metric space. Let be -Lipschitz maps. Then there exists a map such that
- For all , ,
Proof: Let be the direct sum of rescaled by the weights in the theorem. The Lipschitz upper bound follows from the fact that weights sum up to at each point.
Weights are not smooth, they are strongly discontinuous. Nevertheless, the function
is -Lipschitz. Let
where , has support , equals on . Use these numbers as weights, i.e. set
anf let be the direct sum of all ‘s. Then
- ‘s are uniformly Lipschitz.
- If , then
Since this lower bound holds for values of , the proof follows.