= Bi-Lipschitz distortion
{title2=$\operatorname{dist}(f)=b/a$}
For an <injective function> between <metric spaces> with at least two source points, consider all distance ratios
$$
r_f(x,y)=\frac{d_Y(f(x),f(y))}{d_X(x,y)},\qquad x\ne y.
$$
If constants $0<a\leq b<\infty$ satisfy
$$
a\leq r_f(x,y)\leq b\qquad(x\ne y),
$$
then $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)$:
$$
\operatorname{dist}(f)=\frac ba
=\operatorname{Lip}(f)\operatorname{Lip}(f^{-1})\geq1.
$$
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. <Lecture notes on metric embeddings by Jiří Matoušek>[Matoušek, Section 1.1: distortion and Lipschitz maps]{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 $\sqrt5/\sqrt2=\sqrt{5/2}$. Consequently $a=1$, $b=2$, and $\operatorname{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$.
\Image[/metric-embedding-distance-ratios.png]
{title=Uniform scaling keeps distortion one; unequal coordinate scaling gives distortion two}
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 give
$$
\frac1{b/a}d_X(x,y)\leq\left\|\frac{f(x)}b-\frac{f(y)}b\right\|\leq d_X(x,y).
$$
This 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:
$$
c_Y(X)=\inf_{f:X\hookrightarrow Y}\operatorname{dist}(f).
$$
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$.
Back to article page
