Cai, Chen ;
Kim, Woojin ;
Mémoli, Facundo ;
Wang, Yusu
ElderRuleStaircodes for Augmented Metric Spaces
Abstract
An augmented metric space (X, d_X, f_X) is a metric space (X, d_X) equipped with a function f_X: X → ℝ. It arises commonly in practice, e.g, a point cloud X in ℝ^d where each point x∈ X has a density function value f_X(x) associated to it. Such an augmented metric space naturally gives rise to a 2parameter filtration. However, the resulting 2parameter persistence module could still be of wild representation type, and may not have simple indecomposables.
In this paper, motivated by the elderrule for the zeroth homology of a 1parameter filtration, we propose a barcodelike summary, called the elderrulestaircode, as a way to encode the zeroth homology of the 2parameter filtration induced by a finite augmented metric space. Specifically, given a finite (X, d_X, f_X), its elderrulestaircode consists of n = X number of staircaselike blocks in the plane. We show that the fibered barcode, the fibered merge tree, and the graded Betti numbers associated to the zeroth homology of the 2parameter filtration induced by (X, d_X, f_X) can all be efficiently computed once the elderrulestaircode is given. Furthermore, for certain special cases, this staircode corresponds exactly to the set of indecomposables of the zeroth homology of the 2parameter filtration. Finally, we develop and implement an efficient algorithm to compute the elderrulestaircode in O(n²log n) time, which can be improved to O(n²α(n)) if X is from a fixed dimensional Euclidean space ℝ^d, where α(n) is the inverse Ackermann function.
BibTeX  Entry
@InProceedings{cai_et_al:LIPIcs:2020:12184,
author = {Chen Cai and Woojin Kim and Facundo M{\'e}moli and Yusu Wang},
title = {{ElderRuleStaircodes for Augmented Metric Spaces}},
booktitle = {36th International Symposium on Computational Geometry (SoCG 2020)},
pages = {26:126:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771436},
ISSN = {18688969},
year = {2020},
volume = {164},
editor = {Sergio Cabello and Danny Z. Chen},
publisher = {Schloss DagstuhlLeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12184},
URN = {urn:nbn:de:0030drops121848},
doi = {10.4230/LIPIcs.SoCG.2020.26},
annote = {Keywords: Persistent homology, Multiparameter persistence, Barcodes, Elder rule, Hierarchical clustering, Graded Betti numbers}
}
08.06.2020
Keywords: 

Persistent homology, Multiparameter persistence, Barcodes, Elder rule, Hierarchical clustering, Graded Betti numbers 
Seminar: 

36th International Symposium on Computational Geometry (SoCG 2020)

Issue date: 

2020 
Date of publication: 

08.06.2020 