CaltechAUTHORS
  A Caltech Library Service

Embedding metric spaces in their intrinsic dimension

Abraham, Ittai and Bartal, Yair and Neiman, Ofer (2008) Embedding metric spaces in their intrinsic dimension. In: SODA '08 Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms. Society for Industrial and Applied Mathematics , Philadelphia, PA, pp. 363-372. https://resolver.caltech.edu/CaltechAUTHORS:20160414-160718051

[img] PDF - Published Version
See Usage Policy.

518kB

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20160414-160718051

Abstract

A fundamental question of metric embedding is whether the metric dimension of a metric space is related to its intrinsic dimension. That is whether the dimension in which it can be embedded in some real normed space is implied by the intrinsic dimension which is reflected by the inherent geometry of the space. The existence of such an embedding was conjectured by Assouad and was later posed as an open problem by others. This question is tightly related to a major goal of many practical application fields: developing tools to represent intrinsically low dimensional metric data sets in a succinct manner. In this paper we give the first algorithmic technique with formal guarantees for finding faithful and low dimensional representations of data lying in high dimensional space. Our main theorem states that every finite metric space X embeds into Euclidean space with dimension O(dim(X)/ϵ) and distortion O(log^(1+ϵ) n), where dim(X) is the doubling dimension of the space X. Moreover, we show that X can be embedded into dimension Õ(dim(X)) with constant average distortion and ℓ_q-distortion for any q < ∞. Our technique also provides a dimension-distortion tradeoff and an extension of Assouad’s theorem, providing distance oracles that improve known construction when dim(X) = o(log |X|).


Item Type:Book Section
Related URLs:
URLURL TypeDescription
http://dl.acm.org/citation.cfm?id=1347122PublisherArticle
Additional Information:© 2008 Society for Industrial and Applied Mathematics. October 11, 2007. Supported in part by a grant from the Israeli Science Foundation (195/02).
Funders:
Funding AgencyGrant Number
Israel Science Foundation195/02
Record Number:CaltechAUTHORS:20160414-160718051
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:20160414-160718051
Official Citation:Ittai Abraham, Yair Bartal, and Ofer Neiman. 2008. Embedding metric spaces in their intrinsic dimension. In Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms (SODA '08). Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 363-372.
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:66196
Collection:CaltechAUTHORS
Deposited By: Kristin Buxton
Deposited On:14 Apr 2016 23:29
Last Modified:03 Oct 2019 09:54

Repository Staff Only: item control page