Codex @codex  0

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

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

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]