Metric Space Embeddings into l_1: An Optimization Approach (Thesis)
The technique of metric space embeddings into Euclidean space has been
used extensively to give powerful approximation algorithms for a
variety of problems. Much of the success of this technique has been
due to the famous lemma of Johnson and Lindenstrauss which says that
any n points in Euclidean space can be well approximated by vectors of
length roughly O(log n) via random projections.
Embeddings into Euclidean space, however, are known to be somewhat
limited: For example, there are planar graph metrics which require
Ω(√log n) distortion in Euclidean space.
Finite metric spaces in Rd
under the l1 norm arise in practice as well, and it is known that for
embedding this is a strictly richer class of metrics than the finite
Euclidean metrics. This has motivated an interest in l1 as a possible
host space for difficult metrics, particularly edit metrics and planar
We have developed an approach to the study of l1 embeddings based on
mathematical optimization. We show how these techniques, through
duality, lead naturally to both lower bounds and algorithms. We
demonstrate this approach by proving that no analogue of the
Johnson-Lindenstrauss lemma exists for l1. This answers the open
question recently popularized by both Piotr Indyk and Nathan Linial.