A Caltech Library Service

Dimensionality reduction: beyond the Johnson-Lindenstrauss bound

Bartal, Yair and Recht, Ben and Schulman, Leonard J. (2011) Dimensionality reduction: beyond the Johnson-Lindenstrauss bound. In: Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms. Association for Computing Machinery , New York, pp. 868-887. ISBN 978-0-898719-93-2.

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item:


Dimension reduction of metric data has become a useful technique with numerous applications. The celebrated Johnson-Lindenstrauss lemma states that any n-point subset of Euclidean space can be embedded in O(ε^(−2)log n)-dimension with (1 + ε)-distortion. This bound is known to be nearly tight. In many applications the demand that all distances should be nearly preserved is too strong. In this paper we show that indeed under natural relaxations of the goal of the embedding, an improved dimension reduction is possible where the target dimension is independent of n. Our main result can be viewed as a local dimension reduction. There are a variety of empirical situations in which small distances are meaningful and reliable, but larger ones are not. Such situations arise in source coding, image processing, computational biology, and other applications, and are the motivation for widely-used heuristics such as Isomap and Locally Linear Embedding. Pursuing a line of work begun by Whitney, Nash showed that every C^1 manifold of dimension d can be embedded in R^(2d+2) in such a manner that the local structure at each point is preserved isometrically. Our work is an analog of Nash's for discrete subsets of Euclidean space. For perfect preservation of infinitesimal neighborhoods we substitute near-isometric embedding of neighborhoods of bounded cardinality. We show that any finite subset of Euclidean space can be embedded in O(ε^(−2)log k)-dimension while preserving with (1 + ε)-distortion the distances within a "core neighborhood" of each point. (The core neighborhood is a metric ball around the point, whose radius is a substantial fraction of the radius of the ball of cardinality k, the k-neighborhood.) When the metric space satisfies a weak growth rate property, the guarantee applies to the entire k-neighborhood (with some dependency of the embedding dimension on the growth rate). We also show how to obtain a global embedding that also keeps distant points well-separated (at the cost of dependency on the doubling dimension of the space). As an application of our methods we obtain an (Assouad-style) dimension reduction for finite subsets of Euclidean space where the metric is raised to some fractional power (the resulting metrics are known as snowflakes). We show that any such metric X can be embedded in dimension Õ(ε^(−3) dim(X)) with 1 + ε distortion, where dim(X) is the doubling dimension, a measure of the intrinsic dimension of the set. This result improves recent work by Gottlieb and Krauthgamer [20] to a nearly tight bound. The new dimension reduction results are useful for applications such as clustering and distance labeling.

Item Type:Book Section
Related URLs:
URLURL TypeDescription
Schulman, Leonard J.0000-0001-9901-2797
Additional Information:© 2011 SIAM. A previous version of this paper was posted under the title: "A Nash-type Dimensionality Reduction for Discrete Subsets of L2". The work of the first and second authors was performed in part while at the Center for the Mathematics of Information, Caltech. School of Engineering and Computer Science, Hebrew University, Israel. Supported in part by a grant from the Israeli Science Foundation (195/02) and in part by a grant from the National Science Foundation (NSF CCF-065253). Supported in part by NSA H98230-06-1-0074, NSF CCF-0515342 and NSF CCF-0829909.
Funding AgencyGrant Number
Israel Science Foundation195/02
Record Number:CaltechAUTHORS:20120509-070406524
Persistent URL:
Official Citation:Dimensionality reduction: beyond the Johnson-Lindenstrauss bound Yair Bartal, Ben Recht, Leonard J. Schulman Pages: 868-887
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:31370
Deposited By: Ruth Sustaita
Deposited On:09 May 2012 17:14
Last Modified:09 Mar 2020 13:19

Repository Staff Only: item control page