34 research outputs found
On the notion of weak isometry for finite metric spaces
No full textFinite metric spaces are the object of study in many data analysis problems. We examine the concept of weak isometry between finite metric spaces, in order to analyse properties of the spaces that are invariant under strictly increasing rescaling of the distance functions. In this paper, we analyse some of the possible complete and incomplete invariants for weak isometry and we introduce a dissimilarity measure that asses how far two spaces are from being weakly isometric. Furthermore, we compare these ideas with the theory of persistent homology, to study how the two are related
Betti splitting from a topological point of view
No full textA Betti splitting I=J+K of a monomial ideal I ensures the recovery of the graded Betti numbers of I starting from those of J,K and J∩K. In this paper, we introduce an analogous notion for simplicial complexes, using Alexander duality, proving that it is equivalent to a recursive splitting condition on links of some vertices. We provide results ensuring the existence of a Betti splitting for a simplicial complex Δ, relating it to topological properties of Δ. Among other things, we prove that orientability for a manifold without boundary is equivalent to the admission of a Betti splitting induced by the removal of a single facet. Taking advantage of our topological approach, we provide the first example of a monomial ideal which admits Betti splittings in all characteristics but with characteristic-dependent resolution. Moreover, we introduce new numerical descriptors for simplicial complexes and topological spaces, useful to deal with questions concerning the existence of Betti splitting
Chunk Reduction for Multi-Parameter Persistent Homology
No full textThe extension of persistent homology to multi-parameter setups is an algorithmic challenge. Since most computation tasks scale badly with the size of the input complex, an important pre-processing step consists of simplifying the input while maintaining the homological information. We present an algorithm that drastically reduces the size of an input. Our approach is an extension of the chunk algorithm for persistent homology (Bauer et al., Topological Methods in Data Analysis and Visualization III, 2014). We show that our construction produces the smallest multi-filtered chain complex among all the complexes quasi-isomorphic to the input, improving on the guarantees of previous work in the context of discrete Morse theory. Our algorithm also offers an immediate parallelization scheme in shared memory. Already its sequential version compares favorably with existing simplification schemes, as we show by experimental evaluation
Critical sets of PL and discrete Morse theory: a correspondence
No full textPiecewise-linear (PL) Morse theory and discrete Morse theory are used in shape analysis tasks to investigate the topological features of discretized spaces. In spite of their common origin in smooth Morse theory, various notions of critical points have been given in the literature for the discrete setting, making a clear understanding of the relationships occurring between them not obvious. This paper aims at providing equivalence results about critical points of the two discretized Morse theories. First of all, we prove the equivalence of the existing notions of PL critical points. Next, under an optimality condition called relative perfectness, we show a dimension agnostic correspondence between the set of PL critical points and that of discrete critical simplices ofthe combinatorial approach. Finally, we show how a relatively perfect discrete gradient vector field can be algorithmically built up to dimension 3. This way, we guarantee a formal and operative connection between critical sets in the PL and discrete theories
Eurographics Workshop on 3D Object Retrieval - Short Papers: Frontmatter
No full textEurographics Workshop on 3D Object Retrieva
Topological modifications and hierarchical representation of cell complexes in arbitrary dimensions
No full textA kernel for multi-parameter persistent homology
No full textTopological data analysis and its main method, persistent homology, provide a toolkit for computing topological information of high-dimensional and noisy data sets. Kernels for one-parameter persistent homology have been established to connect persistent homology with machine learning techniques with applicability on shape analysis, recognition, and classification. We contribute a kernel construction for multi-parameter persistence by integrating a one-parameter kernel weighted along straight lines. We prove that our kernel is stable and efficiently computable, which establishes a theoretical connection between topological data analysis and machine learning for multivariate data analysis
Morse complexes for shape segmentation and homological analysis: discrete models and algorithms
No full textMorse theory offers a natural and mathematically-sound tool for shape analysis and understanding. It allows
studying the behavior of a scalar function defined on a manifold. Starting from a Morse function, we can decompose the domain of the function into meaningful regions associated with the critical points of the function. Such
decompositions, called Morse complexes, provide a segmentation of a shape and are extensively used in terrain
modeling and in scientific visualization. Discrete Morse theory, a combinatorial counterpart of smooth Morse
theory defined over cell complexes, provides an excellent basis for computing Morse complexes in a robust and
efficient way. Moreover, since a discrete Morse complex computed over a given complex has the same homology
as the original one, but fewer cells, discrete Morse theory is a fundamental tool for efficiently detecting holes
in shapes through homology and persistent homology. In this survey, we review, classify and analyze algorithms
for computing and simplifying Morse complexes in the context of such applications with an emphasis on discrete
Morse theory and on algorithms based on i
Homological scaffold via minimal homology bases
No full textThe homological scaffold leverages persistent homology to construct a topologically sound summary of a weighted network. However, its crucial dependency on the choice of representative cycles hinders the ability to trace back global features onto individual network components, unless one provides a principled way to make such a choice. In this paper, we apply recent advances in the computation of minimal homology bases to introduce a quasi-canonical version of the scaffold, called minimal, and employ it to analyze data both real and in silico. At the same time, we verify that, statistically, the standard scaffold is a good proxy of the minimal one for sufficiently complex networks
