Computing Zigzag Persistent Cohomology
Computing Zigzag Persistent Cohomology
复制标题
计算 Zigzag 持久上同调
DOI：
--
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
S. Oudot
中科院分区：
文献类型：
--
作者：
Clément Maria;S. Oudot
Zigzag持久化同调是持久化同调的强大概括，它不仅允许人们以更少的噪声和使用更少的内存来计算持久化图，而且还可以在新的应用领域中使用持久化。然而，由于该理论的代数处理的复杂性增加，该领域的大多数算法结果仍然具有理论性质。
本文描述了一种计算之字形持久度的有效算法，强调了其实用价值。该算法是一种Z字形持久上同调算法，基于Z字形序列内的反射和换位变换的对偶化。
我们对该算法进行了广泛的实验研究。我们沿着两个方向对该算法进行了研究。首先，我们将其性能与Zigzag持久化同调算法进行了比较，并展示了上同调算法对Zigzag持久化的兴趣。其次，我们通过将之字形持久化与该领域最先进的方法，特别是标准持久同调和稀疏过滤的优化算法进行比较，来说明它在拓扑数据分析中的兴趣。我们比较了不同算法的内存和时间复杂度，以及输出持久图的质量。
Zigzag persistent homology is a powerful generalisation of persistent homology that allows one not only to compute persistence diagrams with less noise and using less memory, but also to use persistence in new fields of application. However, due to the increase in complexity of the algebraic treatment of the theory, most algorithmic results in the field have remained of theoretical nature.
This article describes an efficient algorithm to compute zigzag persistence, emphasising on its practical interest. The algorithm is a zigzag persistent cohomology algorithm, based on the dualisation of reflections and transpositions transformations within the zigzag sequence.
We provide an extensive experimental study of the algorithm. We study the algorithm along two directions. First, we compare its performance with zigzag persistent homology algorithm and show the interest of cohomology in zigzag persistence. Second, we illustrate the interest of zigzag persistence in topological data analysis by comparing it to state of the art methods in the field, specifically optimised algorithm for standard persistent homology and sparse filtrations. We compare the memory and time complexities of the different algorithms, as well as the quality of the output persistence diagrams.