文章基本信息

标题：Elder-Rule-Staircodes for Augmented Metric Spaces
本地全文：下载
作者：Chen Cai ; Woojin Kim ; Facundo Mmoli 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2020
卷号：164
页码：26:1-26:17
DOI：10.4230/LIPIcs.SoCG.2020.26
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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 2-parameter filtration. However, the resulting 2-parameter persistence module 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 a 1-parameter filtration, we propose a barcode-like summary, called the elder-rule-staircode, as a way to encode the zeroth homology of the 2-parameter filtration induced by a finite augmented metric space. Specifically, given a finite (X, d_X, f_X), its elder-rule-staircode consists of n = X number of staircase-like 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 2-parameter filtration induced by (X, d_X, f_X) can all be efficiently computed once the elder-rule-staircode is given. Furthermore, for certain special cases, this staircode corresponds exactly to the set of indecomposables of the zeroth homology of the 2-parameter filtration. Finally, we develop and implement an efficient algorithm to compute the elder-rule-staircode 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.
关键词：Persistent homology; Multiparameter persistence; Barcodes; Elder rule; Hierarchical clustering; Graded Betti numbers