Source
Johnson and Lindenstrauss (1984), LIT-1153, Theorem 2 (p. 195) and Benyamini’s appendix (p. 205), read in NOTE-930. Filed for later use; it answers no question of the record’s yet.
What was actually shown
Theorem 2. If A ⊂ X has d(x, y) ≥ ε > 0 for all x ≠ y in A and diameter D, every Lipschitz f: A → ℓ₂ extends to f̃: X → ℓ₂ with ‖f̃‖_lip ≤ (6D/ε)‖f‖_lip. The proof factors the map through ℓ₁ on the points of A and, by a weak form of Grothendieck’s inequality, through ℓ∞ with ‖H‖ ≤ 3‖G‖.
Benyamini’s version. The same holds with any Banach space Z in place of ℓ₂, with ‖f̃‖_lip ≤ (4D/ε)‖f‖_lip. Lemma 6 gives a retraction of ℓ∞(Γ) onto the positive part of the ℓ₁(Γ) ball with Lipschitz constant at most 2, and a map H into {αe_γ} with ‖H‖_lip ≤ 4.
What could have come out otherwise. A separated set and a map into some Banach space with no extension of constant 4D/ε would refute the appendix. Both proofs were read in the reading.
What this does not say
- That the constants are best possible. The paper does not discuss it.
- Anything for sets that are not separated. As ε goes to 0 the bound is vacuous; the bound in n is THEORY-392’s.
- Anything about random projections. Neither proof uses Lemma 1.
Connections
- THEORY-400 and THEORY-396: Lee and Naor’s bounds in terms of random partitions, doubling and the number of points. They do not cite this theorem. Their reading observes that the bounds are incomparable with 4D/ε, and that 4D/ε for every superspace and Banach target is already an absolute extendability bound, which their §1.2 does not count (NOTE-927, the reader’s observation).
- THEORY-392: the paper’s bound in terms of the number of points. The two together say an extension constant can be paid for either by how many points there are or by how spread out they are.