Functional analysis

Functional analysis brings linear algebra and topology together to study vector spaces of functions and the linear operators acting on them. A function space such as $C([0,1])$ has infinitely many independent directions: the monomials $1,x,x^2,\dots$ are linearly independent. Finite linear combinations alone cannot describe all its continuous functions. A useful theory must also say when approximations converge, whether their limits belong to the chosen space, and which operations preserve that norm convergence. Normed vector spaces, Banach spaces, and bounded linear operators provide these three controls.^[ref]

A bounded linear operator $T:X\to Y$ between normed vector spaces satisfies $\Vert Tf{\Vert }_Y\le M\Vert f{\Vert }_X$ for every $f$, with one finite constant $M$. The least possible constant is its operator norm. By linearity, the same estimate controls approximation errors:This is exactly continuity for a linear map between normed vector spaces; neither space needs to be complete. It turns an input accuracy guarantee into an output accuracy guarantee, even when the input has infinitely many degrees of freedom.^[ref]

For a concrete linear functional on $C([0,1])$, take the integral $F(f)={\int }_0^{1}f(x)dx$. In the supremum norm,The constant function $f=1$ attains equality, so $\Vert F\Vert =1$. For $f(x)=x^2$, the output is $F(f)=1/3$; any approximation $g$ with $\Vert g-x^2{\Vert }_{\infty }\le 0.01$ therefore has $|F(g)-1/3|\le 0.01$. The Cauchy-Schwarz inequality also gives $|F(f)|\le \Vert f{\Vert }_2\Vert 1{\Vert }_2=\Vert f{\Vert }_2$ on this interval, again with equality at $1$. Thus integration remains a bounded linear functional under the L2 norm, although point evaluation behaves very differently.

The beauty of this viewpoint is that one estimate can justify an entire approximation procedure. Once a sequence converges in the chosen norm, every bounded linear operator carries its limit along. Completeness ensures that Cauchy approximations actually describe an element of the space. The choice of norm matters: it determines which errors are small and which measurements are stable. The examples below distinguish an average, which ignores sufficiently narrow peaks, from point evaluation, which detects their full height. For applications, this decides whether reducing an overall fitting error guarantees an accurate reported measurement. A small L2 norm of the error controls its integral on this interval, while it gives no such guarantee for a single sampled value.

The Nemytskii operator associated with a scalar function $f$ applies $f$ pointwise to a function. The domain and target function spaces must be specified; an arbitrary continuous $f$ need not preserve them. On a finite-measure domain, a bounded continuous $f:\mathbb{R}\to \mathbb{R}$ defines a continuous map $N_f:L^2\to L^2$ with $\Vert N_f(u){\Vert }_2\le \Vert f{\Vert }_{\infty }|\Omega {|}^{1/2}$. To prove continuity, extract an almost-everywhere convergent further subsequence from every $L^2$-convergent subsequence and apply the dominated convergence theorem to $|f(u_j)-f(u){|}^2$. This forces convergence of the entire image sequence in $L^2$.

For normed vector spaces of functions on the same domain, a continuous embedding is an injective inclusion $X\subset Y$ satisfying $\Vert u{\Vert }_Y\le C\Vert u{\Vert }_X$.

A compact embedding of Banach spaces $X,Y$ is an injective continuous linear map $i:X\to Y$ that sends every bounded set to a relatively compact subset. Equivalently, every bounded sequence in $X$ has a subsequence converging in $Y$. One identifies $X$ with its image when $i$ is the natural inclusion. The Rellich-Kondrachov theorem supplies many compact embeddings between Sobolev spaces and Lp spaces on bounded domains.

A nonnegative function-valued operator $S$ is sublinear if $S(f+g)\le S(f)+S(g)$ and $S(cf)=|c|S(f)$ almost everywhere. This pointwise domination notion includes maximal one-sided interval averaging operators and differs from requiring an ordinary linear map.

An operator has weak type $(p,q)$, with finite $q$, if the displayed bound holds for every input and every $\lambda >0$, with one constant independent of both. It controls the distribution of its output rather than requiring its strong $L^q$ norm to be finite.

Let $S$ be a sublinear operator with positive constants and $\mu \{Sf>a\}\le C_1\Vert f{\Vert }_1/a$ and $\Vert Sf{\Vert }_{\infty }\le C_{\infty }\Vert f{\Vert }_{\infty }$. Split $f$ into its part above $a/(2C_{\infty })$ and its bounded remainder. The latter contributes at most $a/2$, so the weak bound controls the superlevel measure by $2C_1{a}^{-1}{\int }_{|f|>a/(2C_{\infty })}|f|$. Integrating this estimate with layer cake representation proves the displayed bound for $1<p<\infty$ and $q=p/(p-1)$. In particular it gives the strong $L^p$ estimate for the Hardy-Littlewood maximal function.

For a normed space $E$ and $0<q<\infty$, an operator $T:E\to L^0$ is of weak type $(E,q)$ when the displayed distribution bound holds uniformly over $f\in E$ and $a>0$. No completeness of $E$ is needed. A sublinear operator has pointwise triangle domination and absolute homogeneity; its outputs may be understood modulo almost everywhere equality.

Suppose linear operators $A_t$ and $A_0$ on a normed space satisfy $|A_{t}f|,|A_{0}f|\le Sf$, where $S$ has weak type with a normed domain, and all relevant suprema are measurable. If $A_{t}g\to A_{0}g$ almost everywhere on a dense subspace, the same holds for every input. For a fixed approximation $g$, the limiting error is at most $2S(f-g)$. The measure where it exceeds $a$ is at most $(2C\Vert f-g\Vert /a{)}^q$, which tends to zero as the approximation improves. This is a convergence-to-a-specified-limit version of almost-everywhere convergence from weak-type domination.

For a nonnegative sublinear operator, weak type $(1,1)$ is the displayed level-set bound for all integrable inputs and positive thresholds. It supplies an exceptional-set estimate for approximation errors; the uncentered maximal weak-type inequality is a central example.

Suppose a family of linear operators, including its limiting operator, is pointwise dominated by a sublinear operator of weak type (1,1). Convergence almost everywhere on an $L^1$-dense subspace then extends to every $L^1$ input. Approximate the input by errors of norm at most $2^{-2n}$. The weak estimate and the Borel-Cantelli first lemma make the corresponding domination errors tend to zero almost everywhere. Linearity bounds the difference between the full and approximating convergence errors by twice that domination error. This argument does not need an uncountable supremum to be measurable.

An operator algebra is an algebra of linear operators, with multiplication given by composition. In quantum examples it can be generated by creation and annihilation operators subject to the canonical commutation relations or canonical anticommutation relations. Its analytic realization requires specifying a common domain for unbounded operators.

For a lattice system, finite-region observable algebras ${\mathcal{A}}_{\Lambda }$ embed into larger ones by tensoring with the identity. Their union has a norm closure called the quasi-local observable algebra, a C-star algebra. It describes finite-support observables and norm limits of such observables. An operator flipping every spin of an infinite lattice need not belong to it: successive finite-region flips are not norm-Cauchy. Restrictions to this algebra can therefore lose relative-phase information retained by increasingly nonlocal finite-system observables.

A vector is cyclic for an operator algebra when its orbit under that algebra has dense linear span. This is distinct from requiring the powers of one chosen operator to span the space. If the algebra is linear, its orbit itself is already a vector subspace.

A vector is separating for an operator algebra when evaluation at that vector is injective. A cyclic vector for the commutant of an operator algebra is separating for the original algebra: if $a\Omega =0$, then $a$ vanishes on its dense commutant orbit.

For a Von Neumann algebra with a cyclic separating vector, this is a densely defined antilinear operator. It is closable: the commutant orbit lies in the domain of its antilinear adjoint and is dense. Write $S$ for its closure and $S=J{\Delta }^{1/2}$ for its polar decomposition. In finite dimension it is everywhere defined and invertible. For a tracial vector, $S_0$ is isometric and extends to an antiunitary involution.

The positive operator in the polar decomposition $S=J{\Delta }^{1/2}$ of the Tomita operator. In a matrix-algebra standard representation with cyclic vector $D>0$, it is $\Delta (X)=D^{2}X{D}^{-2}$. For a tracial vector it is the identity.

The antiunitary factor in the polar decomposition of the Tomita operator. In the finite-dimensional and tracial settings it satisfies $J^2=I$ and $JMJ=M^{\prime }$. In a matrix-algebra standard representation by left multiplication, with positive invertible cyclic vector $D$, it acts by $J(X)=X^{\ast }$.

A unital star-subalgebra of the bounded operators on a Hilbert space that is closed in the weak operator topology, equivalently in the strong operator topology. The Von Neumann double commutant theorem makes these conditions equivalent to equality with the double commutant of an operator algebra. It is norm closed and hence a C-star algebra.

Here a Hilbert space module means a Hilbert space with a unital star-representation of a Von Neumann algebra, rather than a Hilbert C-star module with an algebra-valued inner product. A closed invariant subspace is reducing because the algebra is closed under adjoints. Module equivalence means an intertwining unitary. The polar decomposition of a bounded operator converts an intertwiner into a unitary between its initial and final support subspaces.

Two Hilbert space modules are unitarily equivalent if each embeds isometrically as a closed submodule of the other. For isometric intertwiners $u:H_1\to H_2$ and $v:H_2\to H_1$, let $D=H_1\ominus v{H}_2$ and $K={⨁}_{n\ge 0}(vu{)}^{n}D$. These summands are orthogonal. The operator acting as $u$ on $K$ and as $v^{\ast }$ on $K^{\perp }$ is the required unitary onto $H_2$.

A Von Neumann algebra whose center consists exactly of scalar multiples of the identity. A group von Neumann algebra is a factor exactly when every nonidentity conjugacy class is infinite. A central operator has a square-summable coefficient vector constant on those classes; an infinite class must therefore have coefficient zero. Conversely, the sum of left translations over a finite nonidentity class is a nonscalar central operator.

For a discrete group, its group von Neumann algebra is generated on ${\ell }^2(\Gamma )$ by left translations $\lambda (g){\delta }_h={\delta }_{gh}$. The vector ${\delta }_e$ is cyclic and separating, and its vector functional is tracial. Its modular conjugation acts by $J{\delta }_g={\delta }_{g^{-1}}$ with conjugated scalar coefficients. The commutant is the algebra generated by right translations $\rho (g){\delta }_h={\delta }_{h{g}^{-1}}$.

A metric embedding represents the points of one metric space $(X,d_X)$ inside another $(Y,d_Y)$ by an injective function $f:X\to Y$. The geometric question is how faithfully the representation preserves pairwise distances. For example, binary strings can be treated as vectors so that tools from linear algebra become available, but the chosen norm determines what their separation means. A drawing of the points alone does not specify a metric embedding: both metrics matter.

An isometric embedding preserves every distance exactly. A metric embedding that is a bi-Lipschitz map allows multiplicative error while keeping its bi-Lipschitz distortion bounded over all pairs. A coarse embedding instead controls separation through possibly nonlinear functions of distance. These are different requirements: the Hamming cube as an L1 and L2 metric below preserves Hamming distance exactly in one representation and takes its square root in another.

The usefulness is that a complicated distance comparison becomes a calculation with familiar vectors and norms. This also helps assess a visualization: nearby points should not acquire arbitrarily large separations, and far-apart points should not collapse together. Matoušek's 2013 lecture notes describe how motivations from computer science, especially approximation algorithms, accelerated the study of metric embeddings from the 1990s onward. ^[ref]

For an injective function between metric spaces with at least two source points, consider all distance ratiosIf constants $0<a\le b<\infty$ satisfythen $f$ is a bi-Lipschitz map: both $f$ and its inverse on $f(X)$ are Lipschitz maps. The bound $b/a$ compares the most expanded pair with the most contracted pair. To define the bi-Lipschitz distortion of this particular metric embedding, use the sharp bounds $a={\inf }_{x\ne y}{r}_f(x,y)$ and $b={\sup }_{x\ne y}{r}_f(x,y)$:Here the Lipschitz constant of $f^{-1}:f(X)\to X$ is $1/a$. If no positive finite bounds exist, the bi-Lipschitz distortion is infinite. For a finite source, every injective function has finite bi-Lipschitz distortion, but its size can depend on the source. Matoušek gives the equivalent definition using one scale factor and a multiplicative error bound. ^[ref]

Changing units is harmless: replacing $d_Y$ by $\lambda d_Y$, with $\lambda >0$, multiplies both $a$ and $b$ by $\lambda$ and leaves $b/a$ unchanged. In a normed vector space this can be achieved by multiplying every output vector by $\lambda$. Thus bi-Lipschitz distortion one means that all distances change by the same factor; an isometric embedding additionally requires that factor to be one. A stretch factor with a specified normalization is a related quantity; when comparing sources, check which overall scale has been fixed.

Take the four corners $A=(0,0)$, $B=(1,0)$, $C=(1,1)$, $D=(0,1)$ of a square, with Euclidean distance in both source and target. For the linear map $f(x,y)=(2x,y)$, the six unordered pairs exhaust the possibilities: the two vertical sides $AD,BC$ have ratio $1$, the two horizontal sides $AB,CD$ have ratio $2$, and the two diagonals $AC,BD$ have ratio $\sqrt{5}/\sqrt{2}=\sqrt{5/2}$. Consequently $a=1$, $b=2$, and $\mathrm{dist}(f)=2$. In contrast, $g(x,y)=(3x,3y)$, three times the identity function, gives ratio $3$ for every pair and has bi-Lipschitz distortion $3/3=1$.

The ratio chart makes the reason visible: a common multiplier moves every ratio together, while unequal coordinate scaling spreads the ratios apart. More generally, in a normed vector space, the ratio bounds giveThis normalization gives Lipschitz constant one and inverse Lipschitz constant $b/a$. It is only a change of scale, so it cannot improve the bi-Lipschitz distortion.

The best possible bi-Lipschitz distortion of a source into a specified target is a separate quantity:The infimum runs over all injective functions, and need not be attained. The notation $c_p(X)$ means the analogous infimum over metric embeddings into an Lp space. A calculation for one chosen $f$ gives an upper bound for $c_Y(X)$; proving optimality also requires a lower bound for every possible $f$.

For an injective function that does not increase distances, one stretch-factor convention measures the largest compression that must be undone:If the sharp Lipschitz constant of $f$ is one, this equals bi-Lipschitz distortion. Fixing the scale matters: uniform compression $f(x)=x/2$ has stretch factor two in this convention, but bi-Lipschitz distortion one. In a geometric spanner, the corresponding stretch factor is the largest graph-route distance divided by direct Euclidean distance; the graph-to-Euclidean identification does not increase distances. ^[ref].

A map $f:X\to Y$ between metric spaces is a coarse embedding when nondecreasing control functions ${\rho }_{-},{\rho }_{+}:[0,\infty )\to [0,\infty )$ satisfyThe last condition means that distances tending to infinity in the source must also tend to infinity in the target. The upper control prevents bounded source distances from having unbounded image distances. Unlike a metric embedding as defined here, a coarse embedding need not be injective: its lower control may vanish at small distances. Finite bi-Lipschitz distortion implies a coarse embedding by taking ${\rho }_{-}(t)=at$ and ${\rho }_{+}(t)=bt$, but nonlinear controls such as $\sqrt{t}$ allow much more compression.

A family $(X_n)$ uniformly coarsely embeds into $Y$ when maps $f_n:X_n\to Y$ admit the same two control functions ${\rho }_{-}$ and ${\rho }_{+}$ from the definition of a coarse embedding, independent of $n$. For a single finite metric space, the lower control can vanish up to its diameter and then grow without bound; this says little about its representation. For a family with unbounded diameters, common controls have real content: they cannot be chosen afresh after seeing each member's diameter. The Hamming cube as an L1 and L2 metric supplies explicit common controls, in contrast with the expander graph obstruction to uniform coarse embedding.

Use the $\{0,1{\}}^n$ convention for the Hamming cube $H_n$. Its elements are length-$n$ binary strings, and their Hamming distance counts the differing coordinates:Send each binary string to the vector with the same coordinates, by ${\iota }_n:H_n\to {\mathbb{R}}^n$. Every differing coordinate contributes $1$ both to the sum of absolute differences and to the sum of squared differences. Therefore the L1 norm and L2 norm give, respectively,This short coordinate calculation proves that the L1 norm gives an isometric embedding, while Euclidean distance grows like the square root of the number of changed binary digits. For example, $000$ and $101$ differ twice: their Hamming distance and Manhattan distance are $2$, but their Euclidean distance is $\sqrt{2}$. Comparing binary strings in these two geometric representations answers different questions even though the points have the same coordinates.

For distinct pairs $k$ ranges over every integer from $1$ to $n$. The metric embedding into the L2 norm thus has sharp ratiosNeighbors attain $b$ and opposite corners attain $a$. This computes the bi-Lipschitz distortion of this coordinate map; it does not prove that every metric embedding into an L2 space has at least this bi-Lipschitz distortion. Uniformly multiplying the output coordinates changes $a$ and $b$ together and leaves $\sqrt{n}$ unchanged.

The important family distinction is that these coordinate maps have no dimension-independent bound on their bi-Lipschitz distortion into the L2 norm, yet they do give a uniform coarse embedding of a family of metric spaces. Pad each output vector with zero coordinates to view all maps in the single l2 sequence space, an L2 space for counting measure. Then the same functionswork for every $n$, and ${\rho }_{-}(t)\to \infty$. Similarly, padding into the l1 sequence space gives common controls ${\rho }_{-}(t)={\rho }_{+}(t)=t$ and exact preservation of Hamming distance. These claims use unnormalized Hamming distance; replacing it by normalized Hamming distance changes the family of source metrics.

The geometry has a practical origin: Hamming's 1950 paper uses the number of differing positions between binary strings to study error-correcting codes. Changing one binary digit moves to a neighboring corner, so a question about corrupted messages becomes a question about separation in the Hamming cube. ^[ref]

For a finite graph $G=(V,E)$, its edge-expansion constant isAn expander family has uniformly bounded degrees, orders tending to infinity, and expansion constants bounded below by a positive constant.

For a port-labeled $D$-regular graph $G$ and a $d$-regular graph $H$ on its $D$ port labels, replace every vertex by a copy of $H$. An edge makes a step in $H$, crosses the corresponding edge of $G$, then makes another step in $H$. The result has $|G|D$ vertices and degree $d^2$. Its normalized operator is $BRB$, where $B=I\otimes P_H$ and $R$ is the involutive edge rotation of $G$. Decomposing a mean-zero vector into cloud-constant and cloud-orthogonal parts proves the bound $\rho (G\mathrm{zigzag}H)\le \rho (G)+2\rho (H)+\rho (H{)}^2$.

Choose $D=d^2$ and a fixed $d$-regular graph $H$ on $D^2$ vertices with absolute nonconstant eigenvalues at most $1/10$. Start with the loop-inclusive complete graph $G_0$ on $D$ vertices and iterate $G_{t+1}=G_t^2\mathrm{zigzag}H$. The degree stays $D$, vertex counts are $D^{2t+1}$, and ${\rho }_{t+1}\le {\rho }_t^2+21/100$. Since ${\rho }_0=0$, all ${\rho }_t\le 1/2$. The spectral cut bound gives multiplicity-counted edge expansion at least $D/4$. Removing loops and merging parallel edges loses at most a factor $D$, producing simple expander graphs with maximum degree $D$ and edge expansion at least $1/4$.

If $G$ has adjacency matrix $A=(a_{xy})$ and expansion $h$, then every $L^1$-valued map on its $n$ vertices satisfiesFor scalar functions this follows from the layer-cake formula applied above and below a median; integration over the $L^1$ coordinate proves the vector-valued form.

For a nonnegative measurable function $g$,On a graph, applying this identity to $|g(x)-g(y)|$ expresses its total variation as the integral of the edge boundaries of the superlevel sets.

More generally, if $\phi :[0,\infty )\to [0,\infty )$ is differentiable, increasing, and satisfies $\phi (0)=0$, then Tonelli theorem and the fundamental theorem of calculus give

Let $F,G\ge 0$, $1<p<\infty$, and $G\in L^p$. Assume the displayed tail inequality and finite positive-threshold superlevel measures. First split $G$ at $a/2$ to obtain $a\mu \{F>2a\}\le {\int }_{\{G>a\}}G$. Layer cake representation and Tonelli theorem imply $F\in L^p$. Integrating the original inequality against $p{a}^{p-2}$ then gives $\Vert F{\Vert }_p^p\le q\int G{F}^{p-1}\le q\Vert G{\Vert }_p\Vert F{\Vert }_p^{p-1}$, with $q=p/(p-1)$. This is the analytic estimate behind the Doob Lp maximal inequality.

If a $d$-regular graph on $n$ vertices has expansion $h$, its $L^1$ distortion obeysThe Poincare inequality controls average image distance by edge lengths, while bounded-degree ball growth makes the average graph distance comparable to $\log n/\log d$.

An expander family does not uniformly coarsely embed into $L^1$ or $L^2$. Uniform upper control bounds every embedded edge, whereas the expander Poincare inequality bounds the average image distance. A fixed proportion of vertex pairs have graph distance tending to infinity, contradicting the lower control. The $L^2$ case also follows from the isometric Gaussian embedding of a Hilbert space into $L^1$.

A Banach space $X$ is finitely representable in $Y$ when, for every finite-dimensional subspace $E\subseteq X$ and every $\epsilon >0$, there are a subspace $F\subseteq Y$ and an isomorphism $T:E\to F$ with $\Vert T\Vert \Vert T^{-1}\Vert <1+\epsilon$.

A Banach space is superreflexive when every Banach space finitely representable in it is a reflexive Banach space. Equivalently, it admits an equivalent uniformly convex norm, or every one of its ultrapowers is reflexive.

A Banach space $X$ is reflexive exactly when, for every $\theta >0$ and every sequence $(x_i)$ in $B_X$, some convex combination of a finite initial segment lies within $\theta$ of a convex combination of the remaining tail. In a reflexive space both convex hulls approximate a common weak cluster point. The converse is the convex-block form of the James reflexivity criterion.

James's theorem says that a Banach space is reflexive exactly when every continuous linear functional attains its supremum on the closed unit ball. Its separation proof also yields the equivalent convex-block criterion: nonreflexivity produces a bounded sequence whose initial and tail convex hulls remain uniformly separated.

For finite-dimensional subspaces $E\subseteq X^{\ast \ast }$ and $F\subseteq X^{\ast }$, the principle of local reflexivity gives an almost-isometric map $T:E\to X$ that fixes $E\cap X$ and preserves the pairings with $F$. It lets finite-dimensional bidual separation data be realized inside $X$.

A Banach space $X$ is superreflexive exactly when, for every $\theta >0$, some $N$ forces every sequence $(x_i{)}_{i=1}^N\subseteq B_X$ to have two convex combinations, one before and one after a cut, at distance below $\theta$. Failure produces a nonreflexive ultrapower; finite representability transfers a violating finite sequence back from any nonreflexive space finitely representable in $X$.

A Banach space $X$ is superreflexive exactly when the distortions $c_X(D_n)$ of the finite diamond graphs tend to infinity. A uniformly separated convex-block sequence recursively realizes all branches of $D_n$ with bounded distortion, while uniform convexity forces quantitative collapse across repeated diamonds.

Every metric space with $n$ points admits an embedding into a Hilbert space with distortion $O(\log n)$. The usual random-subset construction gives an embedding into Euclidean dimension $O((\log n{)}^2)$.

Fix a point $x_0$ in a metric space $X$. The Fréchet embedding sends $x$ to the bounded function $a\mapsto d(x,a)-d(x_0,a)$ in ${\ell }^{\infty }(X)$. The triangle inequality bounds each coordinate by $d(x,x_0)$ and gives $\Vert f_x-f_y{\Vert }_{\infty }\le d(x,y)$. Taking $a=x$ gives equality, so the map is an isometric embedding. For a separable metric space a countable dense set of anchors suffices. Finite collections of distances to selected subsets instead give one-Lipschitz coordinates that need not be an exact Fréchet embedding.

For every integer $q\ge 2$, every $n$-point metric space embeds into ${\ell }_{\infty }^k$ with distortion at most $2q-1$ andThe coordinates are distance-to-subset functions. Randomly sampled subsets at $q$ density scales separate every pair at one scale; a union bound leaves the stated number of coordinates.

If a fixed-degree expander on $n$ vertices embeds into ${\ell }_{\infty }^k$ with distortion $\alpha$, thenIndeed, ${\ell }_{\infty }^k\hookrightarrow {\ell }_p^k$ has distortion $k^{1/p}$, while $c_p(G)\gtrsim (\log n)/p$. Taking $p\asymp \log k$ gives $\log k\gtrsim (\log n)/\alpha$.

For $0<\epsilon <1$ and any $n$ points in a Hilbert space, there is a linear map into Euclidean dimension $O({\epsilon }^{-2}\log n)$ that multiplies every pairwise distance by a factor between $1-\epsilon$ and $1+\epsilon$.

The striking feature is that the target dimension depends on the number of points and the allowed error, independently of the ambient dimension. Fix a finite set $S=\{x_1,\dots ,x_n\}\subset {\mathbb{R}}^D$, with $n\ge 2$, and $0<\epsilon <1$. An equivalent sufficient statement uses squared Euclidean distances: a linear map $T:{\mathbb{R}}^D\to {\mathbb{R}}^k$ exists, with $k=O({\epsilon }^{-2}\log n)$, such thatThe finite-set theorem cited here supplies an explicit sufficient target dimension for this squared-distance formulation. ^[ref]

Taking square roots gives distance factors $\sqrt{1-\epsilon }$ and $\sqrt{1+\epsilon }$, which lie inside $[1-\epsilon ,1+\epsilon ]$. Conversely, bounds $1\pm \epsilon$ on distances only give squared-distance bounds $(1\pm \epsilon {)}^2$; the same numerical tolerance should not be silently used for both. Under the squared-distance bounds, the bi-Lipschitz distortion is at most $\sqrt{(1+\epsilon )/(1-\epsilon )}$.

The Johnson–Lindenstrauss lemma preserves this fixed finite set, rather than every vector in the ambient Euclidean space. A linear map with $k<D$ has a nonzero kernel by the rank-nullity theorem, so some nonzero vectors collapse completely. For finitely many points in a real Hilbert space, apply the finite-dimensional argument on their linear span and extend by orthogonal projection onto that linear span. If the sufficient target dimension exceeds the ambient dimension, the identity map already preserves every Euclidean distance exactly, with zero padding if a larger target is requested.

Draw a $k\times D$ random matrix $G$ whose entries are independent random variables with the standard normal distribution, and setThe factor $1/\sqrt{k}$ makes the expected value of the squared L2 norm equal to the original squared L2 norm. This Gaussian Johnson–Lindenstrauss transform is a linear map, generally not an orthogonal projection: its rows are not required to be orthogonal vectors. ^[ref]

For the fixed finite set $S$, let $0<\delta <1$ be an allowed failure probability, and defineWith $\log$ denoting the natural logarithm, a sufficient integer target dimension isThen one draw of this specified random matrix satisfies all the squared Euclidean distance bounds simultaneously with probability at least $1-\delta$. Since $c(\epsilon )\ge {\epsilon }^2/12$, the simpler sufficient bound $k\ge \lceil 12{\epsilon }^{-2}\log (n(n-1)/\delta )\rceil$ also works. Both are sufficient bounds for this argument; they do not claim the smallest possible target dimension.

This is a probability statement about a map drawn independently of the fixed finite set. It implies existence because the success probability is positive, but permits failed draws. The set cannot be chosen after inspecting the map with this same guarantee. In particular, no single draw preserves every possible finite set in the ambient Euclidean space when $k<D$.

Here is an original reproducible finite set with 40 points and 512 coordinates. Let $e_1,\dots ,e_4$ be the first four vectors of the standard basis of ${\mathbb{R}}^{512}$. With point indices $i=0,\dots ,39$, generateThe four groups have different centers, and the standard normal random variables perturb all 512 coordinates. Generate the coordinates in row order using NumPy's PCG64 pseudorandom number generator with seed 20261013. Then keep this finite set fixed. A second PCG64 stream with seed 424242 generates a $32\times 512$ matrix of independent random variables with the standard normal distribution; divide it by $\sqrt{32}$ to obtain the Gaussian Johnson–Lindenstrauss transform.

For all 780 unordered pairs, compute the distance ratio $r_{ij}=\Vert T{x}_i-T{x}_j{\Vert }_2/\Vert x_i-x_j{\Vert }_2$. In this draw, its minimum is approximately $0.733010$ and its maximum $1.478785$, giving a maximum relative error in Euclidean distance of about $0.478785$. The squared-distance ratios $r_{ij}^2$ instead range from approximately $0.537304$ to $2.186806$: their maximum relative error is about $1.186806$. Thus this particular draw fails a 20% distance tolerance. The Johnson–Lindenstrauss lemma does not assert that every draw into 32 dimensions must succeed.

The two bands of original Euclidean distances distinguish pairs within a group from pairs between groups. Their spread after the linear map shows why checking an average distance is insufficient: the Johnson–Lindenstrauss lemma controls every pair. The dashed 20% distance band is an illustrative tolerance, not a confidence interval or a squared-distance band. The affine hull of 40 points has dimension at most 39; 512 is the ambient coordinate count, and no full-dimensionality assumption is required. For this draw the bi-Lipschitz distortion is approximately $1.478785/0.733010=2.017414$.

Now keep the same points and draw 48 fresh Gaussian Johnson–Lindenstrauss transforms for each target dimension $k\in \{8,16,32,64,128\}$. NumPy's SeedSequence(314159).spawn(240) supplies distinct PCG64 streams, ordered first by target dimension, then by draw. Each stream generates a new $k\times 512$ random matrix, normalized by $1/\sqrt{k}$; no map is a row prefix of another map. Each plotted value is

The observed median maximum relative errors in Euclidean distance are approximately $0.735$, $0.520$, $0.381$, $0.267$, and $0.184$, respectively. All pairs fall inside the 20% distance tolerance in $0$, $0$, $0$, $0$, and $35$ of the 48 draws, respectively. These are computations on one synthetic finite set, rather than optimal dimension bounds or measured physical data. The displayed quantiles describe the sampled maps; they do not certify a success probability for other sets. Even at 128 dimensions, 13 of the sampled maps fail this tolerance.

The practical benefit is that each point acquires fewer coordinates while its pairwise Euclidean distances can remain useful. The choice of target dimension balances compression, accuracy, and failure probability. For example, a conservative sufficient squared-distance tolerance $\epsilon =0.2$ with $n=40$ and $\delta =0.05$ gives $k\ge 1195$ by the explicit bound above. Here that exceeds the ambient dimension, so the identity map is better for a certified guarantee. The much smaller dimensions in the plots illustrate observed behavior without claiming that this sufficient bound is sharp.

A short concentration inequality argument explains the bound. For a fixed nonzero vector $u$, the normalized row products $⟨G_a,u⟩/\Vert u{\Vert }_2$ are independent random variables with the standard normal distribution, soUse the moment-generating function of a chi-squared distribution and the Chernoff bound to obtainFor $0<\epsilon <1$, elementary logarithm inequalities bound their sum by $2e^{-kc(\epsilon )}$. Apply the union bound to the $\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ nonzero pair differences to get failure probability at most $n(n-1)e^{-kc(\epsilon )}\le \delta$. Independence of different pairs is unnecessary; they use the same map. This combines fixed-vector concentration with a finite-set union bound. ^[ref]

The unit sphere of an $n$-dimensional normed space has a $\delta$-net of size at most $(3/\delta {)}^n$. If $1-\delta \le \Vert Tx\Vert \le 1+\delta$ on this net and $\delta <1/3$, then

If $A\in \{-1,1{\}}^{d\times p}$ has independent Rademacher entries, then for fixed $u\ne 0$ and $0<t<1$,Applying a union bound to all pairwise differences embeds $n$ fixed points into dimension $O(t^{-2}\log (n/\epsilon ))$ while preserving every squared distance within a factor $1\pm t$ with probability at least $1-\epsilon$.

For a standard normal variable $Y$ and $\beta =\mathbb{E}|Y|=\sqrt{2/\pi }$,The exponential Markov inequality consequently gives Gaussian concentration for averages of independent copies of $|Y|$.

The random matrixsatisfiesA net argument shows that $k\ge C_{\epsilon }n$ permits a linear embedding of distortion below $1+\epsilon$.

Every $n$-point metric space embeds into ${\ell }_1^{O(\log n)}$ with distortion $O(\log n)$. Apply the Bourgain embedding theorem, reduce its Euclidean dimension to $O(\log n)$ with the Johnson–Lindenstrauss lemma, and use an Almost-isometric Gaussian embedding from l2 into l1.

On continuous functions $u:[0,T]\to X$, the exponentially weighted supremum norm is $\Vert u{\Vert }_{\alpha }={\sup }_{0\le t\le T}{e}^{-\alpha t}\Vert u(t)\Vert$. It is equivalent to the ordinary supremum norm and often turns a Volterra integral map into a contraction mapping.

An operator topology specifies convergence of linear operators. Common choices include the norm, strong, and weak operator topologies.

Operators $T_n$ converge to $T$ in the strong operator topology when $T_{n}x\to Tx$ in norm for every vector $x$.

This topology on bounded operators is generated by the seminorms $(\Vert T\xi {\Vert }^2+\Vert T^{\ast }\xi {\Vert }^2{)}^{1/2}$. A net converges exactly when both it and its adjoint net converge in the strong operator topology. It is the topology used in the full-unit-ball version of the Kaplansky density theorem.

Operators $T_n$ converge to $T$ in the weak operator topology when $⟨T_{n}x,y⟩\to ⟨Tx,y⟩$ for every pair of vectors $x,y$.