Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userSpatio-temporal Persistent Homology for Dynamic Metric Spaces
250
0
0.0
(
0
)
Added by
Woojin Kim
Publication date
2018
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
Characterizing the dynamics of time-evolving data within the framework of topological data analysis (TDA) has been attracting increasingly more attention. Popular instances of time-evolving data include flocking/swarming behaviors in animals and social networks in the human sphere. A natural mathematical model for such collective behaviors is a dynamic point cloud, or more generally a dynamic metric space (DMS). In this paper we extend the Rips filtration stability result for (static) metric spaces to the setting of DMSs. We do this by devising a certain three-parameter spatiotemporal filtration of a DMS. Applying the homology functor to this filtration gives rise to multidimensional persistence module derived from the DMS. We show that this multidimensional module enjoys stability under a suitable generalization of the Gromov-Hausdorff distance which permits metrizing the collection of all DMSs. On the other hand, it is recognized that, in general, comparing two multidimensional persistence modules leads to intractable computational problems. For the purpose of practical comparison of DMSs, we focus on both the rank invariant or the dimension function of the multidimensional persistence module that is derived from a DMS. We specifically propose to utilize a certain metric d for comparing these invariants: In our work this d is either (1) a certain generalization of the erosion distance by Patel, or (2) a specialized version of the well known interleaving distance. We also study the computational complexity associated to both choices of d.
rate research
Read More
We derive the relationship between the persistent homology barcodes of two dual filtered CW complexes. Applied to greyscale digital images, we obtain an algorithm to convert barcodes between the two different (dual) topological models of pixel connectivity.
In many applications concerning the comparison of data expressed by $mathbb{R}^m$-valued functions defined on a topological space $X$, the invariance with respect to a given group $G$ of self-homeomorphisms of $X$ is required. While persistent homology is quite efficient in the topological and qualitative comparison of this kind of data when the invariance group $G$ is the group $mathrm{Homeo}(X)$ of all self-homeomorphisms of $X$, this theory is not tailored to manage the case in which $G$ is a proper subgroup of $mathrm{Homeo}(X)$, and its invariance appears too general for several tasks. This paper proposes a way to adapt persistent homology in order to get invariance just with respect to a given group of self-homeomorphisms of $X$. The main idea consists in a dual approach, based on considering the set of all $G$-invariant non-expanding operators defined on the space of the admissible filtering functions on $X$. Some theoretical results concerning this approach are proven and two experiments are presented. An experiment illustrates the application of the proposed technique to compare 1D-signals, when the invariance is expressed by the group of affinities, the group of orientation-preserving affinities, the group of isometries, the group of translations and the identity group. Another experiment shows how our technique can be used for image comparison.
Persistent homology is a topological feature used in a variety of applications such as generating features for data analysis and penalizing optimization problems. We develop an approach to accelerate persistent homology computations performed on many similar filtered topological spaces which is based on updating associated matrix factorizations. Our approach improves the update scheme of Cohen-Steiner, Edelsbrunner, and Morozov for permutations by additionally handling addition and deletion of cells in a filtered topological space and by processing changes in a single batch. We show that the complexity of our scheme scales with the number of elementary changes to the filtration which as a result is often less expensive than the full persistent homology computation. Finally, we perform computational experiments demonstrating practical speedups in several situations including feature generation and optimization guided by persistent homology.
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 $xin 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^2log n)$ time, which can be improved to $O(n^2alpha(n))$ if $X$ is from a fixed dimensional Euclidean space $mathbb{R}^d$, where $alpha(n)$ is the inverse Ackermann function.
The present lack of a stable method to compare persistent homology groups with torsion is a relevant problem in current research about Persistent Homology and its applications in Pattern Recognition. In this paper we introduce a pseudo-distance d_T that represents a possible solution to this problem. Indeed, d_T is a pseudo-distance between multidimensional persistent homology groups with coefficients in an Abelian group, hence possibly having torsion. Our main theorem proves the stability of the new pseudo-distance with respect to the change of the filtering function, expressed both with respect to the max-norm and to the natural pseudo-distance between topological spaces endowed with vector-valued filtering functions. Furthermore, we prove a result showing the relationship between d_T and the matching distance in the 1-dimensional case, when the homology coefficients are taken in a field and hence the comparison can be made.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
