More Like this

1. Polytopal Complex Construction and Use in Persistent Homology

   https://doi.org/10.1109/ICDMW58026.2022.00087  

   Singh, Rohit P. ; Wilsey, Philip A. ( November 2022 , ICDM Workshop on High Dimensional Data Mining)

   Topological Data Analysis (TDA) is a data mining technique to characterize the topological features of data. Persistent Homology (PH) is an important tool of TDA that has been applied to a wide range of applications. However its time and space complexities motivates a need for new methods to compute the PH of high-dimensional data. An important, and memory intensive, element in the computation of PH is the complex constructed from the input data. In general, PH tools use and focus on optimizing simplicial complexes; less frequently cubical complexes are also studied. This paper develops a method to construct polytopal complexes (or complexes constructed of any mix of convex polytopes) in any dimension Rn . In general, polytopal complexes are significantly smaller than simplicial or cubical complexes. This paper includes an experimental assessment of the impact that polytopal complexes have on memory complexity and output results of a PH computation. 

   more » « less
2. Data Reduction and Feature Isolation for Computing Persistent Homology on High Dimensional Data

   https://doi.org/10.1109/BigData52589.2021.9671839  

   Verma, Rishi R. ; Malott, Nicholas O. ; Wilsey, Philip A. ( December 2021 , Workshop on Applications of Topological Data Analysis to "Big Data")

   Persistent Homology (PH) is computationally expensive and is thus generally employed with strict limits on the (i) maximum connectivity distance and (ii) dimensions of homology groups to compute (unless working with trivially small data sets). As a result, most studies with PH only work with H0 and H1 homology groups. This paper examines the identification and isolation of regions of data sets where high dimensional topological features are suspected to be located. These regions are analyzed with PH to characterize the high dimensional homology groups contained in that region. Since only the region around a suspected topological feature is analyzed, it is possible to identify high dimension homologies piecewise and then assemble the results into a scalable characterization of the original data set. 

   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)

   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. A Sparse Delaunay Filtration

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

   Buchin, Kevin and (Ed.)

   We show how a filtration of Delaunay complexes can be used to approximate the persistence diagram of the distance to a point set in ℝ^d. Whereas the full Delaunay complex can be used to compute this persistence diagram exactly, it may have size O(n^⌈d/2⌉). In contrast, our construction uses only O(n) simplices. The central idea is to connect Delaunay complexes on progressively denser subsamples by considering the flips in an incremental construction as simplices in d+1 dimensions. This approach leads to a very simple and straightforward proof of correctness in geometric terms, because the final filtration is dual to a (d+1)-dimensional Voronoi construction similar to the standard Delaunay filtration. We also, show how this complex can be efficiently constructed. 

   more » « less
5. Representation Homology of Topological Spaces

   https://doi.org/10.1093/imrn/rnaa023  

   Berest, Yuri ; Ramadoss, Ajay C ; Yeung, Wai-Kit ( February 2020 , International Mathematics Research Notices)

   null (Ed.)

   Abstract In this paper, we introduce and study representation homology of topological spaces, which is a natural homological extension of representation varieties of fundamental groups. We give an elementary construction of representation homology parallel to the Loday–Pirashvili construction of higher Hochschild homology; in fact, we establish a direct geometric relation between the two theories by proving that the representation homology of the suspension of a (pointed connected) space is isomorphic to its higher Hochschild homology. We also construct some natural maps and spectral sequences relating representation homology to other homology theories associated with spaces (such as Pontryagin algebras, ${{\mathbb{S}}}^1$-equivariant homology of the free loop space, and stable homology of automorphism groups of f.g. free groups). We compute representation homology explicitly (in terms of known invariants) in a number of interesting cases, including spheres, suspensions, complex projective spaces, Riemann surfaces, and some 3-dimensional manifolds, such as link complements in ${\mathbb{R}}^3$ and the lens spaces $ L(p,q) $. In the case of link complements, we identify the representation homology in terms of ordinary Hochschild homology, which gives a new algebraic invariant of links in ${\mathbb{R}}^3$. 

   more » « less