 Award ID(s):
 2049010
 NSFPAR ID:
 10440091
 Date Published:
 Journal Name:
 LIPIcs, Volume 258, SoCG 2023, Complete Volume
 Volume:
 258
 Page Range / eLocation ID:
 25:125:16
 Format(s):
 Medium: X
 Sponsoring Org:
 National Science Foundation
More Like this

Xavier Goaoc ; Michael Kerber (Ed.)The notion of generalized rank invariant in the context of multiparameter persistence has become an important ingredient for defining interesting homological structures such as generalized persistence diagrams. Naturally, computing these rank invariants efficiently is a prelude to computing any of these derived structures efficiently. We show that the generalized rank over a finite interval I of a đÂČindexed persistence module M is equal to the generalized rank of the zigzag module that is induced on a certain path in I tracing mostly its boundary. Hence, we can compute the generalized rank over I by computing the barcode of the zigzag module obtained by restricting the bifiltration inducing M to that path. If the bifiltration and I have at most t simplices and points respectively, this computation takes O(t^Ï) time where Ï â [2,2.373) is the exponent of matrix multiplication. Among others, we apply this result to obtain an improved algorithm for the following problem. Given a bifiltration inducing a module M, determine whether M is interval decomposable and, if so, compute all intervals supporting its summands.more » « less

Abstract The notion of generalized rank in the context of multiparameter persistence has become an important ingredient for defining interesting homological structures such as generalized persistence diagrams. However, its efficient computation has not yet been studied in the literature. We show that the generalized rank over a finite interval
I of a indexed persistence module$$\textbf{Z}^2$$ ${Z}^{2}$M is equal to the generalized rank of the zigzag module that is induced on a certain path inI tracing mostly its boundary. Hence, we can compute the generalized rank ofM overI by computing the barcode of the zigzag module obtained by restricting to that path. IfM is the homology of a bifiltrationF of simplices (while accounting for multicriticality) and$$t$$ $t$I consists of points, this computation takes$$t$$ $t$ time where$$O(t^\omega )$$ $O\left({t}^{\mathrm{\xcf\x89}}\right)$ is the exponent of matrix multiplication. We apply this result to obtain an improved algorithm for the following problem. Given a bifiltration inducing a module$$\omega \in [2,2.373)$$ $\mathrm{\xcf\x89}\xe2\x88\x88[2,2.373)$M , determine whetherM is interval decomposable and, if so, compute all intervals supporting its indecomposable summands. 
Abstract Onedimensional persistent homology is arguably the most important and heavily used computational tool in topological data analysis. Additional information can be extracted from datasets by studying multidimensional persistence modules and by utilizing cohomological ideas, e.g.Â the cohomological cup product. In this work, given a single parameter filtration, we investigate a certain 2dimensional persistence module structure associated with persistent cohomology, where one parameter is the cuplength
and the other is the filtration parameter. This new persistence structure, called the$$\ell \ge 0$$ $\mathrm{\xe2\x84\x93}\xe2\x89\u201e0$persistent cup module , is induced by the cohomological cup product and adapted to the persistence setting. Furthermore, we show that this persistence structure is stable. By fixing the cuplength parameter , we obtain a 1dimensional persistence module, called the persistent$$\ell $$ $\mathrm{\xe2\x84\x93}$ cup module, and again show it is stable in the interleaving distance sense, and study their associated generalized persistence diagrams. In addition, we consider a generalized notion of a$$\ell $$ $\mathrm{\xe2\x84\x93}$persistent invariant , which extends both therank invariant (also referred to aspersistent Betti number ), Puuskaâs rank invariant induced by epimonopreserving invariants of abelian categories, and the recentlydefinedpersistent cuplength invariant , and we establish their stability. This generalized notion of persistent invariant also enables us to lift the LyusternikSchnirelmann (LS) category of topological spaces to a novel stable persistent invariant of filtrations, called thepersistent LScategory invariant . 
Buchin, Kevin and (Ed.)Given a persistence diagram with n points, we give an algorithm that produces a sequence of n persistence diagrams converging in bottleneck distance to the input diagram, the ith of which has i distinct (weighted) points and is a 2approximation to the closest persistence diagram with that many distinct points. For each approximation, we precompute the optimal matching between the ith and the (i+1)st. Perhaps surprisingly, the entire sequence of diagrams as well as the sequence of matchings can be represented in O(n) space. The main approach is to use a variation of the greedy permutation of the persistence diagram to give good Hausdorff approximations and assign weights to these subsets. We give a new algorithm to efficiently compute this permutation, despite the high implicit dimension of points in a persistence diagram due to the effect of the diagonal. The sketches are also structured to permit fast (linear time) approximations to the Hausdorff distance between diagrams  a lower bound on the bottleneck distance. For approximating the bottleneck distance, sketches can also be used to compute a linearsize neighborhood graph directly, obviating the need for geometric data structures used in stateoftheart methods for bottleneck computation.more » « less

Abstract We study a family of invariants of compact metric spaces that combines the Curvature Sets defined by Gromov in the 1980Â s with VietorisâRips Persistent Homology. For given integers
and$$k\ge 0$$ $k\xe2\x89\u201e0$ we consider the dimension$$n\ge 1$$ $n\xe2\x89\u201e1$k VietorisâRips persistence diagrams ofall subsets of a given metric space with cardinality at mostn . We call these invariantspersistence sets and denote them as . We first point out that this family encompasses the usual VietorisâRips diagrams. We then establish that (1) for certain range of values of the parameters$${\textbf{D}}_{n,k}^{\textrm{VR}}$$ ${D}_{n,k}^{\text{VR}}$n andk , computing these invariants is significantly more efficient than computing the usual VietorisâRips persistence diagrams, (2) these invariants have very good discriminating power and, in many cases, capture information that is imperceptible through standard VietorisâRips persistence diagrams, and (3) they enjoy stability properties analogous to those of the usual VietorisâRips persistence diagrams. We precisely characterize some of them in the case of spheres and surfaces with constant curvature using a generalization of Ptolemyâs inequality. We also identify a rich family of metric graphs for which fully recovers their homotopy type by studying splitmetric decompositions. Along the way we prove some useful properties of VietorisâRips persistence diagrams using MayerâVietoris sequences. These yield a geometric algorithm for computing the VietorisâRips persistence diagram of a space$${\textbf{D}}_{4,1}^{\textrm{VR}}$$ ${D}_{4,1}^{\text{VR}}$X with cardinality with quadratic time complexity as opposed to the much higher cost incurred by the usual algebraic algorithms relying on matrix reduction.$$2k+2$$ $2k+2$