Minimal Cycle Representatives in Persistent Homology using Linear Programming: an Empirical Study with User's Guide
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 $\ell_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: (i) optimization is effective in reducing the size of cycle representatives, (ii) the computational cost of optimizing a basis of cycle representatives exceeds the cost of computing such a basis in most data sets we consider, (iii) the choice of linear solvers matters a lot to the computation time of optimizing cycles, (iv) 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, (v) 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 $\ell_0$ optimization problem, and (vi) we obtain qualitatively different results for generators in Erd\H{o}s-R\'enyi random clique complexes.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Memory as Structured Trajectories: Persistent Homology and Contextual Sheaves
We propose a topological framework for memory and inference grounded in the structure of spike-timing dynamics, persistent homology, and the Context-Content Uncertainty Principle (CCUP). Starting from the observation tha…
Geometric Localization of Homology Cycles
Computing an optimal cycle in a given homology class, also referred to as the homology localization problem, is known to be an NP-hard problem in general. Furthermore, there is currently no known optimality criterion tha…
Topology Structure Optimization of Reservoirs Using GLMY Homology
Reservoir is an efficient network for time series processing. It is well known that network structure is one of the determinants of its performance. However, the topology structure of reservoirs, as well as their perform…
Cycle Registration in Persistent Homology with Applications in Topological Bootstrap
In this article we propose a novel approach for comparing the persistent homology representations of two spaces (filtrations). Commonly used methods are based on numerical summaries such as persistence diagrams and persi…
Tight basis cycle representatives for persistent homology of large data sets
Persistent homology (PH) is a popular tool for topological data analysis that has found applications across diverse areas of research. It provides a rigorous method to compute robust topological features in discrete expe…
Topological Data Analysis