Hyperbolic metric spaces and stochastic embeddings
1. Reference
Details
Elements of asymptotic geometry
Probabilistic approximation of metric spaces and its algorithmic applications
Embeddings of gromov hyperbolic spaces
Markov type and threshold embeddings
A tight bound on approximating arbitrary metrics by tree metrics
A hyperbolic filling for ultrametric spaces
Algorithms on negatively curved spaces
Nagata dimension, quasisymmetric embeddings, and lipschitz extensions
Details
该分析框架的一个参考应用：Improving robustness of hyperbolic neural networks by lipschitz analysis
2. Preliminaries
大目标
【Q】决定when LF(X) isomorphically 嵌入到 \(L^1\) -space
【A】for any infinite, compact, doubling space \((X,d)\) and exponent \(\alpha\in(0,1)\), the snowflake space \((X, d^{\alpha})\) has free space isomorphic to \(l^1\)
【Q】或者more strongly，when LF(X) is isomorphic to an \(L^1\) -space
【A】iff. X isometrically embeds into an \(\mathcal{R}\) -tree
2.1. Metric Spaces and Maps between them.
2.2. Banach and Bochner-Lebesgue Spaces
definition
- C-bounded
- C-isomorphic embedding
- C-isomorphism
- \[V\approx W\] : there exists an isomorphism between \(V\) and \(W\)
- C-complemented :
- Pelczynski decomposition method
- \(L^1\) -space : if a Banach space equals the Lebesgue space \(L^1 (\Omega,\mathcal{F}, \mu)\) for some measure space \((\Omega,\mathcal{F}, \mu)\)
- function \(g\) is Bochner measurable: if \(g\) is \(\mu\) -almost everywhere pointwise limit of a sequence of simple functions.
- a function is simple : if it belongs to the linear span of the indicator functions.
- function \(g\) is essentially-separably-valued :
2.2.1. Theorem 2.2 Theorem
Details
Let \(X\) be an infinite separable metric space. If \(LF(X)\) is isomorphic to a complemented subspace of \(L^1\) -space, then \(LF(X)\approx L^1\), with the latter isomorphism holdig iff. the completion of \(X\) is purely 1-unrectifiable.
2.2.2. Lemma 2.8
Details
- Let \(U\) be a bounded ultrametric space. Then there exist an \(\mathcal{R}\) -tree \(T\) and a rough biLipschitz embedding \(Con(U)\to T\) that is measurable, maps separable subsets to separable subsets, and has coarsely dense image.
- \(Con(U)\) is roughtly biLipschitz equivalent to \(T\).
2.3. Lipschitz Free Spaces
definitions
- basepoint preserving:
- \(Lip_0 (X)\) : the vector space of basepoint preserving Lipschitz funcitons \(f:X\to \mathcal{R}\)
- 再加上norm定义：\(Lip(f)\)，就形成Banach space
- Lipschitz free space :
2.4. Nagata Dimension and Lipschitz Extension
Details
| an open subset of \(\mathcal{R}^n\) | n |
| doubling space | finite Nagata dimension |
| ultrametric space | 0 |
| nontrivial \(\mathcal{R}\) -trees | 1 |
2.5. Hyperbolic Metric Spaces
2.6. Ultrametric Spaces and R-Trees
Ultrametric Spaces
- A metric space is biLipschitz equivalent to an ultrametric space iff. it is snowflake equivalent to an ultrametric space iff. it has Nagata dimension 0.
- Every ultrametric space is 0-hyperbolic and thus isometrically embeds into an \(\mathcal{R}\) -tree
3. Stochastic Embedding and Lipschitz Free Spaces
3.1. Random Maps and Stochastic Embeddings
random maps
- \(\phi\) is pointwise essentially separably valued
- \(\phi\) is almost surely basepoint preserving
3.2. Spaces of Random Lipschitz Functions
3.3. Stochastic Embeddings into \({\mathcal{R}}\) -trees and isomorphisms to \(L^1\) -Spaces
3.3.1. Theorem 3.3 (Theorem A) Theorem
Theorem
Let \(X\) be an infinite, proper, pointed metric space. If \(X\) stochastic biLipshitzly embeds into a pointed \(\mathcal{R}\) -tree, then \(LF(X)\approx L^1\), with the latter isomorphism hodling iff. the completion of \(X\) is purely 1-unrectifiable.
4. Stochastic Embedding into Ultrametric Spaces
Intuitive Introduction
主要目标是producing stochastic biLipschitz embedding of certain classes of Gromov hyperbolic space into \(\mathcal{R}\) -trees.
由于 \(\mathcal{R}\) -trees 的boundary是 ultrametric space
所以作者主要寻找满足什么条件，使得 hyperbolic metric space的boundary可以stochastic biLipschitzly嵌入到ultrametric space.
第4章主要就是寻找这个条件，作者认为合适的条件为：具有finite Nagata dimension
4.0.1. Lemma 4.1
Details
Let \((X, d_X, p)\) be a pointed metric space, \((K, d_K, q)\) a pointed compact metric space, \(D<\infty\), and \(s\in (0,1)\).
If there exists a dense basepoint-containing subset \(A\subset X\) such that every finite basepoint-containing subset of \(A\) stochastic biLipschitzly embeds into \(K\) with distortion \(D\) and scaling factor \(s\), then \(X\) stochastic biLipschitzly embeds into \(K\) with distortion \(D\) and scaling factor \(s\).
如果X的稠密子集可以随机嵌入到K，那么该性质可以延拓到整个X
4.0.2. Theorem 4.3 Theorem
Details
For every \(\alpha\in(0,1)\), the pointed metric space \(([0,1],|\cdot|^{\alpha})\) stochastic biLipschitzly embeds into a compact, pointed ultrametri space with distortion \(D\le \frac{2^{5\alpha+1}}{(2^{\alpha}-1)(2-2^{\alpha})}\)
4.0.3. Theorem B Theorem
Theorem
Let \((X, d)\) be an infinite, compact, finite Nagata-dimensional metric space. Then for every \(\alpha\in (0,1)\),
the metric space \((X, d^{\alpha})\) admits a stochastic biLipschitz embedding into a pointed ultrametric space,
and \(LF(X, d^{\alpha})\approx l^1\) .
4.1. \(l^{0+}\) -small subsets of \(l^{\infty}\)
把Theorem 4.3的作用域扩展到 \(l^{\infty}([0,1])\) 所有的 \(l^{0+}\) -small子集
4.2. Threshold and Snowflake Embeddings Theorem
Theorem
For every bounded, separable, pointed metric space \((X, d, p)\) with finite Nagata dimension and every \(\alpha\in (0,1)\) , the pointed space $(X, dnilnilnilα,p) $ admits a stochastic biLipschitz embedding of distortion \(D<\infty\) into a bounded, separable, pointed ultrametric space, where \(D\) depends only on \(n, \gamma,\alpha\).
4.3. Free Spaces over Distorted Finite Nagata-Dim. Spaces.
5. log-Stochastic Embedings and Hyperbolic Fillings
Intuitive Introduction
第5章重新开始构造从双曲空间到 R-tree的stochastic biLipschitz embedding
目标是理解上述问题如何通过将 \(\partial X\) stochastic biLipschitz嵌入到ultrametric space来实现
这个问题其实就是经典的 hyperbolic filling领域考虑的问题
本文主要使用的技巧来自于 Embeddings of gromov hyperbolic spaces
作者引入了 log-stochastic biLipschitz embedding
Definitions
- uniformly discrete: if there exists \(\theta>0\) such that \(d(x,y)>\theta\) for all \(x\neq y\in X\)
- locally finite: if all its bounded sets are finite.
5.0.1. Theorem 5.7 (Theorem C) Theorem
Theorem
Let \(A\) be an infinite, uniformly discrete, locally finite, pointed metric space, and let \(X\) be a visual, hyperbolic, pointed metric space. If \(A\) rough biLipschitzly embeds into \(X\) and \(\partial X\) log-stochastic biLipschitzly embeds into a bounded, pointed ultrametric space, then \(A\) stochastic biLipschitzly embeds into a pointed \(\mathcal{R}\) -tree and \(LF(A)\approx l^1\).
5.0.2. Corollary 5.8
Corollary
Let \(A\) be an infinite, uniformly discrete, locally finite, pointed metric space, and let \(X\) be a visual, hperbolic, pointed metric space. If \(A\) rough biLipschitzly embeds into \(X\) and \(\partial X\) is separable and finite Nagata-dimensional, then \(A\) stochastic biLipschitzly embeds into a pointed \(\mathcal{R}\) -tree and \(LF(A)\approx l^1\) .
6. The Lipschitz Free Space over \(\mathcal{H}^n\)
6.0.1. Theorem D Theorem
Theorem
the free space over hyperbolic \(n\) -space \(\mathcal{H}^n\) is isomorphic to the free space over Euclidean \(n\) -space \(\mathcal{R}^n\)
\[LF(\mathcal{H}^n)\approx LF(\mathcal{R}^n)\]