William B. Johnson and Joram Lindenstrauss (1984), “Extensions of Lipschitz mappings into a Hilbert space”, in Conference in Modern Analysis and Probability, Contemporary Mathematics 26: 189–206 — doi:10.1090/conm/026/737400
Key takeaways
From the reading, NOTE-930.
- Lemma 1, as stated. For each 1 > τ > 0 there is K = K(τ) > 0 such that if A ⊂ ℓ₂ⁿ and card A = n, some f maps A onto a subset of ℓ₂ᵏ, k = [K log n], with ‖f‖_lip ‖f⁻¹‖_lip ≤ (1+τ)/(1−τ). The map is a random rank-k orthogonal projection U*QU, U Haar on O(n), and it works with positive probability, which can be pushed towards one by raising k.
- Where τ⁻² comes from. Only the proof. The failure probability is at most 2n(n+1) exp(−τ²K log n/18), “positive if, say, K ≥ (10/τ)²”, so k = [100 τ⁻² log n] suffices.
- How the proof works. It concentrates the norm r(Uy) = √n‖QUy‖ of one projected unit vector about its median, with tail 4 exp(−nε²/2), by Lévy’s isoperimetric inequality as used in Figiel, Lindenstrauss and Milman (1977). Khintchine’s inequality puts the mean between √(k/2) and √k, and the median within a constant of it. A union bound over the at most n(n−1) normalized differences finishes it.
- What is tight. The log n: k dimensions hold at most 4ᵏ vectors at mutual distance ≥ 1 in a ball of radius 2, so an orthonormal set of more than 4ᵏ vectors cannot go into k dimensions with small distortion. The paper says nothing about the dependence on τ.
- What it was for. Theorem 1: every Lipschitz f from an n-point subset of a metric space into ℓ₂ extends with ‖f̃‖_lip ≤ K√(log n) ‖f‖_lip, by Lemma 1 with τ = 1/2, Kirszbraun’s theorem, and the non-linear Hahn–Banach theorem in ℓ∞ᵏ, which costs √k.
- The rest. L(p, n) ≥ δ(Log n / Log Log n)^{1/p−1/2} for 1 ≤ p < 2 (Theorem 3). Extensions from ε-separated sets of diameter D cost at most 6D/ε into ℓ₂ (Theorem 2), and 4D/ε into any Banach space (Benyamini, in the appendix). An ε-net on the unit sphere of an n-dimensional space has at most (1 + 4/ε)ⁿ points (Lemma 3).
Standing in the record
Filed on 2026-10-14 as the anchor for QUESTION-120, and read the same day in NOTE-930. The record held three uses of random projections and not the lemma usually given for why they work: random features for kernels (LIT-679, THEORY-106), the compressed-sensing bound in Toy Models of Superposition (NOTE-278), and the thresholded random projections of sparse distributed memory (NOTE-242) and the insect olfactory code (NOTE-670).
The reading bears on the question’s distances thread. The proof has the shape the question proposes: a threshold of order log of the family’s size over a squared tolerance, here τ⁻² log n from a union bound over point pairs. It says nothing about random features or expand-and-threshold maps. Its Lemma 3 net is the other ingredient a union bound over sparse supports needs, which bears on the superposition thread. Its later proofs are LIT-1157 and LIT-1159, and Indyk and Motwani’s Gaussian proof of a JL-type lemma, read for nearest-neighbour search (LIT-1106, NOTE-905, Appendix A). The order ε⁻² log n is shown necessary for some point set, up to a constant and for ε above about 1/√min{n, d}, in LIT-1154 (NOTE-925). This paper proves only that the log n cannot be improved, and does not state the ε⁻².
In the anthology the lemma appears without a LIT of its own, inside Linformer’s low-rank argument (ANTH-LIT-529). The subject is mathematics, which no anthology topic holds.
Filed, with LIT-1157 and LIT-1159, as THEORY-397. Its own main results, the extension theorems, are filed as THEORY-392 and THEORY-398.