Lipschitz距離

同義語：Lipschitz distance

概要

前提知識: 距離空間, Lipschitz連続, 同相写像, 等長写像, Gromov-Hausdorff距離

Lipschitz距離（Lipschitz distance）とは、二つの距離空間の「形の近さ」を、一方から他方への双 Lipschitz な同相写像が距離をどれだけ伸び縮みさせるかで測る量である。距離を最大で $\lambda$ 倍に伸ばし、逆向きにも最大で $\lambda$ 倍に伸ばす同相写像があれば、二つの空間の Lipschitz 距離は $\log\lambda$ 以下である。
Gromov-Hausdorff距離が「二つの空間を同じ空間に置いたときのずれ」という加法的な近さを測るのに対し、Lipschitz 距離は「距離の比」という乗法的な近さを測り、しかも同相写像を通してしか比べない。そのため、同相でない空間どうしの Lipschitz 距離は $\infty$ であり、有限集合でコンパクト距離空間を近似するような Gromov–Hausdorff 収束は Lipschitz 距離では起こらない。逆に、Lipschitz 距離での収束は Gromov–Hausdorff 収束を導く。
この記事では、Lipschitz 距離を定義し、三角不等式などの基本性質、コンパクトな空間どうしでは Lipschitz 距離が $0$ なら等長であること、Gromov–Hausdorff 距離との比較の不等式を証明する。あわせて、コンパクトでない空間では非退化性が破れる例と、Gromov–Hausdorff 収束するのに Lipschitz 距離が $\infty$ に発散する同相な空間の列を示す。

定義

以下、距離空間はすべて 2 点以上をもつとし、どの空間の距離も文脈から明らかなときは $d$ と書く。

拡大率

距離空間の間の写像 $f\colon X\to Y$ の拡大率（dilatation）を
$$ \operatorname{dil}f:=\sup_{x\neq x'}\frac{d(f(x),f(x'))}{d(x,x')}\in[0,\infty] $$
で定める。$\operatorname{dil}f<\infty$ であることは $f$ が Lipschitz連続であることにほかならず、$\operatorname{dil}f$ はその最小の Lipschitz 定数である。全単射 $f$ で $f$ と $f^{-1}$ がともに Lipschitz 連続であるものを双 Lipschitz 同相写像という。双 Lipschitz 同相写像は同相写像である。

Lipschitz 距離

距離空間 $X,Y$ の Lipschitz 距離を
$$ d_L(X,Y):=\inf\Bigl\{\log\max\{\operatorname{dil}f,\ \operatorname{dil}f^{-1}\}\Bigm|f\colon X\to Y\text{ は双 Lipschitz 同相写像}\Bigr\}\in[0,\infty] $$
で定める。双 Lipschitz 同相写像が一つもないときは $d_L(X,Y):=\infty$ とする。

$d_L$ が負にならないことは次のように分かる。$X$ の相異なる 2 点 $x,x'$ をとると
$$ d(x,x')=d\bigl(f^{-1}(f(x)),f^{-1}(f(x'))\bigr)\le\operatorname{dil}f^{-1}\cdot\operatorname{dil}f\cdot d(x,x') $$
なので $\operatorname{dil}f\cdot\operatorname{dil}f^{-1}\ge1$ であり、二つのうち大きいほうは $1$ 以上である。等号 $\operatorname{dil}f=\operatorname{dil}f^{-1}=1$ が成り立つのは、$f$ が距離を縮めず伸ばさないとき、すなわち $f$ が等長写像のときに限る。

和で定める流儀

$\log\max\{\operatorname{dil}f,\operatorname{dil}f^{-1}\}$ の代わりに $|\log\operatorname{dil}f|+|\log\operatorname{dil}f^{-1}|$ の下限で定める流儀もある。$a:=\log\operatorname{dil}f$、$b:=\log\operatorname{dil}f^{-1}$ とおくと、上で見たとおり $a+b\ge0$ なので、$m:=\max\{a,b\}\ge0$ と $\min\{a,b\}\ge-m$ から
$$ m\le|a|+|b|\le2m $$
が成り立つ。したがって二つの流儀の値は 2 倍以内の差しかなく、どちらで定めても「$0$ になること」「$0$ に収束すること」「有限であること」は同じである。

直感

$d_L(X,Y)<\log\lambda$ であるとは、$X$ と $Y$ の点を一対一に対応させて、どの 2 点の距離の比も $\lambda^{-1}$ 倍から $\lambda$ 倍の範囲に収められるということである。たとえば $\lambda=1.01$ なら、二つの空間は「1% の誤差で同じ形」である。
Gromov–Hausdorff 距離が小さいことは、対応する点どうしの距離の差が小さいことであった（Gromov-Hausdorff距離の命題「対応による特徴付け」）。差が小さくても、小さな距離の比は大きく狂いうる。また Gromov–Hausdorff 距離は点の対応が一対一でなくてもよく、空間の位相が変わる近似（有限集合による近似、次元が下がる潰れ）を許す。Lipschitz 距離はそのどちらも許さない、より強い近さである。

例

相似な空間

$X$ を有界な距離空間とし、$\lambda>0$ に対して距離を $\lambda$ 倍した空間を $\lambda X:=(X,\lambda d)$ と書く。恒等写像 $X\to\lambda X$ の拡大率は $\lambda$、逆写像の拡大率は $\lambda^{-1}$ なので $d_L(X,\lambda X)\le|\log\lambda|$ である。逆向きの不等式は prop-lipd-basic の 4 から従い（$\operatorname{diam}\lambda X=\lambda\operatorname{diam}X$）、
$$ d_L(X,\lambda X)=|\log\lambda| $$
となる。たとえば閉区間 $[0,a]$ と $[0,b]$（$a,b>0$）は $[0,b]=(b/a)[0,a]$ と等長なので $d_L([0,a],[0,b])=|\log(a/b)|$ であり、半径 $r$ の球面と単位球面の Lipschitz 距離は $|\log r|$ である。

Riemann 計量の比較

$M$ を連結な可微分多様体とし、$g,g'$ を $M$ 上の Riemann 計量（Riemann多様体）とする。$\lambda\ge1$ について、すべての接ベクトル $v$ で
$$ \lambda^{-2}g(v,v)\le g'(v,v)\le\lambda^2g(v,v) $$
が成り立つとする。区分的に $C^1$ な曲線の長さは速さの積分なので、$g'$ に関する長さは $g$ に関する長さの $\lambda^{-1}$ 倍以上 $\lambda$ 倍以下である。Riemann 距離は 2 点を結ぶ曲線の長さの下限なので、$\lambda^{-1}d_g\le d_{g'}\le\lambda d_g$ が成り立つ。よって恒等写像 $(M,d_g)\to(M,d_{g'})$ とその逆の拡大率は $\lambda$ 以下であり、$d_L\bigl((M,d_g),(M,d_{g'})\bigr)\le\log\lambda$ である。計量が一様に近ければ、距離空間として Lipschitz 距離で近い。

同相でない空間

双 Lipschitz 同相写像は同相写像なので、同相でない空間の Lipschitz 距離は $\infty$ である。たとえば閉区間 $[0,1]$ と単位円周 $S^1$（$S^1$ はどの 1 点を除いても連結だが、$[0,1]$ は内部の 1 点を除くと連結でなくなる）、点の個数が異なる有限距離空間どうし、コンパクト空間とコンパクトでない空間はどれも $d_L=\infty$ である。一方、これらの組の Gromov–Hausdorff 距離は、有界でありさえすれば有限である（Gromov-Hausdorff距離の命題「直径の評価」）。

性質

基本性質

距離空間 $X,Y,Z$ について次が成り立つ。

対称性：$d_L(X,Y)=d_L(Y,X)$。
三角不等式：$d_L(X,Z)\le d_L(X,Y)+d_L(Y,Z)$。
$X$ と $X'$、$Y$ と $Y'$ がそれぞれ等長なら $d_L(X,Y)=d_L(X',Y')$。特に等長な空間の Lipschitz 距離は $0$ である。
$X,Y$ が有界なら $d_L(X,Y)\ge\bigl|\log(\operatorname{diam}X/\operatorname{diam}Y)\bigr|$。
$d_L(X,Y)<\infty$ なら、$X$ と $Y$ は同相であり、一方が完備（完備距離空間）・有界・全有界・コンパクトなら他方もそうである。

1 は $f$ と $f^{-1}$ の役割を入れ替えればよい。
2：合成の拡大率は $\operatorname{dil}(g\circ f)\le\operatorname{dil}g\cdot\operatorname{dil}f$ を満たす（$d(g(f(x)),g(f(x')))\le\operatorname{dil}g\cdot d(f(x),f(x'))\le\operatorname{dil}g\cdot\operatorname{dil}f\cdot d(x,x')$）。双 Lipschitz 同相写像 $f\colon X\to Y$、$g\colon Y\to Z$ について、$g\circ f$ も双 Lipschitz 同相写像で、
$$ \max\{\operatorname{dil}(g\circ f),\operatorname{dil}(g\circ f)^{-1}\}\le\max\{\operatorname{dil}g,\operatorname{dil}g^{-1}\}\cdot\max\{\operatorname{dil}f,\operatorname{dil}f^{-1}\} $$
である（$(g\circ f)^{-1}=f^{-1}\circ g^{-1}$）。対数をとり $f,g$ について下限をとればよい。どちらかが $\infty$ のときは自明である。
3：等長写像の拡大率は $1$ なので、2 と同じ計算で等長写像を合成しても値は変わらない。恒等写像により $d_L(X,X)=0$ である。
4：$f\colon X\to Y$ を双 Lipschitz 同相写像とすると、$d(f(x),f(x'))\le\operatorname{dil}f\cdot d(x,x')$ と $f$ の全射性から $\operatorname{diam}Y\le\operatorname{dil}f\cdot\operatorname{diam}X$、同様に $\operatorname{diam}X\le\operatorname{dil}f^{-1}\cdot\operatorname{diam}Y$ である（2 点以上もつので直径は正）。よって $\max\{\operatorname{dil}f,\operatorname{dil}f^{-1}\}\ge\max\{\operatorname{diam}Y/\operatorname{diam}X,\ \operatorname{diam}X/\operatorname{diam}Y\}$ であり、対数をとって下限をとればよい。
5：双 Lipschitz 同相写像 $f$ が存在する。$f$ と $f^{-1}$ は Lipschitz 連続なので、Cauchy列・有界集合・有限な $\varepsilon$-ネット（半径を $\operatorname{dil}f$ 倍する）を互いに写し合う。コンパクト性は位相的な性質なので同相写像で保たれる。$\square$

$d_L$ は $\infty$ の値をとり、また次の thm-lipd-nondegenerate と ex-lipd-noncompact が示すように、等長でない空間の間でも $0$ になりうる。したがって $d_L$ は一般の距離空間の等長類の上では拡張された擬距離であり、コンパクト距離空間の等長類の上では（$\infty$ を許す）距離である。

コンパクトな空間での非退化性

$X,Y$ をコンパクト距離空間とする。$d_L(X,Y)=0$ ならば、$X$ と $Y$ は等長である。

仮定から、双 Lipschitz 同相写像の列 $f_k\colon X\to Y$ で $\lambda_k:=\max\{\operatorname{dil}f_k,\operatorname{dil}f_k^{-1}\}\to1$ となるものがある。$g_k:=f_k^{-1}$ とおく。$\lambda_k\le\Lambda$ となる定数 $\Lambda$ をとると、$\{f_k\}$ と $\{g_k\}$ はどちらも $\Lambda$-Lipschitz な写像の族なので同程度連続である。$X,Y$ はコンパクトなので、Arzelà–Ascoliの定理（その記事では値域を $\mathbb{R}^m$ として述べているが、証明は、$X$ の稠密な可算部分集合の上で対角線論法により各点収束する部分列をとり、同程度連続性で一様収束に広げるもので、値域をコンパクト距離空間に替えても、その点列コンパクト性と完備性によりそのまま通る）により、部分列をとって $f_k$ が連続写像 $f\colon X\to Y$ に、$g_k$ が連続写像 $g\colon Y\to X$ に一様収束するとしてよい（はじめに $f_k$ について、その部分列の中で $g_k$ について部分列をとる）。
$f$ は等長埋め込みである。実際、$x,x'\in X$ について
$$ \lambda_k^{-1}d(x,x')\le d(f_k(x),f_k(x'))\le\lambda_kd(x,x') $$
であり（左の不等式は $d(x,x')=d(g_k(f_k(x)),g_k(f_k(x')))\le\lambda_kd(f_k(x),f_k(x'))$ による）、$k\to\infty$ とすると距離の連続性から $d(f(x),f(x'))=d(x,x')$ となる。同様に $g$ も等長埋め込みである。
次に $g\circ f=\mathrm{id}_X$ を示す。$x\in X$ について、$g_k(f_k(x))=x$ なので
$$ d(g(f(x)),x)\le d\bigl(g(f(x)),g_k(f(x))\bigr)+d\bigl(g_k(f(x)),g_k(f_k(x))\bigr)\le\sup_Y d(g,g_k)+\Lambda\,d(f(x),f_k(x)) $$
であり、右辺は一様収束により $0$ に収束する。同様に $f\circ g=\mathrm{id}_Y$ である。よって $f$ は全単射な等長埋め込み、すなわち等長写像である。$\square$

反例：コンパクトでない空間では非退化性が破れる

$a_n:=1+1/n$（$n\ge1$）とおく。可算集合 $X=\{x_1,x_2,\dots\}$ に距離 $d(x_i,x_j):=a_i+a_j$（$i\neq j$）を、$Y=\{y_0,y_1,y_2,\dots\}$ に距離 $d(y_i,y_j):=b_i+b_j$（$i\neq j$）を入れる。ただし $b_0:=1$、$b_n:=a_n$（$n\ge1$）とする。このとき $X,Y$ は有界で完備な距離空間であり、$d_L(X,Y)=0$ であるが、$X$ と $Y$ は等長でない。

確かめを開く

重み $w_i>0$ から $d(i,j):=w_i+w_j$（$i\neq j$）で定めた関数は距離である：三角不等式は $w_i+w_k\le(w_i+w_j)+(w_j+w_k)$ による。相異なる 2 点の距離は $2$ 以上なので、$X,Y$ の Cauchy 列は最終的に一定であり、どちらも完備である。また無限集合なので、どちらもコンパクトでない。相異なる 3 点 $i,j,k$ について $w_i=\frac12\bigl(d(i,j)+d(i,k)-d(j,k)\bigr)$ なので、各点の重みは距離から決まり、等長写像は重みを保つ。$Y$ には重み $1$ の点 $y_0$ があり、$X$ には重み $1$ の点がない（$a_n>1$）ので、$X$ から $Y$ への等長写像は $y_0$ を像に含まず、全射でない。よって $X$ と $Y$ は等長でない。

$k\ge2$ について全単射 $f_k\colon X\to Y$ を、$n< k$ では $f_k(x_n)=y_n$、$f_k(x_k)=y_0$、$n> k$ では $f_k(x_n)=y_{n-1}$ で定める。各点で重みの比 $r_n:=w(f_k(x_n))/a_n$ は、$n< k$ で $1$、$n=k$ で $1/(1+1/k)$、$n> k$ で $a_{n-1}/a_n=n^2/(n^2-1)\in(1,1+1/k]$ である。距離は重みの和なので、比 $d(f_k(x_i),f_k(x_j))/d(x_i,x_j)=(r_ia_i+r_ja_j)/(a_i+a_j)$ は $r_i$ と $r_j$ の間にある。したがって $\operatorname{dil}f_k\le1+1/k$、$\operatorname{dil}f_k^{-1}\le1+1/k$ であり、$d_L(X,Y)\le\log(1+1/k)\to0$ となる。$\square$

この例は thm-lipd-nondegenerate の仮定から「コンパクト」だけを外したものであり、有界性と完備性を保ったままでも結論が成り立たないことを示す。

Gromov–Hausdorff 距離との比較

Lipschitz 距離による Gromov–Hausdorff 距離の評価

$X,Y$ を有界な距離空間とすると
$$ d_{GH}(X,Y)\le\frac12\bigl(e^{d_L(X,Y)}-1\bigr)\max\{\operatorname{diam}X,\operatorname{diam}Y\} $$
が成り立つ（右辺が $\infty$ のときは自明）。

双 Lipschitz 同相写像 $f\colon X\to Y$ をとり、$\lambda:=\max\{\operatorname{dil}f,\operatorname{dil}f^{-1}\}$、$D:=\max\{\operatorname{diam}X,\operatorname{diam}Y\}$ とおく。$f$ のグラフ $R:=\{(x,f(x))\mid x\in X\}$ は $f$ が全単射なので $X$ と $Y$ の間の対応である（Gromov-Hausdorff距離の定義「対応と歪み」）。$x,x'\in X$ について、$d(f(x),f(x'))\ge d(x,x')$ なら
$$ d(f(x),f(x'))-d(x,x')\le(\lambda-1)d(x,x')\le(\lambda-1)D, $$
$d(f(x),f(x'))< d(x,x')$ なら、$f^{-1}$ の拡大率を使って
$$ d(x,x')-d(f(x),f(x'))\le(\lambda-1)d(f(x),f(x'))\le(\lambda-1)D $$
である。よって $R$ の歪みは $(\lambda-1)D$ 以下であり、Gromov-Hausdorff距離の命題「対応による特徴付け」により $d_{GH}(X,Y)\le\frac12(\lambda-1)D$ となる。$f$ について下限をとると、$\lambda$ の下限は $e^{d_L(X,Y)}$ なので主張を得る。$\square$

Lipschitz 収束は Gromov–Hausdorff 収束を導く

コンパクト距離空間の列 $X_k$ とコンパクト距離空間 $X$ について $d_L(X_k,X)\to0$ ならば、$X_k$ は $X$ に Gromov–Hausdorff 収束する。

prop-lipd-basic の 4 により $\operatorname{diam}X_k\le e^{d_L(X_k,X)}\operatorname{diam}X$ なので、$k$ が大きければ $\operatorname{diam}X_k\le2\operatorname{diam}X$ である。thm-lipd-gh から $d_{GH}(X_k,X)\le(e^{d_L(X_k,X)}-1)\operatorname{diam}X\to0$ となる。$\square$

逆は成り立たない。空間の位相が変わる近似は Lipschitz 距離では $\infty$ になる（ex-lipd-infinite）。次の例は、すべて同じ位相をもつ空間の列でも、Gromov–Hausdorff 距離が $0$ に近づきながら Lipschitz 距離は $\infty$ に発散しうることを示す。

反例：同相な空間の列で逆が成り立たない

$k\ge1$ について、$[0,1]$ 上の距離
$$ d_k(s,t):=|s-t|+\frac1k\min\{1,\ k^2|s-t|\} $$
を考え、$X_k:=([0,1],d_k)$ とおく。$X_k$ はすべて $[0,1]$ と同相で、$d_{GH}(X_k,[0,1])\le\frac1{2k}\to0$ であるが、$d_L(X_k,[0,1])\ge\log(1+k)\to\infty$ である。

確かめを開く

$\varphi(u):=\min\{1,k^2u\}$ は $[0,\infty)$ で単調非減少・凹で $\varphi(0)=0$ なので劣加法的であり、$\varphi(|s-t|)$ は三角不等式を満たす。よって $d_k$ は距離で、$|s-t|\le d_k(s,t)\le(1+k)|s-t|$ から $X_k$ は $[0,1]$ と同相である。$0\le d_k(s,t)-|s-t|\le1/k$ なので、恒等写像のグラフは歪み $1/k$ 以下の対応であり、$d_{GH}(X_k,[0,1])\le\frac1{2k}$ である。

距離空間 $Z$ の中の曲線 $c\colon[0,1]\to Z$ の長さを、分割 $0=u_0< u_1<\dots< u_m=1$ にわたる $\sum_jd(c(u_{j-1}),c(u_j))$ の上限とする（長さ空間）。$X_k$ の恒等写像 $\mathrm{id}\colon[0,1]\to X_k$ の長さは $1+k$ である。実際、幅がすべて $1/k^2$ 以下の分割では和はちょうど $\sum_j(1+k)(u_j-u_{j-1})=1+k$ であり、分割を細かくしても三角不等式により和は減らないので、どの分割の和も $1+k$ 以下である。

$f\colon[0,1]\to X_k$ を双 Lipschitz 同相写像とする。$f$ は区間の間の連続な全単射なので狭義単調である。$X_k$ の分割 $0=u_0<\dots< u_m=1$ に対し $s_j:=f^{-1}(u_j)$ は単調に並び、$\sum_j|s_j-s_{j-1}|=1$ である。よって $\sum_jd_k(u_{j-1},u_j)\le\operatorname{dil}f\sum_j|s_j-s_{j-1}|=\operatorname{dil}f$ であり、分割について上限をとると $1+k\le\operatorname{dil}f$ を得る。したがって $d_L(X_k,[0,1])\ge\log(1+k)$ である。$\square$

$X_k$ では、$1/k^2$ より短い距離が $1+k$ 倍に引き伸ばされている。この引き伸ばしは距離の差としては $1/k$ 以下で Gromov–Hausdorff 距離には見えないが、距離の比としては大きく、曲線の長さを $1+k$ 倍にする。

条件を外した反例

外す条件	反例	成り立たなくなること
thm-lipd-nondegenerate の $X,Y$ のコンパクト性	重みの和で距離を入れた可算集合 $X,Y$（ex-lipd-noncompact）	$d_L(X,Y)=0$ だが $X$ と $Y$ は等長でない
cor-lipd-gh の逆向きで、空間が互いに同相であること	有限な $1/k$-ネット $S_k\subset[0,1]$（Gromov-Hausdorff距離の例「有限集合による近似と潰れる方向」）	$d_{GH}(S_k,[0,1])\to0$ だが $d_L(S_k,[0,1])=\infty$
cor-lipd-gh の逆向きで、距離の比が一様に $1$ に近いこと	$X_k=([0,1],d_k)$（ex-lipd-converse）	同相で $d_{GH}(X_k,[0,1])\to0$ だが $d_L(X_k,[0,1])\to\infty$

表の 2 行目と 3 行目は、どちらも「Gromov–Hausdorff 収束すれば Lipschitz 収束する」という逆の主張の反例である。2 行目は同相でないことで、3 行目は同相でも距離の比が一様に $1$ に近くないことで破れる。

補足

Lipschitz 距離が小さい空間は、双 Lipschitz 同相写像で写り合うので、位相だけでなく、曲線の長さ、Hausdorff次元、倍加測度をもつことなど、双 Lipschitz 同相写像で保たれる量や性質を共有する。ex-lipd-riemann のように Riemann 計量が一様に近いことから Lipschitz 距離の評価が出る一方、ex-lipd-converse のように Gromov–Hausdorff 距離が小さくても長さは大きく変わりうる。距離の差を測る Gromov–Hausdorff 距離と、距離の比を測る Lipschitz 距離は、この意味で役割が違う。

Lipschitz距離

概要

定義

直感

例

性質

Gromov–Hausdorff 距離との比較

条件を外した反例

補足

関連項目