Elder-rule-staircodes for Augmented Metric Spaces
Elder-rule-staircodes for Augmented Metric Spaces
复制标题
DOI：
10.1137/20m1353605
复制
发表时间：
2020-03
期刊：
影响因子：
--
通讯作者：
Chen Cai;Woojin Kim;F. Mémoli;Yusu Wang
中科院分区：
文献类型：
--
作者：
Chen Cai;Woojin Kim;F. Mémoli;Yusu Wang
增强度量空间是配备函数$ f_x的度量空间$（x，d_x）$：x \ to \ mathbb {r} $。这种类型的数据通常是在实践中出现的，例如，$ \ mathbb {r}^d $中的点云$ x $，其中x $中的每个点$ x \具有密度函数值$ f_x（x）$与之相关。增强度量空间$（x，d_x，f_x）$自然产生了2个参数过滤$ \ Mathcal {K} $。但是，所得的2-参数持续同源性$ \ mathrm {h} _ {\ bullet}（\ mathcal {k}）$仍然可能是野生表示类型，并且可能不会具有简单的indecosobles。在本文中，以1参数过滤的零零同源性的老式规则的激励，我们提出了一个类似条形码的摘要，称为“老年规则”，作为一种编码$ \ mathrm {h h} _0的方式（\ \ \ \ \ Mathcal {K}）$。具体而言，如果$ n = | x | $，则旧规则阶层由$ n $数量的楼梯状块组成。我们表明，如果$ \ mathrm {h} _0（\ mathcal {k}）$是间隔可分解的，则$ \ mathrm {h} _0的条形码（\ mathcal {k}）$等于Elder-rule-ule-ule-lule----楼梯。此外，无论间隔可分解性如何，纤维条形码，尺寸函数（又称Hilbert函数）和分级的betti $ \ mathrm {h} _0（\ Mathcal {k}）$都可以有效地计算一次给出了老年规则的码。最后，我们开发并实施了一种有效的算法，以计算$ O（n^2 \ log n）$时间以$ o（n^2 \ log n）$时间计算，如果可以将其提高到$ o（n^2 \ alpha（n））$ $ x $来自固定的euclidean space $ \ mathbb {r}^d $，其中$ \ alpha（n）$是逆Ackermann函数。
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.