More Like this

1. Algorithmic reconstruction of the fiber of persistent homology on cell complexes

   https://doi.org/10.1007/s41468-024-00165-w  

   Leygonie, Jacob ; Henselman-Petrusek, Gregory ( April 2024 , Journal of Applied and Computational Topology)

   Let Kbe a finite simplicial, cubical, delta or CW complex. The persistence map $$\textrm{PH}$$$\text{PH}$takes a filter $$f:K\rightarrow \mathbb {R}$$$f:K\to R$as input and returns the barcodes of the sublevel set persistent homology of fin each dimension. We address the inverse problem: given target barcodes D, computing the fiber $$\textrm{PH}^{-1}(D)$$${\text{PH}}^{-1}\left(D\right)$. For this, we use the fact that $$\textrm{PH}^{-1}(D)$$${\text{PH}}^{-1}\left(D\right)$decomposes as a polyhedral complex when Kis a simplicial complex, and we generalise this result to arbitrary based chain complexes. We then design and implement a depth-first search that recovers the polytopes forming the fiber $$\textrm{PH}^{-1}(D)$$${\text{PH}}^{-1}\left(D\right)$. As an application, we solve a corpus of 120 sample problems, providing a first insight into the statistical structure of these fibers, for general CW complexes.

    

   more » « less
2. Temporal network analysis using zigzag persistence

   https://doi.org/10.1140/epjds/s13688-023-00379-5  

   Myers, Audun ; Muñoz, David ; Khasawneh, Firas A ; Munch, Elizabeth ( December 2023 , EPJ Data Science)

   This work presents a framework for studying temporal networks using zigzag persistence, a tool from the field of Topological Data Analysis (TDA). The resulting approach is general and applicable to a wide variety of time-varying graphs. For example, these graphs may correspond to a system modeled as a network with edges whose weights are functions of time, or they may represent a time series of a complex dynamical system. We use simplicial complexes to represent snapshots of the temporal networks that can then be analyzed using zigzag persistence. We show two applications of our method to dynamic networks: an analysis of commuting trends on multiple temporal scales, e.g., daily and weekly, in the Great Britain transportation network, and the detection of periodic/chaotic transitions due to intermittency in dynamical systems represented by temporal ordinal partition networks. Our findings show that the resulting zero- and one-dimensional zigzag persistence diagrams can detect changes in the networks’ shapes that are missed by traditional connectivity and centrality graph statistics. 

   more » « less
3. Learning Simplicial Complexes from Persistence Diagrams

   Belton, Robin Lynne ; Fasy, Brittany Terese ; Mertz, Rostik ; Micka, Samuel ; Millman, David L. ; Salinas, Daniel ; Schenfisch, Anna ; Schupbach, Jordan ; Williams, Lucia ( August 2018 , Canadian Conference on Computational Geometry)

   Topological Data Analysis (TDA) studies the “shape” of data. A common topological descriptor is the persistence diagram, which encodes topological features in a topological space at different scales. Turner, Mukherjee, and Boyer showed that one can reconstruct a simplicial complex embedded in R^3 using persistence diagrams generated from all possible height filtrations (an uncountably infinite number of directions). In this paper, we present an algorithm for reconstructing plane graphs K = (V, E) in R^2, i.e., a planar graph with vertices in general position and a straight-line embedding, from a quadratic number height filtrations and their respective persistence diagrams. 

   more » « less
4. Learning Simplicial Complexes from Persistence Diagrams

   Robin Lynne Belton, Brittany Terese ( July 2018 , CCCG '18: Thirtieth Canadian Conference on Computational Geometry)

   Topological Data Analysis (TDA) studies the shape of data. A common topological descriptor is the persistence diagram, which encodes topological features in a topological space at different scales. Turner, Mukeherjee, and Boyer showed that one can reconstruct a simplicial complex embedded in R^3 using persistence diagrams generated from all possible height filtrations (an uncountably infinite number of directions). In this paper, we present an algorithm for reconstructing plane graphs K=(V,E) in R^2 , i.e., a planar graph with vertices in general position and a straight-line embedding, from a quadratic number height filtrations and their respective persistence diagrams. 

   more » « less
5. Minimal Cycle Representatives in Persistent Homology Using Linear Programming: An Empirical Study With User’s Guide

   https://doi.org/10.3389/frai.2021.681117  

   Li, Lu ; Thompson, Connor ; Henselman-Petrusek, Gregory ; Giusti, Chad ; Ziegelmeier, Lori ( October 2021 , Frontiers in Artificial Intelligence)

   Cycle representatives of persistent homology classes can be used to provide descriptions of topological features in data. However, the non-uniqueness of these representatives creates ambiguity and can lead to many different interpretations of the same set of classes. One approach to solving this problem is to optimize the choice of representative against some measure that is meaningful in the context of the data. In this work, we provide a study of the effectiveness and computational cost of several ℓ 1 minimization optimization procedures for constructing homological cycle bases for persistent homology with rational coefficients in dimension one, including uniform-weighted and length-weighted edge-loss algorithms as well as uniform-weighted and area-weighted triangle-loss algorithms. We conduct these optimizations via standard linear programming methods, applying general-purpose solvers to optimize over column bases of simplicial boundary matrices. Our key findings are: 1) optimization is effective in reducing the size of cycle representatives, though the extent of the reduction varies according to the dimension and distribution of the underlying data, 2) the computational cost of optimizing a basis of cycle representatives exceeds the cost of computing such a basis, in most data sets we consider, 3) the choice of linear solvers matters a lot to the computation time of optimizing cycles, 4) the computation time of solving an integer program is not significantly longer than the computation time of solving a linear program for most of the cycle representatives, using the Gurobi linear solver, 5) strikingly, whether requiring integer solutions or not, we almost always obtain a solution with the same cost and almost all solutions found have entries in { ‐ 1,0,1 } and therefore, are also solutions to a restricted ℓ 0 optimization problem, and 6) we obtain qualitatively different results for generators in Erdős-Rényi random clique complexes than in real-world and synthetic point cloud data. 

   more » « less