On Lipschitz embedding of finite metric spaces in Hilbert space

DOI10.1007/BF02776078zbMath0657.46013WikidataQ97309166 ScholiaQ97309166MaRDI QIDQ1110768

Publication date: 1985

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

Random graphs (graph-theoretic aspects) (05C80) Normed linear spaces and Banach spaces; Banach lattices (46B99) Homotopy and topological questions for infinite-dimensional manifolds (58B05)

Related Items (only showing first 100 items - show all)

New types of Lipschitz summing maps between metric spaces ⋮ Geometric complexity of embeddings in $\mathbb R^d$ ⋮ Metric violation distance: hardness and approximation ⋮ The Range of Topological Effects on Communication ⋮ Warped cones and spectral gaps ⋮ The geometry of graphs and some of its algorithmic applications ⋮ The Johnson-Lindenstrauss lemma almost characterizes Hilbert space, but not quite ⋮ Coarse differentiation and multi-flows in planar graphs ⋮ $\ell ^2_2$ spreading metrics for vertex ordering problems ⋮ Limitations to Fréchet's metric embedding method ⋮ Vertical perimeter versus horizontal perimeter ⋮ Metric Embedding via Shortest Path Decompositions ⋮ Semidefinite programming in combinatorial optimization ⋮ A linguistic approach to classification of bacterial genomes ⋮ On the distortion required for embedding finite metric spaces into normed spaces ⋮ Markov type and threshold embeddings ⋮ Randomized nonlinear projections uncover high-dimensional structure ⋮ Negative-type diversities, a multi-dimensional analogue of negative-type metrics ⋮ On embedding expanders into $\ell_p$ spaces ⋮ Terminal embeddings ⋮ Lossless Prioritized Embeddings ⋮ Near isometric terminal embeddings for doubling metrics ⋮ Prioritized Metric Structures and Embedding ⋮ Metric differentiation, monotonicity and maps to $L^{1}$ ⋮ Efficient Oracles and Routing Schemes for Replacement Paths ⋮ Proximity-preserving labeling schemes ⋮ Bandwidth and low dimensional embedding ⋮ Optimal stable nonlinear approximation ⋮ Diversity-normed spaces and diversity embeddings ⋮ An introduction to the Ribe program ⋮ Distance geometry and data science ⋮ Lipschitz-free Spaces on Finite Metric Spaces ⋮ Compression bounds for Lipschitz maps from the Heisenberg group to $L_{1}$ ⋮ Compression of uniform embeddings into Hilbert space. ⋮ Lipschitz $(q, p)$-summing maps from $C(K)$-spaces to metric spaces ⋮ Expander graphs and their applications ⋮ The Excluded Minors for Isometric Realizability in the Plane ⋮ Lipschitz $p$-integral operators and Lipschitz $p$-nuclear operators ⋮ Metric Curvatures Revisited: A Brief Overview ⋮ Euclidean distortion and the sparsest cut ⋮ Diameters, distortion, and eigenvalues ⋮ Hilbert space compression for free products and HNN-extensions. ⋮ Volume in general metric spaces ⋮ On embedding trees into uniformly convex Banach spaces ⋮ Obituary: On the mathematical contributions of Joram Lindenstrauss ⋮ Cellular resolutions of cointerval ideals ⋮ The complexity of some topological inference problems ⋮ On average distortion of embedding metrics into the line ⋮ Compressive sensing using chaotic sequence based on Chebyshev map ⋮ Polynomial-sized topological approximations using the permutahedron ⋮ Combinatorial theorems about embedding trees on the real line ⋮ Uniform estimates of nonlinear spectral gaps ⋮ Optimal distortion embeddings of distance regular graphs into Euclidean spaces ⋮ Comparison of Metric Spectral Gaps ⋮ Improved approximate Rips filtrations with shifted integer lattices and cubical complexes ⋮ Low Distortion Metric Embedding into Constant Dimension ⋮ Quantitative bi-Lipschitz embeddings of bounded-curvature manifolds and orbifolds ⋮ Fréchet embeddings of negative type metrics ⋮ L ^p -distortion and p -spectral gap of finite graphs ⋮ Remarks on Lipschitz 𝑝-summing operators ⋮ Nonlinear spectral calculus and super-expanders ⋮ One-way permutations, computational asymmetry and distortion. ⋮ Randomized large distortion dimension reduction ⋮ Isometric embedding of Busemann surfaces into $L_1$ ⋮ Ultrametric skeletons ⋮ Euclidean quotients of finite metric spaces ⋮ Shortest-path queries in static networks ⋮ Simultaneous spotting of signs and fingerspellings based on hierarchical conditional random fields and boostmap embeddings ⋮ Nonembeddability theorems via Fourier analysis ⋮ Distortion lower bounds for line embeddings ⋮ Snowflake universality of Wasserstein spaces ⋮ Inapproximability for metric embeddings into $\mathbb{R}^{d}$ ⋮ Unavoidable minors for graphs with large $\ell_p$-dimension ⋮ Impossibility of dimension reduction in the nuclear norm ⋮ Fast embedding methods for clustering tens of thousands of sequences ⋮ Subspace projection: A unified framework for a class of partition-based dimension reduction techniques ⋮ Summarization and Search Over Geometric Spaces ⋮ Finite metric spaces needing high dimension for Lipschitz embeddings in Banach spaces ⋮ Book Review: Metric embeddings: bilipschitz and coarse embedddings into Banach spaces ⋮ An average John theorem ⋮ Volume distortion for subsets of Euclidean spaces ⋮ Bandwidth and Low Dimensional Embedding ⋮ Low distortion Euclidean embeddings of trees ⋮ Poincaré inequalities, embeddings, and wild groups ⋮ Multicommodity flows and cuts in polymatroidal networks ⋮ Lipschitz $p$-summing operators ⋮ DIAMOND GRAPHS AND SUPER-REFLEXIVITY ⋮ On notions of distortion and an almost minimum spanning tree with constant average distortion ⋮ Chemical subdiffusivity of critical 2D percolation ⋮ Conformal growth rates and spectral geometry on distributional limits of graphs ⋮ Separators in region intersection graphs ⋮ Approximating the bandwidth via volume respecting embeddings ⋮ Lipschitz $(q,p)$-mixing operators ⋮ Interpolation, the rudimentary geometry of spaces of Lipschitz functions, and geometric complexity ⋮ The Unique Games Conjecture, Integrality Gap for Cut Problems and Embeddability of Negative-Type Metrics into ℓ ₁ ⋮ Approximation Algorithms for Low-Distortion Embeddings into Low-Dimensional Spaces ⋮ Near Isometric Terminal Embeddings for Doubling Metrics ⋮ Least-distortion Euclidean embeddings of graphs: Products of cycles and expanders ⋮ The least Euclidean distortion constant of a distance-regular graph ⋮ On approximate nearest neighbors under $l_\infty$ norm

Cites Work

This page was built for publication: On Lipschitz embedding of finite metric spaces in Hilbert space