Barcodes of Towers and a Streaming Algorithm for Persistent Homology
Barcodes of Towers and a Streaming Algorithm for Persistent Homology
复制标题
塔的条形码和持久同源的流算法
DOI：
--
复制
发表时间：
2017
影响因子：
0.8
通讯作者：
Hannah Schreiber
中科院分区：
文献类型：
--
作者：
Michael Kerber;Hannah Schreiber
塔是由单纯映射连接的一系列单纯复形。我们展示了如何计算过滤，即一系列嵌套单纯复形，具有与塔相同的持久条形码。我们的方法基于 Dey 等人的圆锥策略。 （SoCG，2014）。我们表明，这种方法的一种变体产生的过滤渐近仅略大于塔，并且在理论上和实践中都可以通过流算法有效地计算。此外，我们表明我们的方法可以与流算法相结合，通过矩阵简化来计算塔的条形码。该算法的空间复杂度不取决于塔的长度，而是取决于塔内任何子复合体的最大尺寸。实验评估表明，我们的方法可以有效地处理具有数十亿个复合体的塔。
A tower is a sequence of simplicial complexes connected by simplicial maps. We show how to compute a filtration, a sequence of nested simplicial complexes, with the same persistent barcode as the tower. Our approach is based on the coning strategy by Dey et al. (SoCG, 2014). We show that a variant of this approach yields a filtration that is asymptotically only marginally larger than the tower and can be efficiently computed by a streaming algorithm, both in theory and in practice. Furthermore, we show that our approach can be combined with a streaming algorithm to compute the barcode of the tower via matrix reduction. The space complexity of the algorithm does not depend on the length of the tower, but the maximal size of any subcomplex within the tower. Experimental evaluations show that our approach can efficiently handle towers with billions of complexes.