PaperlayerView exact revision on arXiv

Source-linked AI summary

A roadmap for the computation of persistent homology

Nina Otter, Mason A. Porter, Ulrike Tillmann, Peter Grindrod, Heather A. Harrington

arXiv:1506.08903v7math.ATcs.CGphysics.data-anq-bio.QM

TL;DR

Persistent homology lacks a comprehensive overview of computational methods and state-of-the-art implementations. This paper surveys the computation pipeline and benchmarks open-source libraries, finding that performance varies by complex and algorithm, with ripser, Gudhi, and DIPHA fastest overall.

  • Problem

    Persistent homology lacks an overview of computational methods and comprehensive benchmarking of state-of-the-art implementations, limiting guidance for computational scientists.

  • Method

    The paper introduces persistent-homology theory and computation, surveys the pipeline, and benchmarks open-source implementations on synthetic and real-world data.

  • Results

    Performance varied by complex and algorithm: ripser led for Vietoris–Rips, Gudhi and DIPHA were strongest for cubical complexes, and dual algorithms outperformed standard ones.

  • Takeaways & Limitations

    Ripser, Gudhi, and DIPHA were fastest overall, while Perseus and javaPlex offered easier plug-and-play use for small complexes and initial exploration.

  • Takeaways & Limitations

    Sparsification techniques remain underimplemented, and further research is needed for the data-to-complex and barcode-interpretation stages, especially statistical analysis.

Abstract

from arXiv · show

Persistent homology (PH) is a method used in topological data analysis (TDA) to study qualitative features of data that persist across multiple scales. It is robust to perturbations of input data, independent of dimensions and coordinates, and provides a compact representation of the qualitative features of the input. The computation of PH is an open area with numerous important and fascinating challenges. The field of PH computation is evolving rapidly, and new algorithms and software implementations are being updated and released at a rapid pace. The purposes of our article are to (1) introduce theory and computational methods for PH to a broad range of computational scientists and (2) provide benchmarks of state-of-the-art implementations for the computation of PH. We give a friendly introduction to PH, navigate the pipeline for the computation of PH with an eye towards applications, and use a range of synthetic and real-world data sets to evaluate currently available open-source implementations for the computation of PH. Based on our benchmarking, we indicate which algorithms and implementations are best suited to different types of data sets. In an accompanying tutorial, we provide guidelines for the computation of PH. We make publicly available all scripts that we wrote for the tutorial, and we make available the processed version of the data sets used in the benchmarking.

1 Introduction

Persistent homology uses topology to study qualitative data features across scales, representing their lifetimes in barcodes, while this article introduces computational methods, guidelines, and benchmarks for state-of-the-art implementations.

  • Motivation and overview: Persistent homology studies qualitative features of data across multiple scales using algebraic-topological invariants and represents their lifetimes as barcodes.Barcodes encode feature birth and death, including components, holes, and higher-dimensional voids.
  • Motivation and overview: PH computation supports data types including finite metric spaces, digital images, level-sets of real-valued functions, and networks.Point clouds are thickened across resolution scales, while digital images can be represented using cubical complexes.
  • Challenges: A major challenge is statistically interpreting computed barcodes because practitioners may lack statistical training and barcode space lacks convenient geometric properties.These obstacles complicate defining basic summaries such as means and medians.
  • Computational landscape: The rapidly evolving PH field now offers numerous algorithms and implementations, making it difficult to determine which are best suited to a given task.The article addresses this selection problem through a broad computational introduction and evaluation of existing open-source published libraries.
  • Article contributions: The article closes the field’s overview and benchmarking gap by introducing PH computation, providing guidelines, and testing state-of-the-art open-source implementations.It targets applied mathematicians and computational scientists and makes tutorial scripts and processed benchmark data publicly available.

2 Related work

The paper addresses gaps in existing persistent homology literature by combining application-oriented computational guidance with systematic benchmarking of open-source libraries. It introduces five libraries through a tutorial and compares them across twelve data sets.

  • 2 Related work: The paper introduces persistent homology to non-experts with an applications focus and benchmarks state-of-the-art computational libraries.This addresses both the paper’s introductory and benchmarking aims.
  • 2 Related work: Existing introductions explain persistent homology theory but generally do not provide specific computational guidelines for practitioners.The paper therefore navigates the theory with an eye toward applications and supplies computation-focused guidance.
  • 2 Related work: The tutorial provides instructions for using Perseus, Dionysus, DIPHA, javaPlex, and Gudhi across their implemented functionalities.It consolidates information otherwise scattered across papers, websites, and implementation source code.
  • 2 Related work: 12 data sets are used to test and compare javaPlex, Gudhi, DIPHA, Dionysus, and Perseus in a thorough state-of-the-art benchmark.The authors report surprising results and situate their study among earlier persistent homology benchmarkings.

3 Homology

This section introduces homology as an algebraic-topological framework for capturing components, holes, and voids, and explains how simplicial complexes make these invariants computable. It also emphasizes that computational choices, including coefficient fields and complex construction, affect feasibility and results.

  • Homology foundations: Homology captures qualitative characteristics such as connected components, holes, and voids through algebraic invariants.These invariants can determine a space’s topology up to homotopy under favorable conditions.
  • Simplicial complexes: Simplicial complexes approximate arbitrary spaces and discrete samples, enabling algorithmic computation of homology.They are built from combinatorial elements such as vertices, edges, triangles, tetrahedra, and higher-dimensional polytopes.
  • Homology foundations: The pth homology is Hp(K) := kernel(dp) / image(dp+1), separating p-cycles from p-boundaries.The quotient is valid because the boundary of a boundary is empty, so image(dp+1) is contained in kernel(dp).
  • Homology foundations: Betti numbers count p-dimensional holes represented by p-cycles that are not p-boundaries.For a simplicial complex of dimension n, Hp(K) = 0 for all p > n.
  • Functoriality: Functoriality makes homology compatible with maps and composition, a property crucial to defining persistent homology.A simplicial-complex map f induces maps fp between homology vector spaces, with (g ◦f)p = gp ◦fp for composable maps.
  • Coefficient fields: Changing coefficient fields can alter Betti numbers, as shown for the Klein bottle: β1(K) = 2 and β2(K) = 1 for p = 2, versus β1(K) = 1 and β2(K) = 0 otherwise.The paper therefore uses F2 coefficients, which also match the requirements for barcode-based topological summaries and most PH implementations.
  • Computational considerations: The Čech complex is computationally expensive because checking many intersections can produce dimension |U| −1 and many high-dimensional simplices.This motivates complexes that approximate homology while remaining easy to compute and sparse, especially in high dimensions.

4 Persistent homology

Persistent homology extracts qualitative features robustly by tracking homology across multiple parameter values rather than choosing a single scale. For filtered simplicial complexes, it records inclusion-induced homology maps and represents generator lifetimes through barcodes.

  • Motivation: Persistent homology addresses the lack of a clear scale by computing qualitative features across several or all values of ϵ as simplices are added.This supports recovering properties of an underlying space robustly to small perturbations in the data.
  • Filtered complexes: A filtered simplicial complex is a finite sequence of nested subcomplexes, with homology applied at each filtration step.For every homology degree p, inclusions induce F2-linear maps between the corresponding homology groups.
  • Persistent homology: The pth persistent homology of a filtered complex consists of the homology vector spaces together with inclusion-induced maps between them.These maps satisfy the functoriality property and form an example of a persistence module.
  • Barcodes: With field coefficients, the Fundamental Theorem of Persistent Homology yields a unique collection of disjoint half-open intervals called a barcode.The barcode provides a compact representation of the persistent homology information.
  • Births and deaths: Generators are born when they are absent from the preceding map’s image and die at the first later filtration step where their image becomes zero.Their lifetimes are represented by intervals [i, j), or [i, ∞) when they persist forever.
  • Definitions: An alternative definition of death can differ from the compatible-basis definition used here.Some references also count death when a generator becomes equivalent to the image of another later generator, not only when its image is zero.

5 Computation of PH for data

This section presents the pipeline for computing persistent homology from data and introduces state-of-the-art algorithms for its steps. It emphasizes that persistent homology is computable via linear algebra and stable under perturbations in data measurements.

  • Pipeline: The computation of persistent homology from data is organized as a pipeline whose steps are described alongside state-of-the-art algorithms.The pipeline is summarized in Figure 6.
  • Foundations: Persistent homology is appealing for applications because it is computable via linear algebra and stable with respect to perturbations in data measurements.The section provides a brief overview of stability results in Section 5.5.
  • Representations: Barcode diagrams require choosing a vertical order for intervals, whereas persistence diagrams represent the same intervals as points without this ambiguity.The collection of intervals is unique, but barcode drawings are not uniquely represented because of the ordering choice.

5.1 Data

Persistent homology can analyze finite metric spaces, digital images, and networks by choosing data representations and filtrations suited to each structure. Networks may be extended to higher-dimensional clique complexes, while images naturally use cubical complexes or can be modeled as finite metric spaces.

  • Data types: PH studies finite metric spaces, digital images, and networks, with methods adapted to each data type.These data types provide the section’s main computational settings for PH.
  • Networks: Undirected networks form 1-dimensional simplicial complexes, and weight filtrations produce filtered complexes.Increasing or decreasing network weights defines the filtration direction.
  • Networks: The weight rank clique filtration builds a clique complex on each subnetwork to add higher-dimensional simplices.This is presented as the simplest method for refining network information.
  • Digital images: Digital images naturally use cubical complexes because 2-dimensional images comprise pixels and 3-dimensional images comprise voxels.Cubical complexes are assembled from vertices, edges, squares, cubes, and higher-dimensional analogues, and PH can be computed similarly to the simplicial case.
  • Digital images: Images can also be represented as points in a c×N-dimensional space and treated as finite metric spaces after defining an appropriate distance function.Each coordinate stores a length-c color vector for one of the N pixels or voxels.

5.2 Filtered Simplicial Complexes

This section surveys filtered simplicial complexes designed to approximate topological structure while reducing the computational burden of Čech complexes. It presents Vietoris–Rips, Delaunay, alpha, and witness complexes, emphasizing their constructions, guarantees, and scalability tradeoffs.

  • Theoretical motivation: Useful simplicial complexes should approximate the homology of the underlying space, motivating sparsification approaches for applications.For the Čech complex, this guarantee follows from the Nerve Theorem.
  • Vietoris–Rips complexes: The Vietoris–Rips complex includes simplices whose vertices have pairwise distances at most 2ϵ, and in Euclidean space satisfies Čech_ϵ(S) ⊆ VR_ϵ(S) ⊆ Čech_√2ϵ(S).It can be constructed by forming the ϵ-neighborhood graph and then taking its clique complex.
  • Vietoris–Rips complexes: Vietoris–Rips complexes are usually truncated to dimension k ≪ |S| − 1, with the benchmark often using k = 2 and k = 3.This truncation limits the number of high-dimensional simplices that must be computed.
  • Delaunay and alpha complexes: Delaunay complexes reduce high-dimensional simplex counts geometrically, but their construction has complexity O(N log N) for d ≤ 2 and O(N ⌈d/2⌉) for d ≥ 3.Efficient algorithms exist for d = 2 and d = 3, while higher-dimensional construction remains costly.
  • Delaunay and alpha complexes: Alpha complexes are nerves of Voronoi-ball intersections, have the same homology as the union S_ϵ by the Nerve Theorem, and form subcomplexes of the Delaunay complex.At infinite scale, the alpha complex equals the Delaunay complex.
  • Witness complexes: Witness complexes construct complexes on a smaller landmark subset L ⊆ S while using all points in S as witnesses, and ϵ-witnesses produce nested complexes.The resulting weak Delaunay complex is also called the weak witness complex or witness complex.

5.3 From a Filtered Simplicial Complex to Barcodes

Persistent homology is computed by ordering simplices compatibly with the filtration, constructing and reducing a boundary matrix, and translating the reduced matrix into barcode intervals. The standard algorithm uses the map low to identify simplex pairings and remains one of several algorithms with the same PH output.

  • Boundary matrix construction: Simplices are totally ordered so every face precedes its simplex and filtration-earlier simplices precede later newly added simplices.This ordering makes the boundary matrix compatible with the filtration.
  • Boundary matrix construction: The n × n boundary matrix stores 1 when σi is a codimension-1 face of σj and 0 otherwise.The matrix records face relations among all n simplices.
  • Matrix reduction: The standard algorithm reduces the boundary matrix by Gaussian elimination and defines low(j) as the largest nonzero row index in column j.A matrix is reduced when low is injective wherever defined, and field coefficients are required for this reduction.
  • Reading barcodes: A defined low(j) pairs σj with σi, making σi’s entrance the birth and σj’s entrance the death of a feature.If low(j) = i, the resulting barcode interval is determined by that simplex pair.
  • Reading barcodes: Each pair (σi, σj) yields [dg(σi), dg(σj)), while an unpaired simplex σk yields [dg(σk), ∞).Here dg(σ) is the first filtration index containing σ.

5.4 Statistical interpretation of topological summaries

Statistical interpretation of persistent-homology outputs requires methods for comparing barcodes with null models, averaging across realizations, and applying statistical analysis. Current approaches analyze persistence-diagram geometry or map diagrams into spaces suited to statistical and machine-learning techniques, but practical tools remain limited.

  • Motivation: PH applications require comparing computed barcodes with null-model outputs or averaging results across multiple generative-model realizations.These uses create the need for methods to compare outputs and aggregate results across realizations.
  • Statistical approaches: Statistical analysis treats a barcode as an unknown quantity estimated through persistent-homology computation.The paper identifies statistical methods for PH as necessary for reliable application of PH outputs.
  • Statistical approaches: One approach defines a space of persistence diagrams with distances, enabling means, medians, and statistical tests.Persistence diagrams encode the same information as barcodes, and Wasserstein and bottleneck distances are commonly used for comparisons.
  • Limitations: Statistical analysis on persistence-diagram spaces remains under development, with few application-ready tools.Until recently, Dionysus was the only library implementing bottleneck and Wasserstein distances for d = L∞, while hera introduced a new algorithm for these computations.
  • Statistical approaches: A third approach maps persistence diagrams into Banach or other tractable spaces for statistical analysis and machine learning.Examples include persistence landscapes, algebraic-function representations, persistence images, and kernelization techniques.

5.5 Stability

Persistent homology is useful in applications because it is stable under small perturbations of input data. Its first stability theorem established a 1-Lipschitz relationship between filtered complexes and barcode bottleneck distance under favorable conditions, and subsequent work generalized this result.

  • Stability: Persistent homology remains stable with respect to small perturbations in the input data, supporting its use in applications.This stability concerns perturbations of the input data used in the PH pipeline.
  • Stability: Under favorable conditions, the first PH stability theorem showed that pipeline step (2) is 1-Lipschitz for suitable filtered-complex distances and barcode bottleneck distance.The result was later generalized in several papers, while stability remains an active research area.

6 Excursus: Generalized persistence

Generalized persistence extends persistent homology to sequences with varying map directions, non-inclusion maps, and multiple filtration parameters. Multi-parameter persistence lacks the Fundamental Theorem and generalized intervals, so extracting topological information remains an active research area.

  • Generalized persistence: Algorithms for same-direction inclusion maps can compute persistent homology for sequences of complexes.The section applies the algorithms described in Section 5 to inclusion maps going in one direction.
  • Generalized persistence: The zigzag algorithm computes persistent homology when inclusion maps do not all go in the same direction.This algorithm was introduced in [31].
  • Generalized persistence: For maps that are not inclusions, persistent homology can still be computed using the simplicial map algorithm.The simplicial map algorithm is referenced as [58].
  • Generalized persistence: Varying two or more parameters produces multi-filtered simplicial complexes and multi-parameter persistent homology.The complexes are organized across multiple indices, as illustrated by the displayed diagram.
  • Generalized persistence: Multi-parameter persistence has no valid Fundamental Theorem of Persistent Homology or “generalized interval,” and approaches for extracting topological information remain under active research.The theory is discussed in.

7 Software

The paper surveys publicly available persistent-homology software and benchmarks selected open-source libraries across synthetic and real-world data. It identifies performance trade-offs and recommends implementations according to complex type, data size, and usability.

  • Software overview: The paper overviews publicly available persistent-homology implementations and summarizes their properties in a comparative table.The surveyed libraries include javaPlex, Perseus, jHoles, Dionysus, PHAT, DIPHA, SimpPers, Gudhi, and ripser.
  • Benchmark design: The benchmark evaluates javaPlex, Perseus, Dionysus, DIPHA, Gudhi, and ripser using CPU time, wall time, memory use, and maximum simplicial-complex size.The study uses both synthetic and real-world data and focuses on algorithms implemented by the largest number of packages.
  • Benchmark data: The benchmark data comprise point clouds, weighted undirected networks, and grey-scale digital images from mathematical, scientific, and applied domains.The collection includes synthetic and empirical data sets and is presented as an initial step toward a comprehensive benchmarking collection.
  • Benchmark results: Ripser performs best for Vietoris–Rips complexes, followed by Gudhi and DIPHA, while Gudhi uses 3 to 4 times less memory than DIPHA for cubical complexes.For cubical complexes, DIPHA instead achieves wall times 1 to 2 times faster than Gudhi when both run on one core in a shared-memory system.
  • Benchmark results: Dual implementations substantially outperform standard implementations in both computation time and memory usage.The comparison covers both CPU and wall-time seconds and finds a large performance disparity between the two algorithmic approaches.
  • Practical guidelines: Ripser, Gudhi, and DIPHA are the fastest packages overall, whereas Perseus and javaPlex are recommended for small complexes because they are easiest to use.Perseus and javaPlex are the only libraries described as download-only, plug-and-play, and user-friendly.

8 Future directions

Future work should prioritize the underdeveloped data-to-complex stage of the persistent homology pipeline, alongside community infrastructure for extensible implementations and standardized evaluation.

  • Research priorities: Step 1, constructing filtered complexes from data, remains an active research area, while many complex-sparsification techniques have yet to be explored.By contrast, Step 2 has many fast boundary-matrix reduction algorithms and implementations.
  • Community infrastructure: The field needs a community-wide, extensible library implementing algorithms and data structures for persistent homology.The proposed model parallels established efforts in computational algebra and computational geometry, including Macaulay2, Sage, and CGAL.
  • Evaluation standards: New persistent-homology algorithms and data structures also require shared guidelines and benchmark data sets for testing.The paper’s benchmarking methods and data sets provide an initial foundation for these guidelines and test problems.
Loading 1506.08903v7…