论文标题
部分可观测时空混沌系统的无模型预测
Keeping it sparse: Computing Persistent Homology revisited
论文作者
论文摘要
在这项工作中，我们研究了通过高斯消除的几种矩阵减少的变体，这些变体试图保持降低的基质稀疏。动机来自拓扑数据分析的不断增长的领域，其中矩阵还原是计算条形码的主要子例程，这是其中的主要不变。我们提出了两个标准算法的新型变体，称为掉期和回顾性减少。我们在大量数据中对其进行了测试，以比较其他已知变体，以比较它们的效率，并且有时它们会提供相当大的加速。我们还为回顾性变体提供了新颖的输出敏感边界，可以更好地解释立方最差的复杂性结合与矩阵还原的几乎线性实践行为之间的差异。最后，我们提供了几种构造，其中一个变体的性能比其他变体的性能要好得多。
In this work, we study several variants of matrix reduction via Gaussian elimination that try to keep the reduced matrix sparse. The motivation comes from the growing field of topological data analysis where matrix reduction is the major subroutine to compute barcodes, the main invariant therein. We propose two novel variants of the standard algorithm, called swap and retrospective reductions. We test them on a large collection of data against other known variants to compare their efficiency, and we find that sometimes they provide a considerable speed-up. We also present novel output-sensitive bounds for the retrospective variant which better explain the discrepancy between the cubic worst-case complexity bound and the almost linear practical behavior of matrix reduction. Finally, we provide several constructions on which one of the variants performs strictly better than the others.
