Bilipschitz Embedding in Banach Spaces
by
Bruce Kleiner
Yale University
Coauthors: Jeff Cheeger

A mapping between metric spaces is L-bilipschitz if it stretches distances by a factor of at most L, and compresses them by a factor no worse than 1/L. A basic problem in geometric analysis is to determine when one metric space can be bilipschitz embedded in another, and if so, to estimate the optimal bilipschitz constant. In recent years this question has generated great interest in computer science, since many data sets can be represented as metric spaces, and associated algorithms can be simplified, improved, or estimated, provided one knows that the metric space space in question can be bilipschitz embedded (with controlled bilipschitz constant) in a nice space, such as L² or L¹.

The lecture will discuss several new existence and non-existence results for bilipschitz embeddings in Banach spaces. One approach to non-existence theorems is based on generalized differentiation theorems in the spirit of Rademacher's theorem on the almost everywhere differentiability of Lipschitz functions on Rⁿ. We first show that earlier differentiation based results of Pansu and Cheeger, which proved non-existence of embeddings into R^k, generalize to many Banach space targets, such as L^p for 1 < p < ∞. We then focus on the case when the target is L¹, where differentiation theory is known to fail, and the embedding questions are of particular interest in computer science. When the domain is the Heisenberg group with its Carnot-Caratheodory metric, we show that a modified form of differentiation still holds for Lipschitz maps into L¹, by exploiting a new connection with functions of bounded variation, and some very recent advances in geometric measure theory.

Date received: November 6, 2007