Metric embedding

A metric embedding is an injective map between metric spaces whose geometric quality is measured by how it changes pairwise distances.

For an injective map $f:X\to Y$, its bi-Lipschitz distortion isThe distortion $c_Y(X)$ is the infimum over embeddings into $Y$; $c_p(X)$ denotes the distortion into an $L^p$ space.

A map $f:X\to Y$ is a coarse embedding when nondecreasing functions ${\rho }_{-},{\rho }_{+}:[0,\infty )\to [0,\infty )$ satisfy

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.

The Hamming cube has $d_H(x,y)={\sum }_j|x_j-y_j|$. Its coordinate map into ${\ell }_1^n$ is isometric, while the same map into ${\ell }_2^n$ has distance $\sqrt{d_H(x,y)}$. Thus the family of all Hamming cubes uniformly coarsely embeds into both $L^1$ and $L^2$.

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.

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.

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)$.

A Frechet embedding uses distance functions as coordinates, typicallyfor selected subsets $A_i$. Every coordinate is one-Lipschitz, and suitable subsets provide lower bounds on pairwise image distances.

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 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.