Source-linked AI summary
Persistence stability for geometric complexes
Frederic Chazal, Vin de Silva, Steve Oudot
TL;DR
The paper studies how persistent homology of geometric filtered complexes behaves for approximations of precompact metric spaces. It develops persistence-based proofs of stability with respect to Gromov–Hausdorff distance and extends the results beyond finite spaces and Rips complexes. It also identifies scope boundaries for witness complexes and higher-dimensional simplex arguments.
Problem
The paper addresses stability and homological behavior of geometric filtered complexes built on precompact spaces, including cases beyond finite metric spaces.
Method
The paper uses ε-simplicial multivalued maps and persistence-module interleavings to analyze filtered Rips, Čech, witness, and Dowker complexes.
Results
The stability inequality extends to all totally bounded metric spaces and a larger class of filtered geometric complexes, while Rips and Čech persistence modules are q-tame there.
Takeaways & Limitations
Persistence diagrams provide well-defined stable invariants for these filtrations, even though individual Rips and Čech homology groups may be infinite dimensional at some scales.
Takeaways & Limitations
Witness-complex stability does not extend in full generality when the landmark set is perturbed, even with fixed witnesses, and higher-dimensional simplex subdivision requires further assumptions.
Abstract
from arXiv · showhide
In this paper we study the properties of the homology of different geometric filtered complexes (such as Vietoris-Rips, Cech and witness complexes) built on top of precompact spaces. Using recent developments in the theory of topological persistence we provide simple and natural proofs of the stability of the persistent homology of such complexes with respect to the Gromov--Hausdorff distance. We also exhibit a few noteworthy properties of the homology of the Rips and Cech complexes built on top of compact spaces.
1 Introduction
The paper addresses how to recover topology from metric approximations without relying on a difficult scale choice. It extends persistence-based stability results to totally bounded spaces and several filtered geometric complexes.
- Motivation: Topological inference seeks a simplicial complex on an approximating metric space whose homology or homotopy type matches the unknown space.The approximating space need not be finite a priori.
- Geometric complexes: Rips complexes contain finite subsets of diameter at most α and are useful because they are easy to compute and approximate topology well.For closed Riemannian manifolds, sufficiently small scales recover the homotopy type.
- Motivation: Persistence encodes the homology of the entire nested Rips filtration, allowing users to select relevant scales through a persistence diagram.This avoids depending on a scale that may be difficult to determine from the geometry.
- Contributions: The paper shows that the bottleneck-distance stability inequality extends from finite to totally bounded metric spaces and to a broader class of filtered geometric complexes.The broader class includes Dowker complexes.
- Contributions: ε-simplicial multivalued maps induce canonical ε-interleavings between persistent homology modules of filtered complexes.This provides the central map-level mechanism for the stability results.
- Contributions: For totally bounded vertex sets, the relevant persistent homology modules are tame, so persistence diagrams are well behaved and stability results apply.The paper also studies Rips and Čech homology properties, including results for path-metric and δ-hyperbolic spaces.
2 Persistence modules and persistence diagrams
The paper formalizes persistent homology as a persistence module obtained from homology across a filtered complex. It uses interleavings of such modules to obtain bottleneck-distance bounds for persistence diagrams.
- Persistence modules: A persistence module consists of vector spaces indexed by real parameters together with structure maps satisfying identity and composition laws.The paper works with vector spaces over a fixed field.
- Persistence modules: A filtered simplicial complex produces a persistence module by taking homology at each scale and using inclusion-induced maps between scales.The composition law follows from functoriality of homology.
- Interleavings: A degree-ε homomorphism shifts the target filtration parameter by ε, providing the basic language for comparing filtered homology.The shift map is the principal degree-ε endomorphism.
- Interleavings: Two persistence modules are ε-interleaved when maps in both directions satisfy compatibility with the ε-shift structure.This comparison notion connects filtered complexes to persistence-diagram stability.
- Persistence diagrams: For q-tame modules, persistence diagrams are well defined, and ε-interleaving yields an ε-matching and bottleneck distance at most ε.This theorem is the bridge from module-level stability to diagram-level stability.
3 Multivalued maps
The paper extends simplicial maps to ε-simplicial multivalued maps between filtered complexes. These maps induce canonical homology morphisms that are independent of subordinate choices and compose with additive degree shifts.
- Definitions: An ε-simplicial map sends every simplex at filtration value a to a simplex at value a+ε.This is equivalently a simplicial map at every shifted filtration level.
- Definitions: A multivalued map is a relation projecting surjectively onto its source, and ordinary maps subordinate to it select one target for each source point.Multivalued-map composition is defined through an intermediate target point.
- Definitions: An ε-simplicial multivalued map requires every finite subset of the image of each simplex to be a simplex at the shifted filtration value.This generalizes the single-valued notion while retaining a filtration shift.
- Induced maps: An ε-simplicial multivalued map induces a canonical degree-ε homology map, equal to the map induced by any subordinate simplicial selection.The induced map is well defined because subordinate choices yield contiguous maps.
- Induced maps: The induced homology map is unchanged when the multivalued map is replaced by an ε-simplicial subrelation.Thus the construction depends only on the relevant multivalued relation, not on a particular subordinate selection.
- Composition: Composing ε- and δ-simplicial multivalued maps produces an (ε + δ)-simplicial map whose induced homology map is the composite of the original maps.This additive composition law supports interleaving constructions.
4 Correspondences
Correspondences transfer filtered-complex structure into canonical interleavings, yielding stability results for intrinsic and ambient Čech, Rips, Dowker, and witness filtrations under metric perturbations.
- Correspondences and interleavings: A correspondence between vertex sets induces a canonical ε-interleaving when it and its transpose are ε-simplicial.The induced interleaving maps are the homology maps associated with the correspondence and its transpose.
- Correspondences and interleavings: For metric spaces, correspondence distortion is the supremum of pairwise distance discrepancies, while Gromov–Hausdorff distance is the infimum over correspondence distortions.Distortion is symmetric under transposition, and composition gives the triangle-inequality bound.
- Metric filtered complexes: Rips filtrations on metric spaces are ε-interleaved whenever ε > 2dGH(X, Y).Low-distortion correspondences send simplices at scale a to simplices at scale a + ε, and the transpose supplies the reverse map.
- Metric filtered complexes: Intrinsic Čech filtrations satisfy the same bound: H(Čech(X)) and H(Čech(Y)) are ε-interleaved for ε > 2dGH(X, Y).The correspondence transfers an a-centre in X to an (a + ε)-centre in Y.
- Dowker and ambient Čech complexes: Dowker filtrations are ε-interleaved when paired correspondences have joint distortion at most ε, and ambient Čech filtrations are ε-interleaved for ε > dH(L, L′).The ambient Čech result does not require the usual Euclidean Nerve Lemma argument.
- Witness complexes: Witness filtrations are ε-interleaved for ε ≥ 2 dis(C) when only the witness sets vary, but arbitrary landmark perturbations need not be stable.For landmarks L and L′ with fixed witnesses, interleaving can fail below 1 − 2δ even when dH(L, L′) = δ is arbitrarily small.
5 Regularity of Rips and ˇCech filtrations
For totally bounded spaces, Rips, Čech, ambient Čech, and Dowker persistence modules are sufficiently regular for persistence-diagram stability, while individual homology groups can still be infinite-dimensional.
- Regularity and stability: Totally bounded metric spaces have q-tame persistent homology modules for both Rips and Čech filtrations.Total boundedness means finite ε-samples exist at every resolution.
- Regularity and stability: The resulting Rips persistence diagrams are well defined and satisfy db(dgm(H(Rips(X))), dgm(H(Rips(Y )))) ≤2dGH(X, Y ).The bound extends the finite-space stability result to totally bounded metric spaces.
- Regularity and stability: Ambient Čech persistence is q-tame when at least one of its landmark or witness sets is totally bounded, so its persistence diagram is well defined.The same total-boundedness condition supports the corresponding stability theorem for pairs of landmark sets.
- Regularity and stability: Dowker persistence is q-tame when its defining function family is bounded and totally bounded in the supremum norm; Lipschitz functions on totally bounded spaces provide an example.This extends the regularity analysis beyond Rips and Čech complexes.
- Non-persistent homology: Persistent regularity does not imply finite-dimensional homology at every scale: individual Rips and Čech homology groups may be infinite-dimensional.Examples include uncountably infinite-dimensional H1 for Rips complexes and arbitrary-degree infinite-dimensional Čech homology.
- Open Vietoris–Rips filtration: For every totally bounded metric space, the total homology of the open Rips filtration has a countable basis, although finite dimensionality is not guaranteed.The proof expresses it as a union of finite-dimensional images arising from finite approximations.
3. Any 1-cycle can be written as a finite linear combination of cycles of the form
The section reduces arbitrary 1-cycles to finite combinations of closed polygonal cycles and open paths, then eliminates path endpoints using the zero-boundary condition.
- 3. Any 1-cycle can be written as a finite linear combination of cycles of the form: A closed cycle has the form [x1, x2] + [x2, x3] + · · · + [xk−1, xk] + [xk, x1].An open path instead ends at a vertex distinct from its starting point.
- 3. Any 1-cycle can be written as a finite linear combination of cycles of the form: Any 1-cycle can be decomposed into a finite linear combination of closed cycles and paths.Paths may be taken as finite edge chains, including the trivial decomposition into length-one paths.
- 3. Any 1-cycle can be written as a finite linear combination of cycles of the form: Free vertices are removed one by one by concatenating paths terminating at the same vertex, decreasing their number while preserving the cycle condition.Because the boundary vanishes, at least two paths terminate at each free vertex selected.
4. Consider a cycle of the form
A 1-cycle in the Čech complex can be replaced, through local triangles, by a homologous cycle whose edges lie in a finite set of controlled edges.
- 4. Consider a cycle of the form: A closed 1-cycle is represented as a cyclic edge chain [x1, x2] + [x2, x3] + · · · + [xk, x1].This is the cycle form used for the finite-edge reduction.
- 4. Consider a cycle of the form: Any such cycle whose edges have length at most a is homologous in Čech(X, a) to a cycle using only edges from the finite set Ea.The reduction is the key finite-generation step for first Čech homology.
- 4. Consider a cycle of the form: Each original edge is approximated by an edge in Ea, and the resulting replacement is connected to it through triangles in Čech(X, a).The construction inserts intermediate vertices and uses the corresponding triangles to establish homology.
- 4. Consider a cycle of the form: Consequently, every 1-cycle is homologous to one involving only finitely many edges, implying that H1(Čech(X, a); A) is finitely generated.This conclusion holds over any coefficient ring A under the stated construction.
6 Special classes of metric spaces
For path metric spaces, Rips H1 classes do not appear after any positive scale. For δ-hyperbolic geodesic spaces, Rips H2 classes do not appear after scale 2δ, yielding corresponding persistence-diagram constraints.
- 6.1 The persistence diagram of H1(Rips) for a path metric space: The path-metric argument subdivides each edge into smaller simplices, making homology classes persistently representable at smaller Rips scales.A 1-cycle is decomposed into edges, and each edge is replaced through an intermediate point by two shorter edges.
- 6.1 The persistence diagram of H1(Rips) for a path metric space: The H1 persistence diagram of any path metric space is contained in the vertical line {0} × [0, +∞).This conclusion does not require total boundedness of the space.
- 6.1 The persistence diagram of H1(Rips) for a path metric space: Path metric spaces have no new Rips 1-cycles once the diameter is strictly positive.The maps H1(Rips(X, p)) → H1(Rips(X, q)) are surjective whenever 0 < p < q.
- 6.2 The persistence diagram of H2(Rips) for a δ-hyperbolic space: The H2 construction splits each triangle into four using midpoint vertices and verifies homology through tetrahedra whose edges remain within the original Rips scale.The resulting cycle is homologous to the original through a 3-cycle in Rips(X, q).
- 6.2 The persistence diagram of H2(Rips) for a δ-hyperbolic space: For a δ-hyperbolic geodesic space, H2(Rips(X, p)) → H2(Rips(X, q)) is surjective whenever q > p > 2δ.Triangles are subdivided using side midpoints and δ-hyperbolicity controls the new edges.
- 6.2 The persistence diagram of H2(Rips) for a δ-hyperbolic space: The H2 persistence diagram of a δ-hyperbolic geodesic space is confined to the vertical strip [0, 2δ] × [0, +∞).Equivalently, no new H2 classes occur once the Rips diameter exceeds 2δ.