Literature
Display
← All papers

Extensions of Lipschitz Mappings into a Hilbert Space

William B. Johnson · Joram Lindenstrauss

Published · Contemporary Mathematics 26, 189–206 ↗

Contents

Introduction · Extension constants

Intuition. Imagine a calibration function defined only at measured inputs. A Lipschitz condition says nearby inputs cannot produce wildly different outputs: the output distance is at most a fixed multiple of the input distance. The paper asks how much that multiplier must increase when the function is extended to unmeasured inputs.

Reading the math. Hilbert space generalizes Euclidean vector geometry, retaining an inner product for lengths and angles. A key tool replaces n high-dimensional points with shorter vectors while approximately preserving every pairwise distance. The required dimension grows logarithmically with n, with extra dimensions for tighter accuracy. This finite-set guarantee is not a neural-network storage-capacity formula.

The problem is to extend a Lipschitz map from n points in an arbitrary metric space to the whole space when the target is Hilbert space. L(X,n) measures the worst multiplicative increase in Lipschitz constant. Kirszbraun’s theorem gives constant one for Hilbert domains; general domains can force growth.

The main theorem bounds that cost by a universal constant times the square root of log n. Finite-set dimension reduction is its main tool. The paper also proves lower bounds, studies separated-domain extensions, poses historical questions, and includes an appendix credited to Yoav Benyamini. Its scope is broader than the familiar dimension-reduction lemma.

Equations PDF p.1 · display 1–PDF p.1 · display 3
(PDF p.1 · display 1)Original mathematical display 1, PDF page 1
(PDF p.1 · display 2)Original mathematical display 2, PDF page 1
(PDF p.1 · display 3)Original mathematical display 3, PDF page 1

Introduction · Notation and comparison bounds

The authors use Log x for the maximum of one and the natural logarithm. Balls, unit spheres, the uniform norm of a bounded function, and Banach–Mazur distance are defined before the main argument.

For 1≤p<2, the proposed sharp extension growth remains unresolved in this paper. Its lower bound includes a log log n denominator, whereas the comparison upper bound has the corresponding power of log n alone. Those directions and exponents matter when comparing the theorems.

Equations PDF p.2 · display 4–PDF p.2 · display 7
(PDF p.2 · display 4)Original mathematical display 4, PDF page 2
(PDF p.2 · display 5)Original mathematical display 5, PDF page 2
(PDF p.2 · display 6)Original mathematical display 6, PDF page 2
(PDF p.2 · display 7)Original mathematical display 7, PDF page 2

1 · Lemma 1: finite Euclidean dimension reduction

For a fixed distortion tolerance, an n-point Euclidean set maps to dimension at most a tolerance-dependent constant times log n while controlling every pairwise distance through the displayed two-sided Lipschitz bound. The original ambient dimension disappears from the final bound.

The proof samples a rank-k projection by conjugating a coordinate projection with a Haar-random orthogonal matrix. Concentration on the sphere controls each normalized difference vector; a union bound controls all pairs. It proves existence of a suitable finite-set map, rather than success for every projection or arbitrary learned representation.

Equations PDF p.3 · display 8–PDF p.3 · display 14
(PDF p.3 · display 8)Original mathematical display 8, PDF page 3
(PDF p.3 · display 9)Original mathematical display 9, PDF page 3
(PDF p.3 · display 10)Original mathematical display 10, PDF page 3
(PDF p.3 · display 11)Original mathematical display 11, PDF page 3
(PDF p.3 · display 12)Original mathematical display 12, PDF page 3
(PDF p.3 · display 13)Original mathematical display 13, PDF page 3
(PDF p.3 · display 14)Original mathematical display 14, PDF page 3

1 · Concentration, scale and logarithmic dimension

A scaled projection seminorm concentrates around its median. The proof relates median and mean, then estimates the mean with rotational invariance and Khintchine’s inequality. Its typical scale is the square root of k, turning an additive concentration window into relative distortion.

Taking k proportional to the tolerance-dependent log n makes the failure bound less than one. A packing argument then shows logarithmic dimension is necessary for fixed sufficiently small distortion: a bounded k-dimensional ball cannot contain arbitrarily many separated images of an orthonormal set. This does not itself establish exponential storage of independently readable semantic concepts in a neural model.

Equations PDF p.4 · display 15–PDF p.5 · display 30
(PDF p.4 · display 15)Original mathematical display 15, PDF page 4
(PDF p.4 · display 16)Original mathematical display 16, PDF page 4
(PDF p.4 · display 17)Original mathematical display 17, PDF page 4
(PDF p.4 · display 18)Original mathematical display 18, PDF page 4
(PDF p.4 · display 19)Original mathematical display 19, PDF page 4
(PDF p.4 · display 20)Original mathematical display 20, PDF page 4
(PDF p.4 · display 21)Original mathematical display 21, PDF page 4
(PDF p.4 · display 22)Original mathematical display 22, PDF page 4
(PDF p.4 · display 23)Original mathematical display 23, PDF page 4
(PDF p.5 · display 24)Original mathematical display 24, PDF page 5
(PDF p.5 · display 25)Original mathematical display 25, PDF page 5
(PDF p.5 · display 26)Original mathematical display 26, PDF page 5
(PDF p.5 · display 27)Original mathematical display 27, PDF page 5
(PDF p.5 · display 28)Original mathematical display 28, PDF page 5
(PDF p.5 · display 29)Original mathematical display 29, PDF page 5
(PDF p.5 · display 30)Original mathematical display 30, PDF page 5

1 · Theorem 1: extending into Hilbert space

Dimension reduction first places the n image points in a controlled k-dimensional Euclidean configuration. Coordinatewise extension through an infinity-norm space handles the arbitrary metric domain; comparison of finite-dimensional norms costs a square root of k. Kirszbraun’s theorem controls reconstruction into the Hilbert target.

Combining these steps gives the square-root-of-log-n extension bound. The construction extends a specified finite map; it does not assert a low-dimensional linear extension on the whole original ambient space.

Equations PDF p.6 · display 31–PDF p.6 · display 39
(PDF p.6 · display 31)Original mathematical display 31, PDF page 6
(PDF p.6 · display 32)Original mathematical display 32, PDF page 6
(PDF p.6 · display 33)Original mathematical display 33, PDF page 6
(PDF p.6 · display 34)Original mathematical display 34, PDF page 6
(PDF p.6 · display 35)Original mathematical display 35, PDF page 6
(PDF p.6 · display 36)Original mathematical display 36, PDF page 6
(PDF p.6 · display 37)Original mathematical display 37, PDF page 6
(PDF p.6 · display 38)Original mathematical display 38, PDF page 6
(PDF p.6 · display 39)Original mathematical display 39, PDF page 6

1 · Theorem 2: separated domains

A domain subset with minimum separation ε and finite diameter D admits an extension with cost bounded by 6 D/ε. The proof factors the map through a coordinate-indexed sequence space, uses a weak Grothendieck inequality, and extends an infinity-norm-valued map coordinatewise.

This limits a lower-bound strategy using coarse nets of a sphere. A coarse separated net already admits a controlled extension, so a hard linear projection problem cannot automatically be recovered from every coarse nonlinear approximation.

Equations PDF p.7 · display 40–PDF p.8 · display 50
(PDF p.7 · display 40)Original mathematical display 40, PDF page 7
(PDF p.7 · display 41)Original mathematical display 41, PDF page 7
(PDF p.7 · display 42)Original mathematical display 42, PDF page 7
(PDF p.7 · display 43)Original mathematical display 43, PDF page 7
(PDF p.7 · display 44)Original mathematical display 44, PDF page 7
(PDF p.7 · display 45)Original mathematical display 45, PDF page 7
(PDF p.7 · display 46)Original mathematical display 46, PDF page 7
(PDF p.8 · display 47)Original mathematical display 47, PDF page 8
(PDF p.8 · display 48)Original mathematical display 48, PDF page 8
(PDF p.8 · display 49)Original mathematical display 49, PDF page 8
(PDF p.8 · display 50)Original mathematical display 50, PDF page 8

1 · Lemmas 2–4: tools for the lower bound

Lemma 2 extends a sphere map by positive homogeneity, controlling its Lipschitz constant through its sphere Lipschitz and uniform norms. Lemma 3 obtains an ε-net of cardinality at most the displayed exponential function of dimension by comparing volumes of disjoint small balls.

Lemma 4 supplies nearly Euclidean finite-dimensional subspaces of Lp,1≤p<2, that have large projection constants. They furnish an obstruction: turning an accurate nonlinear extension into a low-norm linear projection would contradict that lower bound.

Equations PDF p.8 · display 51–PDF p.10 · display 64
(PDF p.8 · display 51)Original mathematical display 51, PDF page 8
(PDF p.8 · display 52)Original mathematical display 52, PDF page 8
(PDF p.8 · display 53)Original mathematical display 53, PDF page 8
(PDF p.9 · display 54)Original mathematical display 54, PDF page 9
(PDF p.9 · display 55)Original mathematical display 55, PDF page 9
(PDF p.9 · display 56)Original mathematical display 56, PDF page 9
(PDF p.9 · display 57)Original mathematical display 57, PDF page 9
(PDF p.9 · display 58)Original mathematical display 58, PDF page 9
(PDF p.9 · display 59)Original mathematical display 59, PDF page 9
(PDF p.9 · display 60)Original mathematical display 60, PDF page 9
(PDF p.9 · display 61)Original mathematical display 61, PDF page 9
(PDF p.9 · display 62)Original mathematical display 62, PDF page 9
(PDF p.10 · display 63)Original mathematical display 63, PDF page 10
(PDF p.10 · display 64)Original mathematical display 64, PDF page 10

1 · Proposition 1: linearizing a Lipschitz approximation

The proposition converts a Lipschitz approximation to a bounded linear operator on a subspace into an operator between dual spaces with controlled norm and restriction error. For a reflexive target, an adjoint gives a map back into the original target.

The proof uses norm-one projections from scalar Lipschitz-function spaces onto ordinary dual spaces and their compatibility with restriction. This connects the nonlinear extension problem to linear projection obstructions; pointwise approximation alone would not give that connection.

Equations PDF p.10 · display 65–PDF p.11 · display 72
(PDF p.10 · display 65)Original mathematical display 65, PDF page 10
(PDF p.10 · display 66)Original mathematical display 66, PDF page 10
(PDF p.10 · display 67)Original mathematical display 67, PDF page 10
(PDF p.10 · display 68)Original mathematical display 68, PDF page 10
(PDF p.10 · display 69)Original mathematical display 69, PDF page 10
(PDF p.11 · display 70)Original mathematical display 70, PDF page 11
(PDF p.11 · display 71)Original mathematical display 71, PDF page 11
(PDF p.11 · display 72)Original mathematical display 72, PDF page 11

1 · Lemma 5: smoothing a homogeneous map

Averaging a homogeneous Lipschitz map over the unit ball of a finite-dimensional subspace controls its regularity on that subspace. Comparing overlaps of translated balls turns uniform approximation on a sphere into Lipschitz approximation.

The estimates retain dimension factors and constants. A final homogeneous extension gives a globally defined controlled map. This supplies the regularity needed before Proposition 1 can be used in the lower-bound argument.

Equations PDF p.11 · display 73–PDF p.13 · display 84
(PDF p.11 · display 73)Original mathematical display 73, PDF page 11
(PDF p.11 · display 74)Original mathematical display 74, PDF page 11
(PDF p.11 · display 75)Original mathematical display 75, PDF page 11
(PDF p.11 · display 76)Original mathematical display 76, PDF page 11
(PDF p.12 · display 77)Original mathematical display 77, PDF page 12
(PDF p.12 · display 78)Original mathematical display 78, PDF page 12
(PDF p.12 · display 79)Original mathematical display 79, PDF page 12
(PDF p.12 · display 80)Original mathematical display 80, PDF page 12
(PDF p.12 · display 81)Original mathematical display 81, PDF page 12
(PDF p.12 · display 82)Original mathematical display 82, PDF page 12
(PDF p.13 · display 83)Original mathematical display 83, PDF page 13
(PDF p.13 · display 84)Original mathematical display 84, PDF page 13

1 · Theorem 3: the Lp lower bound

For 1≤p<2, the extension cost is at least an absolute constant times (log n/log log n) raised to 1/p−1/2. The proof chooses a nearly Euclidean subspace with a large projection constant, takes a sufficiently fine finite net, extends its identity map, then homogenizes, smooths and linearizes.

The net must be fine enough that the resulting linear approximation yields an actual projection. Balancing that accuracy requirement with net cardinality produces the log log n term. The gap to the upper bound remains explicit in this 1984 article.

Equations PDF p.13 · display 85–PDF p.14 · display 94
(PDF p.13 · display 85)Original mathematical display 85, PDF page 13
(PDF p.13 · display 86)Original mathematical display 86, PDF page 13
(PDF p.13 · display 87)Original mathematical display 87, PDF page 13
(PDF p.13 · display 88)Original mathematical display 88, PDF page 13
(PDF p.13 · display 89)Original mathematical display 89, PDF page 13
(PDF p.13 · display 90)Original mathematical display 90, PDF page 13
(PDF p.13 · display 91)Original mathematical display 91, PDF page 13
(PDF p.14 · display 92)Original mathematical display 92, PDF page 14
(PDF p.14 · display 93)Original mathematical display 93, PDF page 14
(PDF p.14 · display 94)Original mathematical display 94, PDF page 14

2 · Four open problems posed in 1984

The questions concern sharp extension growth, nonlinear analogues of linear Lp extension results on either side of p=2, dimension reduction beyond Hilbert spaces, and controlled Hilbert embeddings of arbitrary finite metric spaces. These are recorded as historical questions; no claim is made that they all remain open today.

The final question proposes square-root-of-log-n distortion. A preceding proposed finite-dimensional Banach embedding would imply it, and a cube inequality motivates sharpness if the asserted embedding exists. These conjectural directions are separate from the consequences already proved by Lemma 1.

Equations PDF p.14 · display 95–PDF p.15 · display 100
(PDF p.14 · display 95)Original mathematical display 95, PDF page 14
(PDF p.14 · display 96)Original mathematical display 96, PDF page 14
(PDF p.15 · display 97)Original mathematical display 97, PDF page 15
(PDF p.15 · display 98)Original mathematical display 98, PDF page 15
(PDF p.15 · display 99)Original mathematical display 99, PDF page 15
(PDF p.15 · display 100)Original mathematical display 100, PDF page 15

3 · Benyamini’s appendix: the retraction lemma

The appendix replaces the Hilbert target in the separated-domain theorem by any Banach space. It builds a controlled retraction from an infinity-norm space onto the positive part of an ℓ1 unit ball, then a controlled map onto its coordinate segments.

A threshold subtracts the same scalar from positive coordinates until the remaining ℓ1 mass is at most one. A second threshold leaves at most one active coordinate. The displayed formulas prove Lipschitz bounds and fix coordinate basis vectors. Benyamini’s contribution is explicitly credited.

Equations PDF p.16 · display 101–PDF p.16 · display 110
(PDF p.16 · display 101)Original mathematical display 101, PDF page 16
(PDF p.16 · display 102)Original mathematical display 102, PDF page 16
(PDF p.16 · display 103)Original mathematical display 103, PDF page 16
(PDF p.16 · display 104)Original mathematical display 104, PDF page 16
(PDF p.16 · display 105)Original mathematical display 105, PDF page 16
(PDF p.16 · display 106)Original mathematical display 106, PDF page 16
(PDF p.16 · display 107)Original mathematical display 107, PDF page 16
(PDF p.16 · display 108)Original mathematical display 108, PDF page 16
(PDF p.16 · display 109)Original mathematical display 109, PDF page 16
(PDF p.16 · display 110)Original mathematical display 110, PDF page 16

3 · Completing the Banach-target extension

Map the separated set to coordinate basis vectors, assigning one point to zero, and extend that map coordinatewise in an infinity-norm space. Extend the target-valued map linearly along the coordinate segments and compose with the appendix’s controlled segment map.

The resulting 4 D/ε bound does not require Hilbert structure in the target. The edition follows the full 18-page article, including proofs, appendix and fourteen references. It preserves standalone mathematical displays from the original scan at native pixel resolution, excludes download footers, and condenses source prose rather than reproducing full text columns.

Equations PDF p.17 · display 111–PDF p.17 · display 117
(PDF p.17 · display 111)Original mathematical display 111, PDF page 17
(PDF p.17 · display 112)Original mathematical display 112, PDF page 17
(PDF p.17 · display 113)Original mathematical display 113, PDF page 17
(PDF p.17 · display 114)Original mathematical display 114, PDF page 17
(PDF p.17 · display 115)Original mathematical display 115, PDF page 17
(PDF p.17 · display 116)Original mathematical display 116, PDF page 17
(PDF p.17 · display 117)Original mathematical display 117, PDF page 17
Concept demonstration

Open image ↗