Source-linked AI summary
The Theory of the Interleaving Distance on Multidimensional Persistence Modules
Michael Lesnick
TL;DR
Multidimensional persistence modules are substantially richer and more complex than one-dimensional modules, making satisfactory barcode definitions difficult. The paper formalizes multidimensional persistence and interleavings, characterizes interleaving algebraically, and establishes key properties including the one-dimensional isometry theorem and a universality bound.
Problem
Multidimensional persistence modules are richer but more complex, so barcode definitions do not extend in a completely satisfactory way.
Method
The paper defines n-dimensional persistence modules as functors on the coordinatewise poset and characterizes interleavings through presentations differing by small grade shifts.
Results
dI = dB for finite-dimensional 1-D persistence modules, and any other pseudometric d on multidimensional persistence modules satisfies d ≤ dI.
Takeaways & Limitations
The results establish dI as a well-behaved multidimensional generalization of dB with potential applications to shape matching and statistical resampling.
Takeaways & Limitations
How to compute or approximate dI remains an open question, limiting its immediate application despite its potential significance.
Abstract
from arXiv · showhide
In 2009, Chazal et al. introduced $ε$-interleavings of persistence modules. $ε$-interleavings induce a pseudometric $d_I$ on (isomorphism classes of) persistence modules, the interleaving distance. The definitions of $ε$-interleavings and $d_I$ generalize readily to multidimensional persistence modules. In this paper, we develop the theory of multidimensional interleavings, with a view towards applications to topological data analysis. We present four main results. First, we show that on 1-D persistence modules, $d_I$ is equal to the bottleneck distance $d_B$. This result, which first appeared in an earlier preprint of this paper, has since appeared in several other places, and is now known as the isometry theorem. Second, we present a characterization of the $ε$-interleaving relation on multidimensional persistence modules. This expresses transparently the sense in which two $ε$-interleaved modules are algebraically similar. Third, using this characterization, we show that when we define our persistence modules over a prime field, $d_I$ satisfies a universality property. This universality result is the central result of the paper. It says that $d_I$ satisfies a stability property generalizing one which $d_B$ is known to satisfy, and that in addition, if $d$ is any other pseudometric on multidimensional persistence modules satisfying the same stability property, then $d\leq d_I$. We also show that a variant of this universality result holds for $d_B$, over arbitrary fields. Finally, we show that $d_I$ restricts to a metric on isomorphism classes of finitely presented multidimensional persistence modules.
1 Introduction
Multidimensional persistence modules extend persistent homology to richer data representations, but their complexity prevents a satisfactory barcode theory. The paper develops the barcode-free interleaving distance and establishes its principal structural, universality, and metric properties.
- Foundations: n-dimensional persistence modules are functors R^n → Vect, while n-dimensional filtrations are functors R^n → Top mapping morphisms to inclusions.The paper also gives an equivalent graded-module formulation over a monoid ring.
- Motivation: Multidimensional filtrations arise naturally from data and metric spaces, including Vietoris-Rips constructions that address limitations of ordinary persistent homology.The 2-D modules H_i Rips(γ) are described as more robust to noise and more sensitive to density variation than 1-D modules H_i Rips(P).
- Motivation: For n > 1, indecomposable modules are extremely complicated, so generalized barcodes are generally too unwieldy to support a useful bottleneck distance.The paper also states that no good barcode definition as nice subsets of R^n exists, even if the invariant is incomplete.
- Contributions: The interleaving distance dI is defined directly on multidimensional persistence modules as a simple, barcode-free generalization of the bottleneck distance.Its intended role is to provide a stable distance that is also as sensitive as a stable metric can be in a suitable sense.
- Contributions: dI = dB on finite-dimensional 1-D persistence modules, establishing the isometry theorem.The result uses the algebraic stability inequality dI ≥ dB and proves the reverse inequality.
- Contributions: The paper characterizes ε-interleavings through presentations differing by small shifts in generator and relation grades, then proves universality and closure results for dI.Over prime fields, any pseudometric with the same stability property satisfies d ≤ dI; for finitely presented modules, dI is a metric on isomorphism classes.
2 Preliminaries
This section develops the algebraic framework for multidimensional persistence modules and defines interleavings and the interleaving distance. It also illustrates how the distance behaves, including its pseudometric nature and examples involving interval modules.
- Multidimensional persistence modules: P_n is a monoid-ring analogue of a polynomial ring whose exponents range over [0,∞)^n.Its monomials encode graded transitions in multidimensional modules.
- Multidimensional persistence modules: An n-dimensional persistence module is a functor from the poset category R^n to vector spaces, equivalently an n-graded module over P_n.The equivalence permits both categorical and module-theoretic treatments.
- Basic constructions: An interval n-module C(I) assigns the field k on grades in I and zero elsewhere, with identity transition maps within I.The construction uses the interval structure of I.
- Interleavings and distance: The interleaving distance d_I is the infimum of ε for which two modules are ε-interleaved, where interleavings use morphisms in both directions into ε-shifted modules.The diagonal shift is by the vector whose components are all ε.
- Interleavings and distance: d_I is a pseudometric rather than a metric: nonisomorphic modules can have distance zero.A module supported only at grade 0 and the trivial module are ε-interleaved for every ε > 0.
- Interleavings and distance: For an interval I and the trivial module N, d_I(C(I),N) equals the width w(I); for the stated interval I2, the distance is 1.The width is defined using the largest diagonal span contained in I.
3 The Isometry Theorem
The section proves the isometry theorem for pointwise finite-dimensional 1-modules: ε-interleavings are equivalent to ε-matchings of barcodes, yielding equality between interleaving and bottleneck distances.
- Barcode decomposition: Every pointwise finite-dimensional 1-module has a unique barcode indexing its interval-module decomposition.This structure theorem supplies the barcode representation used throughout the section.
- Bottleneck distance: An ε-matching is a bijection between selected barcode intervals that includes all intervals surviving a 2ε test and pairs mutually ε-close intervals.The bottleneck distance is the infimum of ε admitting such a matching.
- Technical convention: The sharper matching convention is sensitive to interval endpoint openness, while producing the same bottleneck distance as the weaker convention.Its advantage is allowing a sharp form of the isometry theorem.
- Algebraic stability: An ε-interleaving morphism between p.f.d. 1-modules induces an ε-matching between their barcodes, so d_B(M,N) ≤ d_I(M,N).This is the algebraic stability theorem in its sharp formulation.
- The isometry theorem: Consequently, the interleaving and bottleneck distances coincide on p.f.d. 1-modules: d_I(M,N) = d_B(M,N).The equality is obtained by combining algebraic stability with the converse implication.
- The isometry theorem: The isometry theorem states that p.f.d. 1-modules are ε-interleaved if and only if their barcodes admit an ε-matching.The converse constructs interleaving morphisms from matched interval summands and trivializes unmatched summands.
4 Characterization of the ϵ-Interleaving Relation
This section characterizes multidimensional ε-interleavings algebraically through presentations whose generator and relation grades differ by ε-shifts. The characterization also applies to finitely presented modules with finite presentations.
- Characterization theorem: The characterization theorem says that two n-modules are ε-interleaved exactly when they admit presentations related by ε-shifts of generators and relations.This makes their algebraic similarity explicit.
- Consequences: The characterization is the key step toward the paper’s universality result and also yields a corresponding characterization of d_I.The proof additionally provides an explicit construction of the relevant presentations.
- Free modules and lifts: Free n-modules are constructed from graded generator sets, and free covers provide surjections used to lift morphisms between n-modules.Lifts exist for every morphism and are unique up to an image contained in the target cover’s kernel.
- Presentations: An n-module presentation has the form ⟨W|Y⟩, where W is an n-graded generator set and Y is a homogeneous relation set.The module is the quotient fr[W]/⟨Y⟩.
- Finite presentability: For finitely presented M and N, the sets of generators and relations in the characterization can all be chosen finite.Thus the characterization preserves finite presentability in its presentation data.
- Proof strategy: The proof lifts interleaving morphisms to free covers, combines the resulting relations, and constructs presentations P_M and P_N for the original modules.The constructed relation sets lie in shifted free modules, enabling the required ε-shift comparison.
5 Universality of the Interleaving and Bottleneck Distances
This section establishes stability and universality properties for the multidimensional interleaving distance, alongside a bottleneck-distance analogue. It also develops geometric lifts of interleavings and proves the one-dimensional isometry theorem.
- Stability of the Interleaving Distance: The interleaving distance dI is stable with respect to multidimensional persistent homology.Theorem 5.3 states stability, generalizing the corresponding one-dimensional bottleneck-distance result.
- Universality of the Interleaving Distance: For prime fields and i ≥1, dI is i-universal; consequently, over prime fields, dI is universal.Any other i-stable metric is bounded above by dI, and the same holds for any other stable metric in the universal formulation.
- Lifts of Interleavings to Functions: Interleavings of n-modules over prime fields lift to pairs of functions on a CW-complex with matching homology modules and d∞ equal to the interleaving parameter.This geometric lifting proposition is the key step used to prove universality.
- Universality of the Bottleneck Distance: For arbitrary fields and i ≥0, the bottleneck distance dB is i-universal.The result is obtained through geometric lifts for p.f.d. 1-modules, with d∞ at most ϵ + δ.
6 The Closure Theorem
The closure theorem shows that finitely presented multidimensional persistence modules attain their interleaving distance: distance ϵ implies an actual ϵ-interleaving. Therefore, dI becomes a metric on their isomorphism classes.
- The Closure Theorem: If finitely presented n-modules M and N satisfy dI(M, N) = ϵ, then they are ϵ-interleaved.This is the Closure Theorem.
- Consequences: dI restricts to a metric on isomorphism classes of finitely presented n-modules.The closure result supplies attainment of the infimum needed to establish this restriction.
- One-Dimensional Case: In one dimension, the closure theorem follows readily from the isometry theorem and finite barcodes of finitely presented persistence modules.The one-dimensional argument uses intervals of the form [s, t), with t possibly infinite.
- Proof Strategy: The proof fixes finite presentation grades and uses local transition-map isomorphisms near generator and relation grades.The finite sets of presentation grades determine the required δ and enable tightening an (ϵ + δ)-interleaving to an ϵ-interleaving.
- Proof Strategy: The tightening argument assumes an (ϵ + δ)-interleaving together with specified transition-map isomorphisms at grades from both presentations.Under these conditions, the constructed morphisms satisfy the interleaving identities at ϵ.
7 Discussion
The discussion identifies computation and broader universality questions as open directions. It also records conjectural extensions beyond prime fields, the current stability formulation, and other persistence settings.
- Computation: Computing or approximating dI remains an open and potentially significant question for applications.The paper presents dI as well behaved but does not settle its computational tractability.
- Universality Questions: The authors conjecture that dI is i-universal for arbitrary fields and i ≥0, beyond the proved prime-field, i ≥1 case.This is stated as Conjecture 5.7.
- Universality Questions: It remains open whether dI is universal under a Gromov–Hausdorff-based stability definition.The question concerns 1-modules arising from persistent homology of Rips constructions.
- Generalizations: The paper asks whether analogous universality results can be obtained for more general persistent homology modules, including levelset zig-zag persistence.It also asks for an algebraic bottleneck-distance analogue for zig-zag persistence and broader commutative quiver representations.