More Like this

1. Curvature Sets Over Persistence Diagrams

   https://doi.org/10.1007/s00454-024-00634-0  

   Gómez, Mario ; Mémoli, Facundo ( April 2024 , Discrete & Computational Geometry)

   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$$k\ge 0$$$k\ge 0$and$$n\ge 1$$$n\ge 1$we consider the dimensionkVietoris–Rips persistence diagrams ofallsubsets of a given metric space with cardinality at mostn. We call these invariantspersistence setsand denote them as$${\textbf{D}}_{n,k}^{\textrm{VR}}$$$D_{n,k}^{\text{VR}}$. 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 parametersnandk, 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$${\textbf{D}}_{4,1}^{\textrm{VR}}$$$D_{4,1}^{\text{VR}}$fully recovers their homotopy type by studying split-metric 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 spaceXwith cardinality$$2k+2$$$2k+2$with quadratic time complexity as opposed to the much higher cost incurred by the usual algebraic algorithms relying on matrix reduction.

    

   more » « less
2. Boundary regularity and stability for spaces with Ricci bounded below

   https://doi.org/10.1007/s00222-021-01092-8  

   Bruè, Elia ; Naber, Aaron ; Semola, Daniele ( May 2022 , Inventiones mathematicae)

   Abstract This paper studies the structure and stability of boundaries in noncollapsed $${{\,\mathrm{RCD}\,}}(K,N)$$ RCD ( K , N ) spaces, that is, metric-measure spaces $$(X,{\mathsf {d}},{\mathscr {H}}^N)$$ ( X , d , H N ) with Ricci curvature bounded below. Our main structural result is that the boundary $$\partial X$$ ∂ X is homeomorphic to a manifold away from a set of codimension 2, and is $$N-1$$ N - 1 rectifiable. Along the way, we show effective measure bounds on the boundary and its tubular neighborhoods. These results are new even for Gromov–Hausdorff limits $$(M_i^N,{\mathsf {d}}_{g_i},p_i) \rightarrow (X,{\mathsf {d}},p)$$ ( M i N , d g i , p i ) → ( X , d , p ) of smooth manifolds with boundary, and require new techniques beyond those needed to prove the analogous statements for the regular set, in particular when it comes to the manifold structure of the boundary $$\partial X$$ ∂ X . The key local result is an $$\varepsilon $$ ε -regularity theorem, which tells us that if a ball $$B_{2}(p)\subset X$$ B 2 ( p ) ⊂ X is sufficiently close to a half space $$B_{2}(0)\subset {\mathbb {R}}^N_+$$ B 2 ( 0 ) ⊂ R + N in the Gromov–Hausdorff sense, then $$B_1(p)$$ B 1 ( p ) is biHölder to an open set of $${\mathbb {R}}^N_+$$ R + N . In particular, $$\partial X$$ ∂ X is itself homeomorphic to $$B_1(0^{N-1})$$ B 1 ( 0 N - 1 ) near $$B_1(p)$$ B 1 ( p ) . Further, the boundary $$\partial X$$ ∂ X is $$N-1$$ N - 1 rectifiable and the boundary measure "Equation missing" is Ahlfors regular on $$B_1(p)$$ B 1 ( p ) with volume close to the Euclidean volume. Our second collection of results involve the stability of the boundary with respect to noncollapsed mGH convergence $$X_i\rightarrow X$$ X i → X . Specifically, we show a boundary volume convergence which tells us that the $$N-1$$ N - 1 Hausdorff measures on the boundaries converge "Equation missing" to the limit Hausdorff measure on $$\partial X$$ ∂ X . We will see that a consequence of this is that if the $$X_i$$ X i are boundary free then so is X . 

   more » « less
3. Spatiotemporal Persistent Homology for Dynamic Metric Spaces

   https://doi.org/10.1007/s00454-019-00168-w  

   Kim, Woojin ; Mémoli, Facundo ( February 2020 , Discrete & Computational Geometry)

   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 metrization of 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. In either case, the metric d can be computed in polynomial time. 

   more » « less
4. Sketching Persistence Diagrams

   https://doi.org/10.4230/LIPIcs.SoCG.2021.57  

   Sheehy, Donald R. ; Sheth, Siddharth ( July 2021 , Leibniz international proceedings in informatics)

   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 2-approximation 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 linear-size neighborhood graph directly, obviating the need for geometric data structures used in state-of-the-art methods for bottleneck computation. 

   more » « less
5. On the behavior of 1-Laplacian ratio cuts on nearly rectangular domains

   https://doi.org/10.1093/imaiai/iaaa034  

   Hamilton, Wesley ; Marzuola, Jeremy L. ; Wu, Hau-tieng ( December 2020 , Information and Inference: A Journal of the IMA)

   The $p$-Laplacian has attracted more and more attention in data analysis disciplines in the past decade. However, there is still a knowledge gap about its behavior, which limits its practical application. In this paper, we are interested in its iterative behavior in domains contained in two-dimensional Euclidean space. Given a connected set $\varOmega _0 \subset \mathbb{R}^2$, define a sequence of sets $(\varOmega _n)_{n=0}^{\infty }$ where $\varOmega _{n+1}$ is the subset of $\varOmega _n$ where the first eigenfunction of the (properly normalized) Neumann $p$-Laplacian $ -\varDelta ^{(p)} \phi = \lambda _1 |\phi |^{p-2} \phi $ is positive (or negative). For $p=1$, this is also referred to as the ratio cut of the domain. We conjecture that these sets converge to the set of rectangles with eccentricity bounded by 2 in the Gromov–Hausdorff distance as long as they have a certain distance to the boundary $\partial \varOmega _0$. We establish some aspects of this conjecture for $p=1$ where we prove that (1) the 1-Laplacian spectral cut of domains sufficiently close to rectangles is a circular arc that is closer to flat than the original domain (leading eventually to quadrilaterals) and (2) quadrilaterals close to a rectangle of aspect ratio $2$ stay close to quadrilaterals and move closer to rectangles in a suitable metric. We also discuss some numerical aspects and pose many open questions.

    

   more » « less