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

1 Introduction

• Cycle representatives are not unique, so choosing among them can affect how a detected hole’s location and shape are described.The desired measure may depend on the application, such as minimizing length or bounding area or volume.Source: §1 · p. 2
• The study asks how optimization costs vary across techniques and solvers, what statistical properties optimized representatives have, and how much the choice of technique matters.Questions include whether supports form single loops, whether weighted and uniform solutions have matching lengths, and whether ℓ1 representatives are also ℓ0 optimal.Source: §1 · p. 3
• The paper frames empirical trends as useful to practitioners because theoretical complexity may not predict computation time in practice.The authors cite persistence computation as an example where a known matrix-multiplication complexity contrasts with almost-always linear practical runtime.Source: §1 · p. 3
• The authors conduct an empirical exploration of linear and mixed-integer programming for one-dimensional persistent homology over rational coefficients.They also present a treatment of parameter dependence on simplex-wise refinements, relevant to common cases such as Vietoris–Rips complexes of point clouds.Source: §1 · p. 3

2 Background: Topological Data Analysis and Persistent Homology

• A simplicial complex models data as vertices and simplices, and the Vietoris–Rips construction includes a simplex when its vertices are pairwise within the chosen distance threshold.The paper focuses on rational coefficients, while noting rational, integer, and F2 coefficient settings.Source: §2 · p. 4
• An n-chain assigns coefficients to n-simplices, and the boundary map sends chains to combinations of lower-dimensional simplices.Cycles have zero boundary; boundaries are images of the next-dimensional boundary map, and every boundary is a cycle.Source: §2 · pp. 4–5
• Homology classes group cycles that differ by a boundary, so homologous cycles represent the same class while non-homologous cycles represent different classes.A homological cycle basis contains cycles representing distinct classes whose classes form a basis for homology.Source: §2 · pp. 5–6, Figure 2 · p. 6
• A filtration is a nested sequence of complexes, and a simplex-wise refinement orders simplices so that each filtration stage is an initial segment of that order.The Vietoris–Rips filtration is given as an example arising from increasing distance thresholds.Source: §2 · p. 7
• A cycle’s lifespan runs from its birth, when it first represents a homology class, until its death, when it represents the zero class.A persistent homological cycle basis gives a homological cycle basis at every filtration stage, and its lifespan intervals form an invariant barcode.Source: §2 · pp. 7–8
• Persistent homology cycle representatives and barcodes may be computed through the R = DV decomposition of boundary matrices.The barcode records feature lifespans, while the number of active basis cycles at a filtration stage equals the corresponding Betti number.Source: §2 · pp. 8–9

3 Related work on minimizing cycle representatives

• Prior work applies minimal cycles to materials, cardiac-image segmentation, and chromatin-loop localization, and provides specialized software for edge-loss and triangle-loss optimization.Other approaches include shortest persistent 1-cycles, approximate shortest bases, and meaningful alternatives to optimal persistent cycles; some have worst-case exponential complexity.Source: §3 · pp. 9–10, §3.7 · p. 16
• Linear-programming approaches include minimizing the number of edges within a homology class, optimizing a homology basis, and minimizing the number of bounding triangles.The cited methods are Dey et al. [18], Escolar and Hiraoka, and Obayashi, respectively.Source: §3 · p. 9

3.1 Background: Linear Programming

• Linear programs optimize linear objectives subject to linear constraints, while mixed integer programs add integrality restrictions and are more challenging to solve; this study uses both formulations.Source: §3.1 · pp. 10–11

3.2 Minimal cycle representatives of a homology class

• For one homology class, linear programming can minimize a geometric loss over homologous representatives; persistent-cycle methods have also been studied under specific assumptions.The cited persistent-cycle treatment assumes coefficients in F2, weighted incident-edge loss, distinct birth values within each simplex dimension, and dimension one.Source: §3.2 · p. 11

3.3 Minimal homological cycle bases

• Minimizing each member of an arbitrary homological cycle basis separately need not yield an optimal basis, and a persistent basis additionally must preserve the barcode’s birth-death pairs.For F2 with ℓ0 loss, the general problem is NP-hard to approximate for dimensions n > 1, while the cited result gives O(n^3) for n = 1.Source: §3.3 · p. 12

3.4 Minimal filtered cycle space bases

• Filtered-basis optimization minimizes each cycle when it first appears, but its cycles need not retain their original death times or form a persistent homological cycle basis.The method may combine a new cycle with earlier boundaries and cycles; the paper illustrates that optimizing a filtered basis can change a cycle’s lifespan.Source: §3.4 · p. 13, Figure 4 · p. 14

3.5 Volume-optimal cycles: minimizing over bounding chains

• For a finite barcode interval, a persistent volume’s boundary has that interval’s lifespan, and replacing the corresponding basis cycle with that boundary preserves a persistent homological cycle basis.Thus, boundaries of persistent volumes can construct such a basis for barcodes composed of finite intervals.Source: §3.5 · p. 15

3.6 ℓ0 versus ℓ1-optimization

• ℓ1 optimization is polynomial-time solvable and promotes sparsity, whereas ℓ0 optimization is NP-hard; LP and MIP optima are guaranteed to coincide only under conditions such as total unimodularity.The paper notes that total unimodularity is not guaranteed for all boundary matrices.Source: §3.6 · p. 16

3.7 Software implementations

• ℓ2 is especially sensitive to outliers, ℓ1 encourages sparsity, and the implementation is available in HomCloud’s optvol.py file.The passage says other loss choices may suit particular applications better or worse than ℓ0 and ℓ1.Source: §3.7 · pp. 16–17

4.1 Structural parameters

• Eight optimization problems combine edge-loss or triangle-loss objectives with integral or rational coefficients and uniform or size-based weights.The size-based weights use edge lengths for edge-loss and triangle areas for triangle-loss.Source: §4 · p. 17, §4.1 · pp. 17–18

4 Programs and solution methods

• Neither edge-loss nor triangle-loss methods is guaranteed to solve the minimal persistent homology cycle basis problem.Triangle-loss results depend on an arbitrary total simplex order, while edge-loss results depend on the initial persistent homology cycle basis.Source: §4 · p. 17

4.2 Edge-loss methods

• The edge-loss pipeline modifies prior methods to remove the simplex-wise filtration constraint and preserve a persistent homology cycle basis with each representative’s lifespan unchanged.Optimizations run after persistence computation, allowing the persistence and linear solvers to be selected independently.Source: §4.2 · p. 18

4.4 Acceleration techniques

• For edge-loss programs, replacing a large set of boundary-matrix variables with a column basis can substantially reduce decision variables without changing feasible solutions.The boundary matrix may have hundreds or thousands of times as many columns as rows.Source: §4.2 · p. 19

4.3 Triangle-loss methods

• Triangle-loss optimization adapts a simplex-wise method to general filtration data by using a simplex-wise refinement, but its outputs depend on the chosen linear orders.The refinement and preprocessing make the method applicable when the original filtration is not simplex-wise.Source: §4.3 · pp. 20–21

4.4 Acceleration techniques

• The first acceleration strategy is generally faster for optimizing an entire basis, while storing the full boundary matrix may be infeasible for large data sets.The two approaches trade computation time against memory.Source: §4.4 · p. 22
• For triangle-loss programs, constructing each constraint matrix from scratch is generally faster across a basis, while precomputing the full boundary matrix trades speed for memory.The full matrix may be too large to store for large data sets.Source: §4.4 · pp. 21–22

5 Experiments

• The experimental suite studies dimension-one cycle representatives on real-world datasets and point samples from four probability distributions with varying dimensions.The optimization problems are defined in Section 4.Source: §5 · p. 22

5.1 Real-world data sets

• The study includes 11 real-world datasets from a widely used persistent-homology benchmark collection, with Table 1 reporting dataset dimensions, point counts, H1 cycle counts, and computation times.Examples include neuronal and collaboration networks and point samples from the Klein bottle.Source: §5.1 · pp. 22–23

5.2 Randomly generated point clouds

• The synthetic geometric corpus contains 360 point clouds, each with 100 points in dimensions 2–10, sampled from four distributions and analyzed using Euclidean distance and Vietoris–Rips complexes.The four distributions are normal, exponential, gamma, and logistic, with 10 realizations per distribution and dimension combination.Source: §5.2 · p. 23

5.3 Erdős-Rényi random complexes

• The non-geometric experiments use 100 Erdős–Rényi random clique complexes built from independent uniform dissimilarities that need not satisfy the triangle inequality.A filtration on each dissimilarity matrix is used to compute persistent homology.Source: §5.3 · p. 23

5.4 Computations

• For each dataset, the authors optimize cycle bases with Algorithms 3 and 4 and compare edge-loss optimization against applying Program (8) to each persistent-homology cycle representative.Table 1 also reports optimization times for six problems and compares two ways to construct triangle-loss inputs; memory constraints prevented computing all triangle-loss representatives for Genome and H3N2.Source: §5.4 · p. 23, Table 1 · p. 24

5.5 Hardware and software

• The Julia test library exposes intermediate pipeline objects, adapts Eirene for rational-coefficient persistence computations, and formats optimization programs for linear solvers.The library is designed for inspecting linear programs and omits performance-enhancing techniques discussed elsewhere in the paper.Source: §5.5 · p. 25
• Gurobi and GLPK can solve both linear and mixed-integer programs, but the authors report that Gurobi is much faster on these problems and use it for most computations.Both solvers are free for academic users.Source: §5.5 · p. 25

6.1 Computation time comparisons

• Optimization took longer than persistence on all synthetic datasets and on 5 of 11 real-world datasets with edge-loss methods and 9 of 11 with uniform triangle-loss methods.The authors conclude that optimizing a basis generally exceeds the cost of computing it.Source: §6.1 · p. 27
• Integer programs took longer than non-integer programs but remained on the same order of magnitude; edge-loss cycles were more efficient to compute than triangle-loss cycles.For more than 50% of cycle representatives, the integer-to-linear-program time ratio centered around 1.Source: §6.1 · pp. 27–28, Figure 6 · p. 28
• GLPK’s median runtime was 2.22 times Gurobi’s for EdgeNI Unif, 1.68 for EdgeI Unif, 2.28 for EdgeNI Len, and 1.73 for EdgeI Len.For some cycles, GLPK took up to 30 times as long, so the authors used Gurobi in subsequent analyses.Source: §6.1 · p. 29

6.2 Performance of acceleration techniques

• Reducing the edge-loss input boundary matrix by using basis columns and deleting rows for edges born after the cycle’s birth made optimization faster, with the smallest input most efficient.The comparison used the Senate and House datasets.Source: §6.2 · p. 29, Table 3 · p. 30
• For triangle-loss inputs, deleting rows and columns was the most efficient of the three tested approaches, consistent with reducing the number of variables speeding optimization.The approaches were zeroing columns, deleting columns, and deleting both columns and rows.Source: §6.2 · p. 29, Table 3 · p. 30
• Building the full boundary matrix and then deleting columns was generally faster, but rebuilding only the needed part enabled optimization of 115 of 117 Genome and 52 of 57 H3N2 representatives.The full matrices were too large to construct for those datasets; they contained 453,424,290 and 3,357,641,440 triangles, respectively.Source: §6.2 · pp. 29–30

6.3 Coefficients of optimal cycle representatives in data sets from Section 5.1 and Section 5.2

• More than 99.97% of EdgeLen solutions and 100% of EdgeUnif and TriUnif solutions had the same optimum cost with or without an integer constraint.All Program (8) solutions and all but one Algorithm 3 solution had coefficients in {-1, 0, 1}; one triangle-loss solution had a coefficient of 2, and bounding coefficients by one made that case infeasible.Source: §6.3 · p. 31

6.4 Comparing optimal cycle representatives against different loss functions

• Some edge-loss and uniform-weighted triangle-loss cycles had strictly smaller surveyor’s area than the persistent-cycle denominator, and ℓ1-optimal cycles could differ from ℓ0-based comparisons.For example, an edge-loss cycle could have lower edge count than an ℓ1-optimal uniform cycle because the latter was not optimized for edge count.Source: §6.4 · p. 32, Figure 7 · p. 32
• 63.28% of PrsHCB LE-Unif-minimal cycles are also LE-Len-minimal, while 99.66% of LE-Len-minimal cycles are also LE-Unif-minimal; triangle-loss cycles can differ substantially.For FCB cycles, the corresponding overlap rates are 61.31% and 99.32%.Source: §6.4 · pp. 33–34
• Area-weighted triangle-loss cycles need not enclose the smallest actual area because the objective sums bounded triangle areas and requires the cycle to contain the simplex born at death.The length-weighted edge-loss cycle lacks that simplex constraint and can enclose less area.Source: §6.4 · p. 35

6.5 Comparative performance and precision of LP solvers

• 9.74% of GLPK length-weighted and 8.32% of GLPK uniform-weighted FCB cycles had non-integral entries, versus 0.12% and 0.04% with Gurobi, respectively.GLPK also ran much slower in the initial experiments; fractional uniform-weighted solutions could remain ℓ1-optimal but cease to be ℓ0-optimal.Source: §6.5 · p. 36

6.6 Statistical properties of optimal cycle representatives with regard to various other quantities of interest

• 91.93% of optimized Erdős–Rényi representatives have one loop, 5.81% have two, and 2.14% have more than two, with a maximum of 15 loops.Edge-loss optimized cycles in the other analyzed data have one loop; 0.13% of triangle-loss cycles have two.Source: §6.6 · p. 36
• 83.17% and 90.35% are the average ratios of optimized to original LE-Unif loss for Program (14) cycles from Sections 5.1 and 5.2, respectively.The corresponding LE-Len ratios are 87.02% and 90.41%; optimization generally reduces representative size, especially for larger originals.Source: §6.6 · pp. 36, 38, Figure 12 · p. 39
• For distribution data, as dimension increases there tend to be more cycle representatives, including more with more edges, and representatives tend to be larger in ℓ0 norm.Source: §6.6 · p. 38, Figure 13 · p. 40

6.7 Optimal cycle representatives for Erdős–Rényi random clique complexes

• Among 34,214 Erdős–Rényi representatives, 3.89% of length-weighted edge-loss, 4.49% of uniform-weighted edge-loss, and 3.52% of uniform-weighted triangle-loss outputs had entries outside {−1, 0, 1}.The authors suggest some such cycles may reflect non-orientable projective planes; non-integral original representatives also prevented integral solutions for 0.27% of edge-loss and 0.11% of triangle-loss outputs.Source: §6.7 · p. 41

7 Conclusion

• The study evaluates total length, number of edges, internal volume, and area-weighted internal volume, and reports consistent trends across samples.Its empirical investigation focuses on H1 cycle representatives.Source: §7 · pp. 41–42
• The authors released a rational-coefficient persistent-homology library and formulated recommendations on solver-input procedures that affect overall computation cost.The library builds on Eirene, uses GLPK and Gurobi, and includes acceleration techniques.Source: §7 · pp. 41–42
• Uniform- and length-weighted edge-loss cycles were computed for all data sets, while triangle-loss optimization failed for six representatives with more than 20 million triangles.Edge-loss cycles were faster for longer-persistence representatives, while triangle-loss cycles could be less costly for shorter-persistence representatives.Source: §7 · p. 42
• Optimal representatives often improve the initial cycle’s loss by a factor of 0.3 to 1.0, while area-weighted triangle-loss cycles can enclose greater area than length- or uniform-weighted cycles.The study also reports that area-weighted triangle-loss cycles can differ geometrically from cycles optimized for edge loss.Source: §7 · p. 42
• Length-weighted edge-loss optimal cycles are also uniform-weighted edge-loss optimal upwards of 99% of the time, whereas triangle-loss cycles can provide distinct information.The reported agreement concerns the data studied; triangle-loss cycles may have higher edge loss than length- or uniform-weighted minimal cycles.Source: §7 · p. 42
• All but one ℓ1-optimal representative were also ℓ0-optimal in real-world and synthetic point-cloud data, but Erdős–Rényi random complexes showed qualitatively different behavior.The ℓ0 comparison restricts coefficients to {0, 1, −1}; optimality among integer-coefficient cycles was not tested.Source: §7 · p. 42

9 Author Contributions

• G.H-P. wrote the Eirene code, while L.L. and C.T. wrote the remaining code and performed the experiments.Source: §9 · p. 43
• L.L. created the figures and tables; G.H-P. and L.Z. designed, directed, and supervised the project.Source: §9 · p. 43
• G.H-P. developed the Supplementary Material theory, and all authors contributed to results analysis and manuscript writing.Source: §9 · p. 43

10 Funding

• The authors acknowledge support from the National Science Foundation.Source: §10 · p. 43
• The acknowledged support includes grant DMS-1854683.Source: §10 · p. 43
• The acknowledged support also includes grants DMS-1854703 and DMS-1854748.Source: §10 · p. 43

A Review: Standard algorithm to compute persistent homology cycle bases, by matrix decomposition

• The standard procedure computes a persistent-homology cycle basis using an R = DV decomposition of boundary matrices.The decomposition is reviewed as the first step of Algorithms 1 and 2.Source: A Review: Standard algorithm to… · p. 47
• In the decomposition, R is reduced and V is invertible and upper triangular; reduced means the low function is injective.Source: A Review: Standard algorithm to… · p. 47
• The simplex set partitions into B_n, B*_n, and H_n, and the relevant boundary-matrix columns for B*_n(t) form a basis for boundaries at time t.Source: A Review: Standard algorithm to… · p. 47
• The decomposition yields a persistent cycle basis from V_n[:, H_n] and R_n[:, E_n], with lifespans determined by simplex birth and death times.The stated lifespans are [Birth(σ), ∞) for V_n[:, σ] and [Birth(σ), Birth(τ)) for R_n[:, τ].Source: A Review: Standard algorithm to… · p. 47
• The barcode of K• can be read from the R = DV decompositions.Source: A Review: Standard algorithm to… · p. 47

• The section establishes correctness proofs for Algorithms 1 and 2.Source: B Correctness of Algorithms 1 and 2 · p. 47
• The exposition is fairly terse because the proof details are primarily technical.Source: B Correctness of Algorithms 1 and 2 · p. 47
• The arguments are primarily self-contained, but the proof of Algorithm 1 begins by recalling a result from [37].Source: B Correctness of Algorithms 1 and 2 · p. 47

• A subset E of Xi,j is an (i, j)-basis when its image under qi,j is injective and forms a basis of Qi,j.Source: §B.1 · p. 47
• A family of n-cycles is a persistent homology cycle basis exactly when it is an (i, j)-basis for every i and j.Source: §B.1 · p. 48
• Theorem B.2 draws on results in [37] [38]; its simplex-wise filtration special case also appeared in [63, Theorem 1] and is related to pair groups.Source: §B.1 · p. 48

• The algorithm starts from a computed dimension-one persistent homology basis over Q and returns the final sequence of cycle representatives.Source: §B.2 · p. 48
• At each iteration, the algorithm optimizes the next cycle representative and replaces that element while leaving the other sequence elements unchanged.Source: §B.2 · p. 48
• For every intermediate sequence, the cycles form a persistent homology cycle basis and preserve lifespans.Source: §B.2 · p. 48
• In the proof, the updated family retains the same span through the replacement construction, yielding an (i, j)-basis and preserving the original cycle's lifespan.Source: §B.2 · p. 49
• Algorithm 3 returns B* as a bona fide persistent homology cycle basis.Source: §B.2 · p. 49

• The linear program associated with a birth-death pair in uses the family of simplices born strictly between the pair's birth and death times.Source: §B.3 · p. 50
• Program (15), the general triangle-loss problem, is a special case of Program (10) for the selected birth-death pair.Source: §B.3 · p. 50
• The refinement orders simplices by birth time, then dimension, then the chosen linear orders, producing a simplex-wise refinement of the filtration.Source: §B.3 · p. 50
• For a refinement of a filtration, retaining basis cycles whose original-filtration birth precedes death gives a persistent homology cycle basis of the original filtration.Source: §B.3 · p. 51
• Algorithm 4 returns a bona fide persistent homology cycle basis of K•.Source: §B.3 · p. 51

C Supplementary Tables and Figures

• Table 4 classifies optimal-cycle coefficients as integral or in {−1, 0, 1}, across integer- and linear-programming solutions and three cycle-optimization types.The table covers the real-world and synthetic data sets discussed in Sections 5.1 and 5.2.Source: Table 4 · p. 52
• Gurobi is consistently faster than GLPK for the uniform- and length-weighted edge-loss optimization problems.The comparison covers 90 normally distributed data sets across dimensions 2–10.Source: Figure 14 · p. 53
• Computation time seems fairly constant across dimensions 2–10 for the tested edge-loss problems.The data sets comprise 10 per dimension, generated from the normal distribution.Source: Figure 14 · p. 53