Measure of distance between persistence modules
In topological data analysis, the interleaving distance is a measure of similarity between persistence modules, a common object of study in topological data analysis and persistent homology. The interleaving distance was first introduced by Frédéric Chazal et al. in 2009. since then, it and its generalizations have been a central consideration in the study of applied algebraic topology and topological data analysis.
Definition.
A "persistence module" formula_1 is a collection formula_2 of vector spaces indexed over the real line, along with a collection formula_3 of linear maps such that formula_4 is always an isomorphism, and the relation formula_5 is satisfied for every formula_6. The case of formula_7 indexing is presented here for simplicity, though the interleaving distance can be readily adapted to more general settings, including multi-dimensional persistence modules.
Let formula_8 and formula_1 be persistence modules. Then for any formula_10, a "formula_11-shift" is a collection formula_12 of linear maps between the persistence modules that commute with the internal maps of formula_8 and formula_1.
The persistence modules formula_8 and formula_1 are said to be formula_11-interleaved if there are formula_11-shifts formula_19 and formula_20 such that the following diagrams commute for all formula_21.
It follows from the definition that if formula_8 and formula_1 are formula_11-interleaved for some formula_11, then they are also formula_26-interleaved for any positive formula_27. Therefore, in order to find the closest interleaving between the two modules, we must take the infimum across all possible interleavings.
The "interleaving distance" between two persistence modules formula_8 and formula_1 is defined as formula_30.
Properties.
Metric properties.
It can be shown that the interleaving distance satisfies the triangle inequality. Namely, given three persistence modules formula_8, formula_1, and formula_33, the inequality formula_34 is satisfied.
On the other hand, there are examples of persistence modules that are not isomorphic but that have interleaving distance zero. Furthermore, if no suitable formula_11 exists then two persistence modules are said to have infinite interleaving distance. These two properties make the interleaving distance an "extended pseudometric", which means non-identical objects are allowed to have distance zero, and objects are allowed to have infinite distance, but the other properties of a proper metric are satisfied.
Further metric properties of the interleaving distance and its variants were investigated by Luis Scoccola in 2020.
Computational complexity.
Computing the interleaving distance between two single-parameter persistence modules can be accomplished in polynomial time. On the other hand, it was shown in 2018 that computing the interleaving distance between two multi-dimensional persistence modules is NP-hard.