Elder-Rule-Staircodes for Augmented Metric Spaces

Abstract

An augmented metric space is a metric space $(X,d_X)$ equipped with a function $f_X:X\to \mathbb{R}$. This type of data arises commonly in practice, e.g, a point cloud $X$ in ${\mathbb{R}}^d$ where each point $x\in X$ has a density function value $f_X(x)$ associated to it. An augmented metric space $(X,d_X,f_X)$ naturally gives rise to a 2-parameter filtration $\mathcal{K}$. However, the resulting 2-parameter persistent homology ${\mathrm{H}}_{\bullet }(\mathcal{K})$ could still be of wild representation type, and may not have simple indecomposables. In this paper, motivated by the elder-rule for the zeroth homology of 1-parameter filtration, we propose a barcode-like summary, called the elder-rule-staircode, as a way to encode ${\mathrm{H}}_0(\mathcal{K})$. Specifically, if $n=|X|$, the elder-rule-staircode consists of $n$ number of staircase-like blocks in the plane. We show that if ${\mathrm{H}}_0(\mathcal{K})$ is interval decomposable, then the barcode of ${\mathrm{H}}_0(\mathcal{K})$ is equal to the elder-rule-staircode. Furthermore, regardless of the interval decomposability, the fibered barcode, the dimension function (a.k.a. the Hilbert function), and the graded Betti numbers of ${\mathrm{H}}_0(\mathcal{K})$ can all be efficiently computed once the elder-rule-staircode is given. Finally, we develop and implement an efficient algorithm to compute the elder-rule-staircode in $O(n^2\log n)$ time, which can be improved to $O(n^2\alpha (n))$ if $X$ is from a fixed dimensional Euclidean space ${\mathbb{R}}^d$, where $\alpha (n)$ is the inverse Ackermann function.

arXiv commentA few important questions considered in the previous version have been settled; see Example 4.12 and Section 4.3 in particular. The paper has been reorganized. This is the full version of the paper in the Proceedings of the 36th International Symposium on Computational Geometry (SoCG 2020); 41 pages, 17 figures

References in corpus (18)

• The Theory of the Interleaving Distance on Multidimensional Persistence Modules
• Deep Learning with Topological Signatures
• Interactive Visualization of 2-D Persistence Modules
• Generalized Persistence Diagrams
• PersLay: A Neural Network Layer for Persistence Diagrams and New Graph Topological Signatures
• Algebraic Stability of Zigzag Persistence Modules
• Learning metrics for persistence-based summaries and applications for graph classification
• Cotorsion torsion triples and the representation theory of filtered hierarchical clustering
• Spatio-temporal Persistent Homology for Dynamic Metric Spaces
• Computing Bottleneck Distance for Multi-parameter Interval Decomposable Persistence Modules
• Data structures for real multiparameter persistence modules
• Generalized Persistence Algorithm for Decomposing Multi-parameter Persistence Modules
• Positivity of Multiparameter Persistence Diagrams and Bottleneck Stability
• Computing Minimal Presentations and Bigraded Betti Numbers of 2-Parameter Persistent Homology
• Understanding the Power of Persistence Pairing via Permutation Test
• A refinement of multi-dimensional persistence
• On Approximation of $2$D Persistence Modules by Interval-decomposables
• On Interval Decomposability of 2D Persistence Modules

Cited by in corpus (1)

• Multi-parameter Module Approximation: an efficient and interpretable invariant for multi-parameter persistence modules with guarantees