《Power Voronoi图的数学原理》

Power Voronoi图的数学原理

Power Voronoi图（也称为加权Voronoi图或幂图）是标准Voronoi图的推广形式，在最优传输理论、计算几何和机器学习中有着重要应用。以下系统阐述其数学原理：

1. 基本定义与几何解释

1.1 标准Voronoi图回顾

给定欧氏空间 ${\mathbb{R}}^n$ 中的一组点 {y1,y2,…,yk}\{y_1, y_2, \dots, y_k\}{y1​,y2​,…,yk​}，标准Voronoi图将空间划分为 $k$ 个区域：
Vj={m∈Rn∣∥m−yj∥≤∥m−yi∥,∀i≠j}V_j = \{m \in \mathbb{R}^n \mid \|m - y_j\| \leq \|m - y_i\|, \quad \forall i \neq j\}Vj​={m∈Rn∣∥m−yj​∥≤∥m−yi​∥,∀i=j}
每个区域 $V_j$ 包含所有离 $y_j$ 比离其他点更近的点。

1.2 Power Voronoi图的定义

给定一组点 {y1,y2,…,yk}⊂Rn\{y_1, y_2, \dots, y_k\} \subset \mathbb{R}^n{y1​,y2​,…,yk​}⊂Rn 和权重 {r12,r22,…,rk2}\{r_1^2, r_2^2, \dots, r_k^2\}{r12​,r22​,…,rk2​}，Power Voronoi图定义为：
Vj={m∈M∣∥m−yj∥2−rj2≤∥m−yi∥2−ri2,∀i≠j}V_j = \{m \in M \mid \|m - y_j\|^2 - r_j^2 \leq \|m - y_i\|^2 - r_i^2, \quad \forall i \neq j\}Vj​={m∈M∣∥m−yj​∥2−rj2​≤∥m−yi​∥2−ri2​,∀i=j}

几何解释：

• $\Vert m-y_j{\Vert }^2-r_j^2$ 称为幂距离（power distance）
• 每个单元 $V_j$ 由不等式定义，表示点 $m$ 到 $y_j$ 的"修正距离"最小
• 当 $r_j=0$ 时，退化为标准Voronoi图

1.3 等价形式

通过代数变换，可得：
$$\Vert m-y_j{\Vert }^2-r_j^2\le \Vert m-y_i{\Vert }^2-r_i^2$$
$$\Rightarrow m^T{y}_j-\frac{1}{2}(y_j^T{y}_j+r_j^2)\le m^T{y}_i-\frac{1}{2}(y_i^T{y}_i+r_i^2)$$

令 $h_j=-\frac{1}{2}(\Vert y_j{\Vert }^2+r_j^2)$，则等价于：
$$m^T{y}_j+h_j\le m^T{y}_i+h_i,\forall i\ne j$$

2. 与凸函数的联系

2.1 分段线性凸函数

定义分段线性凸函数：
$${\theta }_h(x)=\max \{⟨x,y_j⟩+h_j\},j=1,\dots ,k$$

关键性质：

• ${\theta }_h(x)$ 是凸函数
• 其次微分 $\partial {\theta }_h(x)$ 是单值的，且 $\partial {\theta }_h(x)=y_j$ 当 $x\in V_j(h)$
• 梯度映射 $\nabla {\theta }_h$ 将每个Voronoi单元 $V_j$ 映射到点 $y_j$

2.2 Alexandrov定理

论文中引用的Alexandrov定理指出：

假设 $\Omega$ 是 ${\mathbb{R}}^n$ 中具有非空内部的紧凸多面体，$y_1,\dots ,y_k\subset {\mathbb{R}}^n$ 是 $k$ 个不同点，${\nu }_1,\dots ,{\nu }_k>0$ 满足 ${\sum }_{j=1}^k{\nu }_j=\text{vol}(\Omega )$。存在唯一的向量 $h=(h_1,\dots ,h_k{)}^T$（在平移意义下），使得分段线性凸函数 ${\theta }_h(x)=\max \{⟨x,y_j⟩+h_j\}$ 满足：
$$\text{vol}(x\in \Omega \mid \nabla {\theta }_h(x)=y_j)={\nu }_j$$

物理意义：

• 该定理确保了给定目标测度 $\nu$，存在唯一的power Voronoi图实现测度保持映射

2.3 Brenier定理

Brenier定理建立了最优传输与凸函数的关系：

梯度映射 $\nabla {\theta }_h$ 提供了Monge问题的解，即最小化传输成本 ${\int }_{\Omega }\Vert x-{\theta }_h(x){\Vert }^2$

关键结论：

• 最优传输映射 $T$ 可表示为凸函数的梯度：$T=\nabla \varphi$
• 在离散情况下，$\varphi$ 是分段线性凸函数 ${\theta }_h$
• Power Voronoi图是该凸函数的次微分分解

3. 在最优传输中的应用

3.1 半离散最优传输

在变分Wasserstein聚类中，考虑半离散最优传输问题：

• 源分布 $X(x,\mu )$：连续或离散经验分布
• 目标分布 $Y(y,\nu )$：稀疏离散测度 $\{(y_j,{\nu }_j)\}$

Power Voronoi图提供了测度保持映射 $\pi :X\to Y$，使得：
$$\mu (V_j(h))={\nu }_j,j=1,\dots ,k$$

3.2 能量函数与优化

定义能量函数：
$$E(h)={\int }_{\Omega }{\theta }_h(x)\mu (x)dx-\sum _{j=1}^k{\nu }_j{h}_j$$

梯度：
$$\nabla E(h)=(w_1(h)-{\nu }_1,\dots ,w_k(h)-{\nu }_k{)}^T$$
其中 $w_j(h)={\sum }_{x\in V_j}\mu (x)$ 是第 $j$ 个单元的总质量。

Hessian矩阵：
$$H=\frac{{\partial }^{2}E(h)}{\partial h_i\partial h_j}=\{\begin{array}{ll}{\sum }_l\frac{{\int }_{f_{il}}\mu (x)dx}{\Vert y_l-y_i\Vert },& i=j,\forall l,\text{s.t. }{f}_{il}\ne \varnothing \\ -\frac{{\int }_{f_{ij}}\mu (x)dx}{\Vert y_j-y_i\Vert },& i\ne j,f_{ij}\ne \varnothing \\ 0,& i\ne j,f_{ij}=\varnothing \end{array}$$
其中 $f_{ij}$ 是相邻单元 $V_i$ 和 $V_j$ 的交集。

优化过程：
通过牛顿法迭代求解：
$$h^{(t+1)}\leftarrow h^{(t)}-\lambda H^{-1}\nabla E(h)$$

4. 几何性质与计算

4.1 凸分割性质

Power Voronoi图具有以下重要性质：

• 每个单元 $V_j$ 是凸集
• 单元边界是超平面（在2D中是直线，3D中是平面）
• 整个划分是凸分割

4.2 边界计算

相邻单元 $V_i$ 和 $V_j$ 之间的边界由以下方程定义：
$$\Vert m-y_i{\Vert }^2-r_i^2=\Vert m-y_j{\Vert }^2-r_j^2$$
$$\Rightarrow 2m^T(y_j-y_i)=\Vert y_j{\Vert }^2-\Vert y_i{\Vert }^2+r_i^2-r_j^2$$

这是一个超平面方程，法向量为 $y_j-y_i$。

4.3 体积计算

单元 $V_j$ 的体积（或质量）为：
$$w_j(h)={\int }_{V_j}\mu (x)dx=\sum _{x\in V_j}\mu (x)(\text{离散情况})$$

在优化过程中，需要计算相邻单元交集 $f_{ij}$ 的质量：
$${\int }_{f_{ij}}\mu (x)dx$$

5. 与k-means聚类的联系

5.1 Wasserstein均值问题

当目标分布 $Y$ 是稀疏的，Wasserstein距离最小化问题退化为：
$$\underset{Y\in P(M)}{\inf }{W}_2^2(X,Y)=\underset{Y\in P(M),\pi \in P(M\times M)}{\inf }\sum _{y_j=\pi (x_i)}{\mu }_i\Vert x_i-y_j{\Vert }^2$$

这正是加权k-means聚类问题。

5.2 变分Wasserstein聚类

在变分Wasserstein聚类中：

• Power Voronoi图定义了样本到簇的分配
• 通过调整 $h$，使每个单元的总质量 $w_j(h)$ 等于目标测度 ${\nu }_j$
• 簇中心 $y_j$ 通过加权平均更新：
  $$y_j=\frac{{\sum }_{x\in V_j}{\mu }_i{x}_i}{{\sum }_{x\in V_j}{\mu }_i}$$

6. 算法实现

6.1 更新Power Voronoi图的算法

def Variational_OT(X, Y, mu, nu, epsilon):h = np.zeros(k)  # 初始化参数while True:# 1. 更新Power Voronoi图V = compute_power_diagram(Y, h)# 2. 计算单元权重w = [sum(mu[x] for x in V[j]) for j in range(k)]# 3. 计算梯度和Hessiangrad = w - nuH = compute_hessian(Y, V, mu)# 4. 牛顿法更新hdelta_h = -np.linalg.solve(H, grad)h = h + delta_h# 5. 检查收敛if np.linalg.norm(grad) < epsilon:breakreturn V, h

6.2 变分Wasserstein聚类算法

def Variational_Wasserstein_Clustering(X, mu, k):# 初始化簇中心Y = initialize_centroids(X, k)nu = compute_target_measure(k)  # 通常为均匀分布while not converged:# 1. 更新Power Voronoi图V, h = Variational_OT(X, Y, mu, nu, epsilon)# 2. 更新簇中心for j in range(k):Y[j] = sum(mu[x] * x for x in V[j]) / sum(mu[x] for x in V[j])return Y, V

7. 物理意义与应用

7.1 测度保持映射

Power Voronoi图实现了从源分布到目标分布的测度保持映射：

• 每个Voronoi单元 $V_j$ 的总质量等于目标测度 ${\nu }_j$
• 没有质量分裂，符合Monge型最优传输

7.2 几何变形解释

考虑二维平面上的变形：

• 当 $w_j(h)>{\nu }_j$：单元 $V_j$ 质量过大，需要缩小
  • 减小 $h_j$，使边界向 $y_j$ 移动
• 当 $w_j(h)<{\nu }_j$：单元 $V_j$ 质量过小，需要扩大
  • 增加 $h_j$，使边界远离 $y_j$

7.3 应用场景

• 域适应：将源域映射到目标域，同时保持分布特性
• 网格变形：根据曲率重新分布顶点，高曲率区域顶点更密集
• 表示学习：将高维数据嵌入低维空间，保留重要结构

8. 与标准Voronoi图的对比

特性	标准Voronoi图	Power Voronoi图
定义	$|m-y_j|\le |m-y_i|$	$|m-y_j{|}^2-r_j^2\le |m-y_i{|}^2-r_i^2$
参数	仅中心点 $y_j$	中心点 $y_j$ 和权重 $r_j^2$
自由度	低	高（可通过 $h_j$ 调整）
测度保持	不能	可以（通过调整 $h_j$）
应用场景	一般空间划分	最优传输、测度保持映射

9. 总结

Power Voronoi图是标准Voronoi图的推广，其核心数学原理包括：

1. 定义基础：通过幂距离 $\Vert m-y_j{\Vert }^2-r_j^2$ 定义单元边界
2. 凸函数联系：与分段线性凸函数 ${\theta }_h(x)=\max \{⟨x,y_j⟩+h_j\}$ 直接相关
3. 最优传输角色：实现Monge型测度保持映射，解决半离散最优传输问题
4. 变分原理：通过优化能量函数 $E(h)$ 调整划分以满足目标测度
5. 几何性质：保持凸分割，边界为超平面

在变分Wasserstein聚类中，Power Voronoi图是连接最优传输与k-means聚类的关键桥梁，它不仅提供了样本到簇的分配，还确保了测度守恒，使算法能够同时优化聚类质量和Wasserstein距离。其数学优雅性和计算效率使其成为处理分布匹配和聚类问题的有力工具。

---

Kantorovich将Monge型最优传输问题松弛为寻找满足边缘约束的耦合集合中的最小化问题，这一松弛使得问题更具普适性和可解性。以下是详细解释：

---

1. 问题背景

Monge型最优传输要求找到一个测度保持映射 $T:X\to Y$，使得：
$$\underset{T_{\#}\mu =\nu }{\inf }{\int }_{X}c(x,T(x))d\mu (x),$$
其中 $T_{\#}\mu =\nu$ 表示 $T$ 是测度保持映射（即 $\mu (T^{-1}(B))=\nu (B),\forall B\subset Y$）。然而，这类问题可能存在无解的情况（例如当 $X$ 和 $Y$ 的维度不同或测度不满足正则性条件时）。

---

2. Kantorovich的松弛

Kantorovich提出将问题转化为寻找联合概率测度 $\pi \in \Pi (\mu ,\nu )$，其中：

• 耦合集合 $\Pi (\mu ,\nu )$ 定义为所有满足以下边缘约束的联合测度：
  • 行约束：$\pi (\cdot ,Y)=\mu$（对任意 $A\subset X$，${\int }_A\pi (x,y)dy=\mu (A)$）
  • 列约束：$\pi (X,\cdot )=\nu$（对任意 $B\subset Y$，${\int }_B\pi (x,y)dx=\nu (B)$）

目标函数变为：
$$\underset{\pi \in \Pi (\mu ,\nu )}{\inf }{\int }_{X\times Y}c(x,y)d\pi (x,y),$$
其中 $c(x,y)$ 是传输成本函数（通常取为距离的 $p$ 次幂，如 $c(x,y)=d(x,y{)}^p$）。

---

3. 关键思想

• 质量分割：允许一个源点 $x$ 的质量被分配到多个目标点 $y$，而非必须全部映射到一个点。
• 联合测度：$\pi (x,y)$ 表示将质量从 $x$ 分配到 $y$ 的比例。
• 边缘约束：确保总质量守恒：
  • 对所有 $x\in X$，${\int }_Y\pi (x,y)dy=\mu (x)$（源测度的局部质量守恒）。
  • 对所有 $y\in Y$，${\int }_X\pi (x,y)dx=\nu (y)$（目标测度的局部质量守恒）。

---

4. 数学表达

在离散情况下，若 $\mu ={\sum }_{i=1}^n{\mu }_i{\delta }_{x_i}$，$\nu ={\sum }_{j=1}^m{\nu }_j{\delta }_{y_j}$，则：

• 耦合 $\pi$ 是一个 $n\times m$ 矩阵 {πij}\{\pi_{ij}\}{πij​}，满足：
  $$\sum _{j=1}^m{\pi }_{ij}={\mu }_i,\forall i,$$
  $$\sum _{i=1}^n{\pi }_{ij}={\nu }_j,\forall j.$$
• 目标函数变为：
  $$\underset{\pi }{\min }\sum _{i=1}^n\sum _{j=1}^{m}c(x_i,y_j){\pi }_{ij},$$
  这是一个线性规划问题。

---

5. 与Monge问题的关系

• 包含关系：Monge问题的解（若存在）对应于Kantorovich问题的一个特殊耦合（即 $\pi (x,y)=\delta [y=T(x)]d\mu (x)$）。
• 存在性：Kantorovich问题始终存在解（由Kantorovich-Rubinstein定理保证），而Monge问题可能无解。
• 几何意义：Kantorovich解允许质量分裂，更适合处理高维或非光滑问题，但失去了Monge解的显式映射特性。

---

6. 在Wasserstein距离中的应用

Kantorovich松弛直接导出了Wasserstein距离的定义：
$$W_p(\mu ,\nu )={\left(\underset{\pi \in \Pi (\mu ,\nu )}{\inf }{\int }_{X\times Y}d(x,y{)}^{p}d\pi (x,y)\right)}^{1/p}.$$
这是概率测度空间上的有效距离度量，具有良好的数学性质（如三角不等式）。

---

7. 实际意义

• 计算优势：Kantorovich问题可通过线性规划求解，而Monge问题通常需要非凸优化。
• 灵活性：适用于更广泛的测度类型（如连续测度、混合型测度）。
• 应用广泛性：在图像处理、机器学习（如GANs）、经济学等领域有广泛应用。

---

总结

Kantorovich的松弛通过引入耦合测度，将严格的测度保持映射扩展为允许质量分割的联合测度优化，从而解决了Monge问题的局限性。这一松弛不仅保证了问题的可行性，还提供了强大的数学工具（如线性规划）和理论保障（如Wasserstein距离的良定义），成为现代最优传输理论的核心。