Metric Space Embeddings into l_1: An Optimization Approach (Thesis)

Report ID: TR-701-04
Author: Brinkman, William J.
Date: 2004-05-00
Pages: 114
Download Formats: |PDF|
Abstract:

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.

m 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 graph metrics.

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.