Euclidean embedding, randomized clustering, and Lipschitz extension for finite and doubling subsets of L_p when p>2

2025/02/14 by Assaf Naor, Naor, Assaf, Kevin Ren +1 · 1 citation
Computer Science · #Advanced Mathematical Modeling in Engineering #FOS: Mathematics #Functional Analysis (math.FA) #Metric Geometry (math.MG)

paper · pdf · doi:10.48550/arxiv.2502.10543

openalex publication_date 2025/02/14 · openalex created_date 2025/02/19 · openalex updated_date 2026/07/28

Abstract

Fix p>2. We prove that the Euclidean distortion of every n-point subset of L_p is p³(log n)^\frac12+o(1), thus, in particular, demonstrating that all n-point subsets of L_p exhibit an asymptotic improvement over the O(log n) Euclidean distortion guarantee that Bourgain's embedding theorem provides for arbitrary n-point metric spaces. We also prove that the separation modulus of every n-point subset of L_p is O(p²√(log n)), which is sharp up to the dependence on p. We deduce from (a refinement of) this asymptotic evaluation of the finitary separation modulus of L_p that for any n-point subset C of L_p, any Banach space Z, and any 1-Lipschitz function f:C→ Z, there exists a O(p²√(log n))-Lipschitz function F:L_p→ Z that extends f. We obtain analogous separation and extension statements for doubling subsets of L_p.

Cited by

• The separation modulus of unitarily invariant matrix norms

Related

• Extension, separation and isomorphic reverse isoperimetry
• On Lipschitz extension from finite subsets
• Linear Lipschitz and C¹ extension operators through random projection
• A doubling subset of L_p for p>2 that is inherently infinite dimensional
• Log-Lipschitz embeddings of homogeneous sets with sharp logarithmic exponents and slicing the unit cube