Title: Dimension reduction in the l_1 norm

Speaker: Moses Charikar, Princeton University

Date: Tuesday, April 22, 2003 4:30-5:30pm

Location: Hill Center, room 705, (Note room change) Rutgers University, Busch Campus, Piscataway, NJ

Abstract:

The Johnson-Lindenstrauss Lemma shows that any set of n points in Euclidean space can be mapped linearly down to O((log n)/eps^2) dimensions such that all pairwise distances are distorted by at most 1+eps. We study the following basic question: Does there exist an analogue of the Johnson-Lindenstrauss Lemma for the l_1 norm?

Note that the Johnson-Lindenstrauss Lemma gives a linear embedding which is independent of the point set. For the l_1 norm, we show that one cannot hope to use linear embeddings as a dimensionality reduction tool for general point sets, even if the linear embedding is chosen as a function of the given point set. In particular, we construct a set of O(n) points in l_1 such that any linear embedding into l_1^d must incur a distortion of Omega(sqrt{n/d}). This bound is tight up to a log n factor. We then initiate a systematic study of general classes of l_1 embeddable metrics that admit low dimensional, small distortion embeddings. In particular, we show dimensionality reduction theorems for tree metrics, circular-decomposable metrics, and metrics supported on K_{2,3}-free graphs, giving embeddings into l_1^{O(log^2 n)} with constant distortion. Finally, we also present lower bounds on dimension reduction techniques for other l_p norms.

Our work suggests that the notion of a stretch-limited embedding, where no distance is stretched by more than a factor d in any dimension, is important to the study of dimension reduction for l_1. We use such stretch limited embeddings as a tool for proving lower bounds for dimension reduction and also as an algorithmic tool for proving positive results.

This is joint work with Amit Sahai and appeared in FOCS'02.