Source-linked AI summary
Induced Matchings and the Algebraic Stability of Persistence Barcodes
Ulrich Bauer, Michael Lesnick
TL;DR
Earlier proofs produce the barcode matching for interleaved persistence modules only indirectly. This paper defines a matching from each morphism and proves that its quality is controlled by kernel and cokernel barcode intervals, yielding algebraic stability and related characterizations.
Problem
Earlier proofs construct the matching from a δ-interleaving only implicitly through technical lemmas, compactness, and interpolating barcodes.
Source: §1 · p. 4Method
The paper defines a map from morphisms of pointwise finite dimensional persistence modules to matchings between their barcodes.
Source: §1.1 · p. 4Results
Kernel and cokernel interval lengths control the induced matching, yielding algebraic stability for pointwise finite dimensional persistence modules.
Source: §1.1 · p. 4Takeaways & Limitations
A pair of pointwise finite dimensional modules is δ-interleaved exactly when a morphism to the δ-shift has kernel and cokernel barcode intervals of length at most 2δ.
Source: §1.1 · p. 4
Abstract
from arXiv · showhide
We define a simple, explicit map sending a morphism $f:M \rightarrow N$ of pointwise finite dimensional persistence modules to a matching between the barcodes of $M$ and $N$. Our main result is that, in a precise sense, the quality of this matching is tightly controlled by the lengths of the longest intervals in the barcodes of $\ker f$ and $\mathop{\mathrm{coker}} f$. As an immediate corollary, we obtain a new proof of the algebraic stability of persistence, a fundamental result in the theory of persistent homology. In contrast to previous proofs, ours shows explicitly how a $\delta$-interleaving morphism between two persistence modules induces a $\delta$-matching between the barcodes of the two modules. Our main result also specializes to a structure theorem for submodules and quotients of persistence modules, and yields a novel "single-morphism" characterization of the interleaving relation on persistence modules.
1 Introduction
The paper defines an explicit matching induced by a morphism of pointwise finite dimensional persistence modules and proves that its quality is controlled by the longest intervals in the kernel and cokernel barcodes. It applies this result to algebraic stability, submodule and quotient structure, and a single-morphism characterization of interleaving.
1 Introduction
- Algebraic stability says that a δ-interleaving of pointwise finite dimensional modules yields a δ-matching of their barcodes, a result used to justify persistent homology for noisy data.The algebraic theorem generalizes the stability result for real-valued functions and supports comparisons across different domains and data not directly arising from functions.Source: §1 · p. 2
- Earlier algebraic-stability proofs construct a barcode matching only implicitly, through technical lemmas, compactness, and interpolating barcodes.The paper seeks a direct construction from a δ-interleaving to a δ-matching.Source: §1 · p. 4, §1.1 · p. 4
1.1 Induced Matchings of Barcodes
- The map X assigns a barcode matching to each morphism, is not generally functorial, and is functorial on the subcategories of monomorphisms and epimorphisms.The matching is determined by the source, target, and image barcodes, and in turn determines those three barcodes.Source: §1.1 · p. 4
- If kernel barcode intervals have length at most ϵ, the induced matching covers target intervals longer than ϵ; if cokernel intervals have length at most ϵ, it covers source intervals longer than ϵ.In the first case matched right endpoints differ by at most ϵ; in the second, left endpoints differ by at most ϵ, and the target interval is obtained by moving both endpoints left.Source: §1.1 · p. 4
A Structure Theorem for Persistence Submodules and Quotients
- The induced matching theorem specializes to the submodule and quotient structure theorem when the kernel or cokernel is zero.The proof uses none of the technical intermediates in earlier algebraic-stability proofs.Source: A Structure Theorem for Persistence… · p. 5
- For a submodule K of M, canonical barcode injections send intervals of K and M/K to containing intervals of M.The K interval and its image share a right endpoint; the quotient interval and its image share a left endpoint.Source: A Structure Theorem for Persistence… · p. 5
A Single-Morphism Characterization of the Interleaving Relation
- Two pointwise finite dimensional modules are δ-interleaved exactly when a morphism from M to N(δ) has kernel and cokernel barcode intervals of length at most 2δ.Source: A Single-Morphism Characterization of… · p. 5
- The paper derives the q-tame isometry theorem from the p.f.d. isometry theorem, while identifying the choice of a suitable q-tame barcode definition as the chief difficulty.The result extends to q-tame modules, whose structure includes cases arising from compact metric spaces and continuous functions on compact triangulable spaces.Source: A Single-Morphism Characterization of… · p. 6
2 Preliminaries
This section establishes the basic definitions and notation used throughout the paper.
2.1 Persistence Modules and Barcodes
- A persistence module is a functor from the real numbers, viewed as a poset, to vector spaces, with transition maps that compose consistently.A module is pointwise finite dimensional when each vector space is finite dimensional.Source: §2.1 · pp. 6–7
- Barcodes represent multisets of intervals; every pointwise finite-dimensional persistence module is interval-decomposable and has a barcode.An interval module assigns the field to indices in its interval and zero elsewhere.Source: §2.1 · pp. 7–8
2.2 The Category of Matchings
- Matchings are partial bijections, and their composition defines the category Mch whose objects are sets.Their categorical coimage and image are the matched subsets of the source and target.Source: §2.2 · p. 8
2.3 Decorated Endpoints and Intervals
- Intervals are encoded by ordered pairs of decorated endpoints, allowing endpoint inclusion and exclusion to be represented in the real-indexed setting.The endpoint order extends the lexicographic order on real values decorated by − or +.Source: §2.3 · p. 8
3 The Isometry Theorem
For pointwise finite-dimensional persistence modules, the isometry theorem equates δ-interleavings with δ-matchings and identifies interleaving and bottleneck distances. The section develops these notions and discusses dualization.
3.1 Interleavings and the Interleaving Distance
- A δ-interleaving uses morphisms between modules and their δ-shifts, while the interleaving distance is the infimum of such δ values.Shifting a module shifts its barcode intervals to the left by δ.Source: §3.1 · pp. 9–10
- A sup-norm distance δ between functions yields a δ-interleaving between the homology modules of their sublevel-set filtrations.The inclusions between the sublevel sets induce the interleaving after applying homology.Source: §3.1 · p. 10
3.2 δ-Matchings and the Bottleneck Distance
- A δ-matching pairs intervals with endpoint displacement at most δ, leaving unmatched intervals of length at most 2δ.The paper's endpoint-decoration-sensitive definition gives sharper stability results than [10, Section 4.2], although both definitions yield the same bottleneck distance.Source: §3.2 · pp. 10–11, Figure 5 · p. 11
- The bottleneck distance is the infimum of δ admitting a δ-matching, and composition of matchings gives its triangle inequality.Composing a δ1-matching with a δ2-matching yields a (δ1 + δ2)-matching.Source: §3.2 · p. 10
3.3 The Isometry Theorem
- For p.f.d. modules, δ-interleaving is equivalent to δ-matching, so interleaving and bottleneck distances coincide.The algebraic stability theorem is the forward implication; the converse is proved following.Source: §3.3 · p. 11
3.4 Dualization of Persistence Modules
- For a pointwise finite-dimensional module, dualization reverses the index direction and dualizes its barcode by reflecting intervals.The dual of the dual module is canonically isomorphic to the original module.Source: §3.4 · p. 12
4 The Structure of Persistence Submodules and Quotients
Canonical injections pair barcode intervals in decreasing-length order within endpoint classes. The structure theorem describes how these pairings behave under inclusions and quotients of persistence modules.
4.1 Canonical Injections
- Within each fixed endpoint class, a canonical injection maps the ith-largest interval to the ith-largest interval.Intervals are ordered by decreasing length.Source: §4.1 · p. 13, Figure 6 · p. 13
4.2 Structure Theorem
- For a monomorphism M → N, the canonical injection sends each ⟨b, d⟩ in BM to an interval ⟨b′, d⟩ with b′ ≤ b.Source: §4.2 · p. 13
- For an epimorphism M ↠ N, the reverse canonical injection sends each interval ⟨b, d⟩ in BN to an interval ⟨b, d′⟩ in BM with d ≤ d′.Source: §4.2 · pp. 13–14
5 Induced Matchings of Barcodes
The paper assigns a barcode matching to each morphism by factoring it through its image. This matching is determined by the source, target, and image barcodes, but is not generally compatible with composition.
5 Induced Matchings of Barcodes
- For a general morphism, the induced matching is the composition of the matching for its image epimorphism and the matching for its image monomorphism.The epimorphism and monomorphism matchings are defined using reverse and forward canonical injections, respectively.Source: §5 · p. 15
5.1 Properties of Induced Matchings
- The induced matching is completely determined by the barcodes of M, N, and im f, and conversely determines all three.Source: §5.1 · p. 16
5.2 Partial Functoriality of Induced Matchings
- For the example in which g ∘ f = 0, Xg ∘ Xf is nontrivial while Xg∘f is empty, so induced matchings need not respect composition.Source: §5.2 · pp. 17–18
- The induced matching is functorial on the subcategories whose morphisms are monomorphisms or epimorphisms.Source: §5.2 · p. 18
- No functor from persistence modules to matchings can send each module to its barcode.The result follows from the impossibility of such a functor for vector spaces while preserving cardinality as dimension.Source: §5.2 · pp. 18–19
6 The Induced Matching Theorem
The induced matching construction compares the image barcode with a barcode formed by deleting short intervals and shifting the remaining births. For interleavings, it yields an explicit barcode matching and a single-morphism characterization, with a weaker factor in the multidimensional setting.
6 The Induced Matching Theorem
- Deleting intervals shorter than ϵ and shifting remaining births by ϵ forms BNϵ, which the proof sandwiches against the image barcode using canonical injections.The proof uses the barcode of the submodule Nϵ and its inclusion into N.Source: §6 · pp. 19–20
6.1 Algebraic Stability via Induced Matchings
- A δ-interleaving morphism has 2δ-trivial kernel and cokernel, yielding an explicit δ-matching and dB(BM, BN) ≤ dI(M, N).Matched interval endpoints satisfy b′ ≤ b ≤ b′ + 2δ and d − 2δ ≤ d′ ≤ d.Source: §6.1 · p. 22
- The matching construction for δ-interleaved modules depends on one δ-interleaving morphism, without requiring an explicit choice of its reverse morphism.The earlier interpolation-based proofs described here depend essentially on choosing both morphisms.Source: §6.1 · p. 22
6.2 Single-Morphism Characterization of the Interleaving Relation
- Two p.f.d. modules are δ-interleaved exactly when some morphism M → N(δ) has kernel and cokernel both 2δ-trivial.In the multidimensional setting, the converse holds only up to a factor of 2, and the example shows this factor is tight.Source: §6.2 · p. 23
7 Algebraic Stability for q-Tame Persistence Modules
The paper derives algebraic stability for q-tame modules by using interval-decomposable approximations and undecorated barcodes. It obtains the barcode-distance bound from interleaving distance in this setting.
7.1 Undecorated Barcodes of q-Tame Persistence Modules
- A q-tame module may not decompose into interval summands, so its undecorated barcode is defined via the interval-decomposable radical.The radical is a submodule at interleaving distance zero from the original module.Source: §7.1 · pp. 24–25
- Every q-tame module’s radical is interval decomposable, and this paper’s undecorated-barcode definition agrees with the one for interval-decomposable modules.The agreement follows from Proposition 7.2.Source: §7.1 · pp. 24–25
7.2 Algebraic Stability for q-Tame Persistence Modules
- For q-tame M and N, (δ + ϵ)-interleavings for every ϵ > 0 imply a δ-matching between UM and UN, and dB(UM, UN) ≤ dI(M, N).The proof approximates the modules by p.f.d. modules and passes matching bounds to their radical barcodes.Source: §7.2 · p. 25
8 Converse Algebraic Stability
The converse stability results recover interleavings from barcode matchings, first for interval-decomposable modules and then for q-tame modules. Together with the forward bounds, they establish equality of the interleaving and bottleneck distances in both settings.
8.1 Converse Algebraic Stability for Interval-Decomposable Persistence Modules
- For interval-decomposable modules, a δ-matching between barcodes implies a δ-interleaving, giving dB(BM, BN) ≥ dI(M, N).The proof builds interleaving morphisms on matched interval summands and uses trivial morphisms on unmatched parts.Source: §8.1 · pp. 26–27
8.2 Converse Algebraic Stability for q-Tame Persistence Modules
- The proof obtains dB(UM, UN) ≥ dI(M, N) by applying Theorem 8.2 to the radical approximations and using their zero interleaving distance from the original modules plus the triangle inequality.Source: §8.2 · p. 27
- For q-tame modules, the forward and converse bounds give dB(UM, UN) = dI(M, N).The paper identifies this equality as the isometry theorem for q-tame persistence modules.Source: §8.2 · p. 27