CaltechAUTHORS
  A Caltech Library Service

Advances in metric embedding theory

Abraham, Ittai and Bartal, Yair and Neiman, Ofer (2011) Advances in metric embedding theory. Advances in Mathematics, 228 (6). pp. 3026-3126. ISSN 0001-8708. https://resolver.caltech.edu/CaltechAUTHORS:20111122-115302690

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

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

Abstract

Metric Embedding plays an important role in a vast range of application areas such as computer vision, computational biology, machine learning, networking, statistics, and mathematical psychology, to name a few. The mathematical theory of metric embedding is well studied in both pure and applied analysis and has more recently been a source of interest for computer scientists as well. Most of this work is focused on the development of bi-Lipschitz mappings between metric spaces. In this paper we present new concepts in metric embeddings as well as new embedding methods for metric spaces. We focus on finite metric spaces, however some of the concepts and methods are applicable in other settings as well. One of the main cornerstones in finite metric embedding theory is a celebrated theorem of Bourgain which states that every finite metric space on n points embeds in Euclidean space with View the MathML source distortion. Bourgainʼs result is best possible when considering the worst case distortion over all pairs of points in the metric space. Yet, it is natural to ask: can an embedding do much better in terms of the average distortion? Indeed, in most practical applications of metric embedding the main criteria for the quality of an embedding is its average distortion over all pairs.


Item Type:Article
Related URLs:
URLURL TypeDescription
http://dx.doi.org/10.1016/j.aim.2011.08.003 DOIUNSPECIFIED
http://www.sciencedirect.com/science/article/pii/S000187081100288XPublisherUNSPECIFIED
Additional Information:© 2011 Elsevier Inc. Received 16 August 2010; accepted 11 August 2011. Available online 9 September 2011. Communicated by Gil Kalai. Most of the research on this paper was carried out while the author was a student at the Hebrew University. Most of the research was done while the author was supported in part by a grant from the Israeli Science Foundation (195/02) and part of the research was done while the author was at the Center of the Mathematics of Information, Caltech, CA, USA, and was supported in part by a grant from the National Science Foundation (NSF CCF-0652536). Most of the research on this paper was carried out while the author was a student at the Hebrew University and was supported in part by a grant from the Israeli Science Foundation (195/02). Part of the work was done while the author was a postdoctoral scholar at the NYU Courant Institute of Mathematics, and was funded by NSF Expeditions in Computing award, 2009–2010.
Funders:
Funding AgencyGrant Number
Israeli Science Foundation195/02
NSFCCF-0652536
NSF Expeditions in Computing2009-2010
Subject Keywords:Metric spaces; Embedding; Dimension reduction; Coarse geometry; Algorithms
Issue or Number:6
Record Number:CaltechAUTHORS:20111122-115302690
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:20111122-115302690
Official Citation:Ittai Abraham, Yair Bartal, Ofer Neiman, Advances in metric embedding theory, Advances in Mathematics, Volume 228, Issue 6, 20 December 2011, Pages 3026-3126, ISSN 0001-8708, 10.1016/j.aim.2011.08.003. (http://www.sciencedirect.com/science/article/pii/S000187081100288X)
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:27919
Collection:CaltechAUTHORS
Deposited By: Ruth Sustaita
Deposited On:22 Nov 2011 21:21
Last Modified:03 Oct 2019 03:27

Repository Staff Only: item control page