Zigzag Persistence via Reflections and Transpositions
Zigzag Persistence via Reflections and Transpositions
复制标题
通过反射和换位实现之字形持久
DOI：
10.1137/1.9781611973730.14
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
S. Oudot
中科院分区：
文献类型：
--
作者：
Clément Maria;S. Oudot
我们介绍了一个新的算法计算锯齿持久性，设计在相同的精神作为标准的持久性算法。我们的算法减少了一个单一的矩阵，保持一个明确的一组链编码的持续同源性的当前之字形，并更新它下单纯形插入和删除。最坏情况下的总运行时间与通常的三次边界相匹配。
与标准持久性算法的一个显著区别是，我们不插入或删除新的单形“在”之字形的“结束”，而是“在中间”。为了做到这一点，我们使用箭头反射和转置，与反射函子理论中的反射函子相同。我们的分析介绍了新的类型的反射在非线性表示理论：“内射和满射钻石”。它还介绍了“换位菱形”，箭头换位模型。对于每种类型的钻石，我们都能够预测区间分解和相关兼容基底的变化。箭头转置已经研究了标准的持续同源性的背景下，我们将研究延伸到锯齿形持久性的背景下。对于这两种类型的转换，我们提供了简单的程序来更新的区间分解和相关的兼容的同调基。
We introduce a new algorithm for computing zigzag persistence, designed in the same spirit as the standard persistence algorithm. Our algorithm reduces a single matrix, maintains an explicit set of chains encoding the persistent homology of the current zigzag, and updates it under simplex insertions and removals. The total worst-case running time matches the usual cubic bound.
A noticeable difference with the standard persistence algorithm is that we do not insert or remove new simplices "at the end" of the zigzag, but rather "in the middle". To do so, we use arrow reflections and transpositions, in the same spirit as reflection functors in quiver theory. Our analysis introduces new kinds of reflections in quiver representation theory: the "injective and surjective diamonds". It also introduces the "transposition diamond" which models arrow transpositions. For each type of diamond we are able to predict the changes in the interval decomposition and associated compatible bases. Arrow transpositions have been studied previously in the context of standard persistent homology, and we extend the study to the context of zigzag persistence. For both types of transformations, we provide simple procedures to update the interval decomposition and associated compatible homology basis.