跳到正文
格致开物MATHWIKI

持久图

持久图(persistence diagram)把持久同调中的生存区间表示为出生—死亡平面上的点:有限区间 [b,d) 对应点 (b,d)。它是按同调维数区分、允许重数的点多重集;两个类即使具有相同出生与死亡值,也不能合并成只计一次的点。

横坐标表示出生参数,纵坐标表示死亡参数。某点离对角线较远,表示两端参数差较大;它的位置不直接给出孔洞在原始点云中的坐标、面积或形状。无限延续的类另行记录为 (b,∞)。

从条形码读到坐标

考虑持久同调词条中的三顶点过滤:顶点在零加入,两条连接边分别在一、二加入,闭合第三边在三加入,三角面在五加入。它的零维区间为 [0,1)、[0,2)、[0,∞),一维区间为 [3,5)。

零维三个条形区间分别到1、2和无穷,一维条形区间从3到5
有限条的左端实心、右端空心,表示左闭右开。顶端长条带箭头,表示无限延续,不是恰在图窗右边结束。

对应的有限持久图为 D0={(0,1),(0,2)},D1={(3,5)}, 另外在零维记录一个本质点 (0,∞)。这个点不能放在纵坐标六的位置来代替无穷;六只是下图显示范围的上界。

出生死亡平面中零维点位于0,1和0,2,一维点位于3,5,并标出死亡等于出生的对角线
颜色与点形同时区分维数。本质点另行记录;有限平面中的点没有因此被计成全部同调类。

一维点 (3,5) 的持续长度为 5−3=2;它在参数四存在,在参数五已经消失。有限区间转换成点没有丢失端点与重数信息,但图本身一般不能恢复原始空间。

用持久图计算跨尺度秩

固定维数 k,对 s≤t,持续到后期的秩为 βks,t=#{(b,d)∈Dk:b≤s, d>t}, 按重数计数,并把满足条件的本质点包括在内。它对应平面上“出生不晚于 s、死亡晚于 t”的区域。

推导。 区间 [b,d) 对跨阶段映射贡献一个独立方向,恰好要求 b≤s≤t<d。不同区间的贡献相加,便得到计数式。主例中,β00,1.5=2,因为 (0,2) 与 (0,∞) 仍符合条件;(0,1) 已经死亡。同时 β13,4=1、β13,5=0。区间、持久图和跨尺度秩之间的联系见Edelsbrunner与Harer的综述。[1]

如果两个一维类都在三出生、五死亡,图中 (3,5) 的重数为二,跨尺度秩也贡献二。绘图时可以标注“×2”,而不能因两个标记恰好覆盖就把它当作一个类。比较不同同调维数时,应保留维数标签,不能把零维合并与一维环路直接匹配。

对角线与瓶颈距离

比较两幅持久图时,某一幅中的短区间可能没有对应的另一点。标准做法是在两图中都加入具有无限重数的对角线 Δ={(a,a):a∈ℝ}. 非对角点可以匹配到另一图的非对角点,也可匹配到对角线。这表示允许一个有限长度特征在另一图中消失,而不是强行配到无关特征。

对有限死亡点,采用最大坐标差 ‖(b,d)−(b′,d′)‖∞=max⁡{|b−b′|,|d−d′|}. 在同一维数内,瓶颈距离是所有合法配对的最大代价的下确界: dB(D,E)=infγsupp∈D∪Δ‖p−γ(p)‖∞. 这里 γ 按重数给出双射,对角线可提供足够多的匹配点。本质点只能与本质点以有限代价匹配;其代价为出生值差的绝对值。若本质点数不同,普通这一约定下的瓶颈距离为无穷,不能随便把本质点投到有限对角线。[2]

点 p=(b,d) 到对角线的最小代价是 dist∞(p,Δ)=d−b2. 证明。 对任意 a, d−b≤|d−a|+|a−b|≤2max⁡{|d−a|,|a−b|}. 故代价至少为 (d−b)/2。选择 a=(b+d)/2 两项相等,达到下界。这个距离采用 L∞ 范数,不是欧氏垂距 (d−b)/2。

点3,5与3.2,5.1的最大坐标差为0.2,点3,5到对角点4,4的代价为1
配到附近另一点与配到对角线是不同选择。虚线的画法帮助定位坐标差,距离数值仍由最大范数定义。

一个可以完整比较的例子

设 D={(3,5)}、E={(3.2,5.1)},均为同一维数,且没有本质点。将两非对角点直接配对,代价为 max⁡{|3−3.2|,|5−5.1|}=0.2. 另一类选择是各自配到对角线;最优代价分别为一与 (5.1−3.2)/2=0.95,配对的最大代价为一。每图只有一个非对角点,合法匹配在这两类中必居其一,所以 dB(D,E)=min⁡(0.2,1)=0.2. 若变式中把 E 改为空图,则唯一的非对角点只能配到对角线,距离为一。两幅空图的距离则为零。

稳定性与数据解释

一个常用稳定性结论适用于同一非空有限单纯复形上的两组实数过滤值 f,g,要求各自都不早于自己的面,使用同一个系数域与同调维数。相应持久图满足 dB(Dk(f),Dk(g))≤maxσ∈K|f(σ)−g(σ)|. 它控制同一过滤对象上的一致扰动,是稳定性定理的有限单形过滤版本。与连续函数表述的联系可以通过重心细分建立:给每个单形对应的细分顶点赋予它的过滤值,再在细分单形内作分片线性延拓;子水平集与对应子复形具有相容的同调,而两延拓函数的最大差不超过上述单形值的最大差。此处引用稳定性定理,不展开其一般证明;前面的读图与配对算例不依赖这段证明。对不同点云或不同距离函数应用类似结论,还需建立相应的比较和扰动界,不能直接套用右侧这个同一单形集合上的差值。

若一个类的持续长度大于 2δ,在瓶颈代价不超过 δ 的匹配中,它不能配到对角线,因为对角线代价超过 δ。这个推论说明了在给定扰动界下的匹配限制,并不证明该类具有领域研究中的重要性。短条可能来自小尺度真实结构,长条也可能来自采样方式或错误的度量。

报告一幅持久图,应同时给出复形构造、参数约定、系数域、同调维数、有限截断与无穷类的处理。参数若是距离,持续长度具有距离单位;平方半径过滤的长度则具有平方距离单位。不同约定的图可以转换后比较,但不能把原始端点直接混在同一坐标意义下。

参考文献

  1. ↑ Herbert Edelsbrunner、John Harer,Persistent Homology — a Survey,§2及§6。
  2. ↑ David Cohen-Steiner、Herbert Edelsbrunner、John Harer,Stability of Persistence Diagrams,§2“Background”和§3,会议版;期刊版DOI:10.1007/s00454-006-1276-5。