More Like this

1. Metric Thickenings and Group Actions

   https://doi.org/10.1142/S1793525320500569  

   Adams, Henry; Heim, Mark; Peterson, Chris (January 2021, Journal of Topology and Analysis)

   null (Ed.)

   Let [Formula: see text] be a group acting properly and by isometries on a metric space [Formula: see text]; it follows that the quotient or orbit space [Formula: see text] is also a metric space. We study the Vietoris–Rips and Čech complexes of [Formula: see text]. Whereas (co)homology theories for metric spaces let the scale parameter of a Vietoris–Rips or Čech complex go to zero, and whereas geometric group theory requires the scale parameter to be sufficiently large, we instead consider intermediate scale parameters (neither tending to zero nor to infinity). As a particular case, we study the Vietoris–Rips and Čech thickenings of projective spaces at the first scale parameter where the homotopy type changes. 

   more » « less
2. On the Reconstruction of Geodesic Subspaces of ℝ^N

   https://doi.org/10.1142/S0218195922500066  

   Fasy, Brittany Terese; Komendarczyk, Rafal; Majhi, Sushovan; Wenk, Carola (January 2022, International Journal of Computational Geometry & Applications)

   We consider the topological and geometric reconstruction of a geodesic subspace of [Formula: see text] both from the Čech and Vietoris-Rips filtrations on a finite, Hausdorff-close, Euclidean sample. Our reconstruction technique leverages the intrinsic length metric induced by the geodesics on the subspace. We consider the distortion and convexity radius as our sampling parameters for the reconstruction problem. For a geodesic subspace with finite distortion and positive convexity radius, we guarantee a correct computation of its homotopy and homology groups from the sample. This technique provides alternative sampling conditions to the existing and commonly used conditions based on weak feature size and [Formula: see text]–reach, and performs better under certain types of perturbations of the geodesic subspace. For geodesic subspaces of [Formula: see text], we also devise an algorithm to output a homotopy equivalent geometric complex that has a very small Hausdorff distance to the unknown underlying space. 

   more » « less
3. 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)

   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$$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
4. Bootstrapping Persistent Betti Numbers and Other Stabilizing Statistics

   Roycraft, Benjamin; Krebs, Johannes; Polonik, Wolfgang (August 2023, The Annals of Statistics)

   We investigate multivariate bootstrap procedures for general stabilizing statistics, with specific application to topological data analysis. The work relates to other general results in the area of stabilizing statistics, including central limit theorems for geometric and topological functionals of Poisson and binomial processes in the critical regime, where limit theorems prove difficult to use in practice, motivating the use of a bootstrap approach. A smoothed bootstrap procedure is shown to give consistent estimation in these settings. Specific statistics considered include the persistent Betti numbers of Čech and Vietoris–Rips complexes over point sets in Rd, along with Euler characteristics, and the total edge length of the k-nearest neighbor graph. Special emphasis is given to weakening the necessary conditions needed to establish bootstrap consistency. In particular, the assumption of a continuous underlying density is not required. Numerical studies illustrate the performance of the proposed method. 

   more » « less
5. GPU-Accelerated Computation of Vietoris-Rips Persistence Barcodes

   Simon Zhang, Mengbai Xiao (January 2020, Proceedings of Symposium of Computational Geometry (SoCG 2020))

   The computation of Vietoris-Rips persistence barcodes is both execution-intensive and memory-intensive. In this paper, we study the computational structure of Vietoris-Rips persistence barcodes, and identify several unique mathematical properties and algorithmic opportunities with connections to the GPU. Mathematically and empirically, we look into the properties of apparent pairs, which are independently identifiable persistence pairs comprising up to 99% of persistence pairs. We give theoretical upper and lower bounds of the apparent pair rate and model the average case. We also design massively parallel algorithms to take advantage of the very large number of simplices that can be processed independently of each other. Having identified these opportunities, we develop a GPU-accelerated software for computing Vietoris-Rips persistence barcodes, called Ripser++. The software achieves up to 30x speedup over the total execution time of the original Ripser and also reduces CPU-memory usage by up to 2.0x. We believe our GPU-acceleration based efforts open a new chapter for the advancement of topological data analysis in the post-Moore's Law era. 

   more » « less