论文标题
快速计算曲折的持久性
Fast Computation of Zigzag Persistence
论文作者
论文摘要
曲折持久性是标准持久性的强大扩展，除插入外，还允许删除简单。但是，计算曲折的持久性通常比标准持久性要多得多。我们提出了一种称为fastzigzag的算法，该算法缩小了这一效率差距。我们的主要结果是，输入单纯曲折的过滤可以转换为$Δ$ - complex的细胞非Zigzag过滤，其长度相同，其中单元格是输入简单的副本。 Fastzigzag的此转换步骤的成本很小。此外，原始过滤的条形码可以从新的细胞过滤的条形码轻松读取，因为转换体现了一系列拓扑数据分析中已知的钻石开关。这种看似简单的观察结果开辟了改善锯齿形持久性计算的巨大可能性，因为现在任何有效的标准持久性算法/软件现在都可以应用于计算锯齿形持久性。我们的实验表明，这确实在现有的最新软件中实现了可观的性能增长。
Zigzag persistence is a powerful extension of the standard persistence which allows deletions of simplices besides insertions. However, computing zigzag persistence usually takes considerably more time than the standard persistence. We propose an algorithm called FastZigzag which narrows this efficiency gap. Our main result is that an input simplex-wise zigzag filtration can be converted to a cell-wise non-zigzag filtration of a $Δ$-complex with the same length, where the cells are copies of the input simplices. This conversion step in FastZigzag incurs very little cost. Furthermore, the barcode of the original filtration can be easily read from the barcode of the new cell-wise filtration because the conversion embodies a series of diamond switches known in topological data analysis. This seemingly simple observation opens up the vast possibilities for improving the computation of zigzag persistence because any efficient algorithm/software for standard persistence can now be applied to computing zigzag persistence. Our experiment shows that this indeed achieves substantial performance gain over the existing state-of-the-art softwares.
