Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userAccelerating Iterated Persistent Homology Computations with Warm Starts
82
0
0.0
(
0
)
Added by
Yuan Luo
Publication date
2021
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
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.
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.
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.
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.
We consider generic curves in R^2, i.e. generic C^1 functions f from S^1 to R^2. We analyze these curves through the persistent homology groups of a filtration induced on S^1 by f. In particular, we consider the question whether these persistent homology groups uniquely characterize f, at least up to re-parameterizations of S^1. We give a partially positive answer to this question. More precisely, we prove that f=goh, where h:S^1-> S^1 is a C^1-diffeomorphism, if and only if the persistent homology groups of sof and sog coincide, for every s belonging to the group Sigma_2 generated by reflections in the coordinate axes. Moreover, for a smaller set of generic functions, we show that f and g are close to each other in the max-norm (up to re-parameterizations) if and only if, for every s belonging to Sigma_2, the persistent Betti numbers functions of sof and sog are close to each other, with respect to a suitable distance.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
