# Minimal Cycle Representatives in Persistent Homology using Linear Programming: an Empirical Study with User's Guide

arXiv: https://arxiv.org/abs/2105.07025 · HTML: https://mlsanity.com/paper/2105.07025/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 65 references that are in the map.
- First posted on arXiv 14 May 2021.

## Builds on (most cited first, 9 of 9)

- [A roadmap for the computation of persistent homology](https://mlsanity.com/paper/1506.08903/) (2015)
- [Two's company, three (or more) is a simplex: Algebraic-topological tools for understanding higher-order structure in neural data](https://mlsanity.com/paper/1601.01704/) (2016)
- [Topology-Aware Surface Reconstruction for Point Clouds](https://mlsanity.com/paper/1811.12543/) (2018)
- [Using persistent homology and dynamical distances to analyze protein binding](https://mlsanity.com/paper/1412.1394/) (2014)
- [Volume Optimal Cycle: Tightest representative cycle of a generator on persistent homology](https://mlsanity.com/paper/1712.05103/) (2017)
- [The importance of the whole: topological data analysis for the network neuroscientist](https://mlsanity.com/paper/1806.05167/) (2018)
- [Persistent 1-Cycles: Definition, Computation, and Its Application](https://mlsanity.com/paper/1810.04807/) (2018)
- [Efficient algorithms for computing a minimal homology basis](https://mlsanity.com/paper/1801.06759/) (2018)
- [Minimum bounded chains and minimum homologous chains in embedded simplicial complexes](https://mlsanity.com/paper/2003.02801/) (2020)

## Built on by (most cited first, 6 of 6)

- [Tight basis cycle representatives for persistent homology of large data sets](https://mlsanity.com/paper/2206.02925/) (2022)
- [Visualizing Topological Importance: A Class-Driven Approach](https://mlsanity.com/paper/2309.13185/) (2023)
- [Train-Free Segmentation in MRI with Cubical Persistent Homology](https://mlsanity.com/paper/2401.01160/) (2024)
- [A Pipeline for Data-Driven Learning of Topological Features with Applications to Protein Stability Prediction](https://mlsanity.com/paper/2408.04847/) (2024)
- [MCbiF: Measuring Topological Autocorrelation in Multiscale Clusterings via 2-Parameter Persistent Homology](https://mlsanity.com/paper/2510.14710/) (2025)
- [Geometric Localization of Homology Cycles](https://mlsanity.com/paper/2406.03183/) (2024)

## Abstract (arXiv)

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: (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 ℓ0 optimization problem, and (vi) we obtain qualitatively different results for generators in ErdHos-R'enyi random clique complexes.