On the distortion required for embedding finite metric spaces into normed spaces

DOI10.1007/BF02761110zbMath0851.46007OpenAlexW2027697499WikidataQ56001796 ScholiaQ56001796MaRDI QIDQ1912794

Ji{ří} Matoušek

Publication date: 21 November 1996

Published in: Israel Journal of Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf02761110

zbMATH Keywords

distortionfinite metric spacesminimum dimension\(D\)-embedding

Mathematics Subject Classification ID

Geometry and structure of normed linear spaces (46B20) Local theory of Banach spaces (46B07)

Related Items (29)

The Johnson-Lindenstrauss lemma almost characterizes Hilbert space, but not quite ⋮ Limitations to Fréchet's metric embedding method ⋮ A Hierarchy of Lower Bounds for Sublinear Additive Spanners ⋮ Optimal (Euclidean) Metric Compression ⋮ On embedding expanders into \(\ell_p\) spaces ⋮ Terminal embeddings ⋮ Lossless Prioritized Embeddings ⋮ Near isometric terminal embeddings for doubling metrics ⋮ Efficient Oracles and Routing Schemes for Replacement Paths ⋮ Diversity-normed spaces and diversity embeddings ⋮ A nonlinear approach to dimension reduction ⋮ Proximinality and uniformly approximable sets in \(L^p\) ⋮ Labelings vs. embeddings: on distributed and prioritized representations of distances ⋮ \( \varepsilon \)-isometric dimension reduction for incompressible subsets of \(\ell_p\) ⋮ Bounds on Dimension Reduction in the Nuclear Norm ⋮ On embedding trees into uniformly convex Banach spaces ⋮ Advances in metric embedding theory ⋮ Embedding metric spaces into normed spaces and estimates of metric capacity ⋮ Low Distortion Metric Embedding into Constant Dimension ⋮ Distance Oracles for Vertex-Labeled Graphs ⋮ Shortest-path queries in static networks ⋮ Ramsey partitions and proximity data structures ⋮ Impossibility of dimension reduction in the nuclear norm ⋮ Improved Guarantees for Vertex Sparsification in Planar Graphs ⋮ Unnamed Item ⋮ An average John theorem ⋮ Approximation Algorithms for Low-Distortion Embeddings into Low-Dimensional Spaces ⋮ Near Isometric Terminal Embeddings for Doubling Metrics ⋮ On approximate nearest neighbors under \(l_\infty\) norm

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The metrical interpretation of superreflexivity in Banach spaces
• On Lipschitz embedding of finite metric spaces in Hilbert space
• Ramanujan graphs
• Finite metric spaces needing high dimension for Lipschitz embeddings in Banach spaces
• The geometry of graphs and some of its algorithmic applications
• Extensions of Lipschitz mappings into a Hilbert space
• On Type of Metric Spaces
• Minimal Regular Graphs of Girths Eight and Twelve
• On the Betti Numbers of Real Varieties

This page was built for publication: On the distortion required for embedding finite metric spaces into normed spaces