度量嵌入

度量嵌入（metric embedding）把一个度量空间的点映到另一个度量空间中，并考察原距离与像点距离之间的关系。完全保持每一对距离的是等距嵌入；允许距离按统一上下界改变时，则研究双 Lipschitz 嵌入及其畸变。目标空间的距离规则是问题的一部分：同一组坐标在欧氏范数和最大范数下，可以给出不同的结论。

一个可复算的例子是四环：四个点沿环相邻距离为一，相对点沿最短路径的距离为二。把它们画成边长一的欧氏正方形，邻边仍是一，但对角线变为根号二。这幅图保存了邻接关系，却没有保存全部距离。

从距离比看畸变

令 $X = {p_{0}, p_{1}, p_{2}, p_{3}}$ ，距离 $d$ 为每条边长一的四环最短路距离。按环顺序定义坐标映射 $f (p_{0}) = (0, 0), f (p_{1}) = (1, 0), f (p_{2}) = (1, 1), f (p_{3}) = (0, 1) .$ 先在目标平面使用欧氏距离 $ρ (u, v) = ‖ u - v ‖_{2}$ 。六对不同点可分成两组：

点对	原距离 $d$	像距离 $ρ$	比值 $ρ / d$
$01, 12, 23, 30$	1	1	1
$02, 13$	2	$\sqrt{2}$	$1 / \sqrt{2}$

最小距离比为 $1 / \sqrt{2}$ ，最大距离比为一，所以不同点对的相对缩放程度相差 $\sqrt{2}$ 倍。这就是本映射的畸变。把所有像坐标再乘二，两个比值都乘二，但其最大值与最小值之比仍是 $\sqrt{2}$ ；整体放大不消除相对变形。

四环图上相邻点距离一、相对点图距离二，映到欧氏正方形后相邻距离一而对角距离根号二 — 上图使用沿边最短路距离，下图使用平面欧氏距离。看起来相同的方形布局，使用的距离规则不同。

等距与双 Lipschitz 的严格定义

设 $(X, d)$ 、 $(Y, ρ)$ 为度量空间。映射 $f : X \to Y$ 若满足 $ρ (f (x), f (y)) = d (x, y)$ 对所有 $x, y \in X$ 成立，就称为等距嵌入；正距离被保留，因此它自动单射。

若存在常数 $0 < c \leq C < \infty$ ，使所有点对都满足 $c d (x, y) \leq ρ (f (x), f (y)) \leq C d (x, y),$ 则称 $f$ 为双 Lipschitz 嵌入。右边控制放大，左边控制塌缩，并使逆映射 $f^{- 1} : f (X) \to X$ 具有有限 Lipschitz 常数。有限点集的任何单射都可以找到某组正的上下界，但它们的比值可能很大；研究低畸变就是研究这组界能否彼此接近。

当 $X$ 有限且至少含两个点，定义精确的最小、最大距离比 $a_{f} = min_{x \neq y} \frac{ρ (f (x), f (y))}{d (x, y)}, b_{f} = max_{x \neq y} \frac{ρ (f (x), f (y))}{d (x, y)} .$ 对单射 $f$ ， $0 < a_{f} \leq b_{f} < \infty$ ，其畸变定义为 $dist (f) = \frac{b_{f}}{a_{f}} \geq 1.$ 这也是使某个尺度 $s > 0$ 下的不等式 $s d \leq ρ \leq D s d$ 成立的最小 $D$ ：任意此类界都有 $s \leq a_{f}$ 、 $D s \geq b_{f}$ ，所以 $D \geq b_{f} / a_{f}$ ；取 $s = a_{f}$ 就能达到。

畸变为一表示所有距离被同一个正数倍缩放，即相似嵌入；把目标距离相应归一化后才是等距嵌入。MIT 讲义对不放大的映射用最大的收缩倒数量化误差。将本篇映射的目标距离除以 $b_{f}$ ，最大距离比恰为一，最小距离比为 $a_{f} / b_{f}$ ，该收缩倒数就等于 $b_{f} / a_{f}$ 。^[1]

单点空间没有不同点对，上述最小、最大比值不适用。无限空间还要把最值改成上、下确界，并另查下界严格为正、上界有限；这两个条件不会仅由单射或连续性得到。

有限空间的距离坐标等距嵌入

令 $X = {p_{1}, \dots, p_{n}}$ 是有限度量空间， $n \geq 1$ 。给每个点分配它到全部锚点的距离： $Φ (x) = (d (x, p_{1}), \dots, d (x, p_{n})) \in ℝ^{n} .$ 目标采用最大范数 $‖ z ‖_{\infty} = max_{i} | z_{i} |$ ，相应空间记为 $ℓ_{\infty}^{n}$ 。这个有限空间的 Fréchet 距离坐标构造满足 $‖ Φ (x) - Φ (y) ‖_{\infty} = d (x, y) .$

证明。 三角不等式分别给出 $d (x, p_{i}) \leq d (x, y) + d (y, p_{i})$ 和交换 $x, y$ 后的关系，所以每个坐标都有 $| d (x, p_{i}) - d (y, p_{i}) | \leq d (x, y) .$ 取最大值便得到不放大的上界。另一方面，锚点列表中含有 $x$ 本身；在该坐标上，差的绝对值就是 $| d (x, x) - d (y, x) | = d (x, y)$ ，所以上界实际达到。两边相等，也证明不同点的像不同。^[1]

四环的距离坐标具体为 $\begin{matrix} Φ (p_{0}) & = (0, 1, 2, 1), & Φ (p_{1}) & = (1, 0, 1, 2), \\ Φ (p_{2}) & = (2, 1, 0, 1), & Φ (p_{3}) & = (1, 2, 1, 0) . \end{matrix}$ 例如 $p_{0}, p_{2}$ 的坐标差为 $(- 2, 0, 2, 0)$ ，最大绝对值二，正好等于相对点图距离； $p_{0}, p_{1}$ 的最大坐标差为一。

四环距离矩阵的第零与第二行被标出，逐坐标绝对差为二零二零，最大值二保持原图距离 — 一行就是一个点的嵌入坐标。每个坐标都不超出原距离，其中包含端点自身的锚坐标保证达到原距离。

若只保留少数锚点，证明的最后一步可能失效。比如四环只保留 $p_{0}$ 这一坐标， $p_{1}, p_{3}$ 都映为一，不同点发生合并。低维坐标是否保留距离，需要新的条件和估计；不能把完整距离坐标的结论直接移过去。

四环的欧氏障碍与最佳畸变

最大范数的结论不等于任意有限度量都能等距放进欧氏空间。对欧氏空间任意四个向量 $u_{0}, u_{1}, u_{2}, u_{3}$ ，展开平方内积可得 $\sum_{i = 0}^{3} ‖ u_{i} - u_{i + 1} ‖_{2}^{2} - ‖ u_{0} - u_{2} ‖_{2}^{2} - ‖ u_{1} - u_{3} ‖_{2}^{2} = ‖ u_{0} + u_{2} - u_{1} - u_{3} ‖_{2}^{2} \geq 0,$ 其中下标 $u_{4} = u_{0}$ 。也就是说，两条对角线长度的平方和不超过四条边长度的平方和。

若四环能等距嵌入某个欧氏空间，两条对角线都应长二，平方和为八；四条边都应长一，平方和为四。这会要求 $8 \leq 4$ ，矛盾。这个恒等式在任意欧氏维数都成立，增加坐标数不能消除矛盾。

它还给出任意欧氏嵌入的畸变下界。若距离满足 $s d \leq ρ \leq D s d$ ，两条对角线平方和至少为 $8 s^{2}$ ，四边平方和至多为 $4 D^{2} s^{2}$ 。因此 $D \geq \sqrt{2}$ 。开篇的边长一欧氏正方形恰好达到 $D = \sqrt{2}$ ，所以对这个四环度量，它已经实现最佳欧氏畸变。

有解变式。 改用最大范数平面，令 $g (p_{0}) = (1, 0), g (p_{1}) = (0, 1), g (p_{2}) = (- 1, 0), g (p_{3}) = (0, - 1) .$ 相邻点坐标差的绝对值为 $(1, 1)$ ，最大值一；相对点差为 $(2, 0)$ 或 $(0, 2)$ ，最大值二。这在二维 $ℓ_{\infty}$ 中等距实现了四环，不需要用满前面构造的四个坐标。

四环顶点位于正负横轴和纵轴单位点，使用最大范数时邻点距离一、对点距离二；以右侧点为中心的最大范数单位球是一个正方形 — 改变的是目标距离规则。阴影正方形是最大范数单位球，并非欧氏单位圆。

若希望一个能等距放在欧氏直线上的变式，可取三点路径，距离为 $d (a, b) = 1, d (b, c) = 2, d (a, c) = 3$ 。映射到 $0, 1, 3 \in ℝ$ 就同时实现三对距离。能否等距实现由整张距离表与目标范数共同决定。

有理距离表的精确实现与验收

下列代码验证有限有理距离表，并直接构造 Fréchet 坐标；另一个函数计算给定有理坐标在最大范数下的距离比和畸变。它不计算欧氏范数下的畸变，因而不会把表中的 $\sqrt{2}$ 用错误范数替代。整数、有理数字符串和 Fraction 保持精确，普通浮点数与布尔值被拒绝。

Python 3

from fractions import Fraction

def rational(value):
    if isinstance(value, bool) or not isinstance(value, (int, str, Fraction)):
        raise TypeError("use integer, rational string or Fraction data")
    try:
        return Fraction(value)
    except (ValueError, ZeroDivisionError) as error:
        raise ValueError("finite rational value required") from error

def checked_metric(distances):
    D = tuple(tuple(rational(v) for v in row) for row in distances)
    n = len(D)
    if n == 0 or any(len(row) != n for row in D):
        raise ValueError("nonempty square distance table required")
    for i in range(n):
        if D[i][i] != 0:
            raise ValueError("diagonal distances must be zero")
        for j in range(n):
            if D[i][j] != D[j][i] or (i != j and D[i][j] <= 0):
                raise ValueError("symmetric, strictly positive off-diagonal data required")
            for k in range(n):
                if D[i][j] > D[i][k]+D[k][j]:
                    raise ValueError("triangle inequality violated")
    return D

def frechet_embedding(distances):
    # Row i gives distances from point i to all anchors.
    return checked_metric(distances)

def linf_distortion(distances, coordinates):
    D = checked_metric(distances)
    P = tuple(tuple(rational(v) for v in row) for row in coordinates)
    n = len(D)
    if n < 2:
        raise ValueError("at least two points required for distance ratios")
    if len(P) != n or not P[0] or any(len(p) != len(P[0]) for p in P):
        raise ValueError("one common positive-dimensional coordinate vector per point required")
    lower, upper = None, None
    for i in range(n):
        for j in range(i):
            image_distance = max(abs(u-v) for u, v in zip(P[i], P[j]))
            if image_distance == 0:
                raise ValueError("coordinates are not injective")
            ratio = image_distance/D[i][j]
            lower = ratio if lower is None else min(lower, ratio)
            upper = ratio if upper is None else max(upper, ratio)
    return {"lower_ratio": lower, "upper_ratio": upper,
            "distortion": upper/lower}

D = [[0,1,2,1], [1,0,1,2], [2,1,0,1], [1,2,1,0]]
encoded = frechet_embedding(D)
assert linf_distortion(D, encoded)["distortion"] == 1
diamond = [(1,0), (0,1), (-1,0), (0,-1)]
assert linf_distortion(D, diamond)["distortion"] == 1
square = [(0,0), (1,0), (1,1), (0,1)]
assert linf_distortion(D, square)["distortion"] == 2
scaled = [(2*x, 2*y) for x, y in diamond]
assert linf_distortion(D, scaled) == {
    "lower_ratio": Fraction(2), "upper_ratio": Fraction(2),
    "distortion": Fraction(1)}
assert frechet_embedding([[0]]) == ((Fraction(0),),)
print(encoded)
print(linf_distortion(D, diamond))

验证函数逐项检查零对角、对称性、不同点严格正距离及所有三角不等式。通过后，距离表的每一行就是定理中已证明正确的坐标。验收函数检查全部不同点对，分别取最小与最大距离比，因此返回的是该有限坐标映射在最大范数下的准确畸变，不是随机抽样估计；坐标合并会明确报错。

设输入有 $n$ 点、所验坐标有 $k$ 维。验证三角不等式需要 $O (n^{3})$ 次有理数比较和加法，保存表需 $O (n^{2})$ 个数。Fréchet 坐标本身含 $n^{2}$ 个数；其全部最大范数距离可用 $O (n^{3})$ 次坐标比较核对。一般坐标验收在验证表之外需 $O (n^{2} k)$ 次运算，总存储 $O (n^{2} + n k)$ 。代码复制输入，有理数位长另影响实际成本。

度量条件与拓扑条件的区别

在 $[0, 1]$ 上，映射 $x \mapsto x^{2}$ 连续、单射，且逆函数平方根连续，因而是拓扑同胚。但不同点的距离比是 $| x^{2} - y^{2} | / | x - y | = x + y$ ，在零附近没有正的统一下界，所以不是双 Lipschitz 映射。保持点的邻近关系与用统一常数控制距离，是不同强度的要求。

有限空间的上述等距定理指定了最大范数和允许的坐标数。对已经位于欧氏空间的有限点集作低维近似，需要另设近似误差与维数条件；它既不消除四环的欧氏障碍，也不能替代这里对全部点对的距离验证。

参考文献

↑ ^1.0 ^1.1 MIT，6.854 Lecture Notes：Embeddings，“Min Ratio Cut”下的“Embeddings”小节，距离畸变、各类范数及距离坐标嵌入。访问日期：2026-10-24。

[mit-1] 1.0 ^1.1 MIT，6.854 Lecture Notes：Embeddings，“Min Ratio Cut”下的“Embeddings”小节，距离畸变、各类范数及距离坐标嵌入。访问日期：2026-10-24。

[1]