Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published December 20, 2011 | public
Journal Article

Advances in metric embedding theory

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.

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.

Additional details

Created:
August 22, 2023
Modified:
October 24, 2023