nucleation

LIT-1152: Extending Lipschitz functions via random metric partitions

3 min read

Properties6
StatusActive — read 2026-10-16 (NOTE-927) in full; worth reading as the method that turns random metric partitions into Lipschitz extensions: padded random partitions at every scale give a gentle partition of unity, and averaging over it extends maps into any Banach space at a constant depending on the domain alone. Read it knowing that its bound for n-point domains, C log n/log log n, improves Johnson, Lindenstrauss and Schechtman's C log n for Banach targets but not Johnson and Lindenstrauss's K√(log n) for Hilbert targets; that it states as open whether √(log n) suffices for every target; that the copy read is the January 2004 preprint; and that it does not discuss separated domains. Filed as THEORY-396 and THEORY-400.
Version2
Tagsmathematics
ExtendsLIT-1153 — Extensions of Lipschitz mappings into a Hilbert space
Cited as “paper” byNOTE-927 — Lee & Naor — extending Lipschitz functions via random metric partitions
Cited as “source” byTHEORY-396 — Every Lipschitz map from an n-point metric space into any Banach space extends to any containing space with Lipschitz constant at most C log n/log log n times its own, by averaging over random partitions at every scale, and every n-point subset of L₂ extends into any Banach space at C√(log n) after Johnson–Lindenstrauss dimension reduction; for maps into Hilbert space this is no improvement on K√(log n), and whether √(log n) suffices for every target is left open, THEORY-400 — A metric space that admits, at every scale, random partitions into small pieces with each point padded away from piece boundaries with constant probability is absolutely Lipschitz extendable: maps from it into any Banach space extend to any containing space at O(1/padding), which gives C log λ for doubling constant λ, C r² for K_r-minor-free graph metrics, C(g+1) on genus-g surfaces and C√d from ℓ₂ᵈ; the bounds are upper bounds only, and the method needs a decomposition the domain may not have

Graph View

James R. Lee and Assaf Naor (2005), “Extending Lipschitz functions via random metric partitions”, Inventiones Mathematicae 160(1): 59–95 — doi:10.1007/s00222-004-0400-5

Key takeaways

From the reading, NOTE-927.

  • The method (Lemma 2.1, Theorem 4.1). A K-gentle partition of unity gives extensions of constant 3K into any Banach space, linear in the map. (ε, δ)-padded random partitions at every scale give K = O(1/(εδ)), and Lemma 3.8 moves them from X to any superspace.
  • Absolute extendability. ae(X), the extension constant over every superspace and every Banach target, depends on X alone. Theorem 5.1: ae(X) ≤ C log λ(X) for doubling X; ≤ C r² for K_r-minor-free graph metrics; ≤ C(g+1) on genus-g surfaces; e(ℓ₂ᵈ, Z) ≤ C√d.
  • n points (Theorem 1.10). ae(X) ≤ C log n/log log n, improving Johnson, Lindenstrauss and Schechtman’s C log n by spreading the smoothing over about log log n scales. For Banach targets only.
  • Hilbert domains (Theorem 1.12). eₙ(L_p, Z) ≤ C(p)(log n)^{1/p} for 1 < p ≤ 2, C√(log n) at p = 2, by Johnson–Lindenstrauss dimension reduction to d of order log n and e(ℓ₂ᵈ, Z) ≤ C√d, averaged over the random map.
  • A lower bound (Lemma 1.13, sketched). eₙ(L₂, L_p) ≥ C(log n/log log n)^{(p−2)/p²} for 2 < p < ∞, so supₙ eₙ(L₂, Z) can be infinite.
  • Open (§1.4). Whether eₙ(X, Z) = O(√(log n)) for every metric X and normed Z: “All known lower bounds fail to beat the ’√(log n) barrier.’”
  • Scope. Constants are universal and unspecified; Theorem 1.10 does not extend to barycentric targets; the excluded-minor results are sketched; separated domains are not discussed.

Standing in the record

Filed on 2026-10-16 as later work on the extension problem of Johnson and Lindenstrauss’s Theorem 1 (THEORY-392), and read the same day in NOTE-927. The registration placed it as the work on the sharpness Johnson and Lindenstrauss left open. The reading corrects that. For maps from n points into Hilbert space the paper’s bound, C log n/log log n, is weaker than their K√(log n); what it improves is the bound for arbitrary Banach targets, and it states the √(log n) question as open in a wider form. Its √(log n) for Hilbert domains into any Banach space (Theorem 1.12) is the dual of their Theorem 1 and uses their lemma. It says nothing about separated domains (THEORY-398); the reading notes that Benyamini’s 4D/ε there is itself an absolute extendability bound that the paper’s §1.2 overlooks. Filed as THEORY-396 and THEORY-400. For QUESTION-120 it is marginal: the random linear map in Theorem 1.12 needs its lower side for every pair and its upper side only on average. The paper is mathematics, not ML practice.

Backlinks