Output-sensitive Computation of Generalized Persistence Diagrams for 2-filtrations
| arXiv:2112.03980, 2021. |
|
Manuscript |
| arXiv: | 2112.0398 |
Abstract
When persistence diagrams are formalized as the Mobius inversion of the birth-death function, they naturally generalize to the multi-parameter setting and enjoy many of the key properties, such as stability, that we expect in applications. The direct definition in the 2-parameter setting, and the corresponding brute-force algorithm to compute them, require Ω(n4) operations. But the size of the generalized persistence diagram, C, can be as low as linear (and as high as cubic). We elucidate a connection between the 2-parameter and the ordinary 1-parameter settings, which allows us to design an output-sensitive algorithm, whose running time is in O(n3+Cn).
When persistence diagrams are formalized as the Mobius inversion of the birth-death function, they naturally generalize to the multi-parameter setting and enjoy many of the key properties, such as stability, that we expect in applications. The direct definition in the 2-parameter setting, and the corresponding brute-force algorithm to compute them, require Ω(n4) operations. But the size of the generalized persistence diagram, C, can be as low as linear (and as high as cubic). We elucidate a connection between the 2-parameter and the ordinary 1-parameter settings, which allows us to design an output-sensitive algorithm, whose running time is in O(n3+Cn).