Misplaced Pages

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 ${\displaystyle \mathbb {V} }$ is a collection ${\displaystyle (V_{t}\mid t\in \mathbb {R} )}$ of vector spaces indexed over the real line, along with a collection ${\displaystyle (v_{t}^{s}:V_{s}\to V_{t}\mid s\leq t)}$ of linear maps such that ${\displaystyle v_{t}^{t}}$ is always an isomorphism, and the relation ${\displaystyle v_{t}^{s}\circ v_{s}^{r}=v_{t}^{r}}$ is satisfied for every ${\displaystyle r\leq s\leq t}$. The case of ${\displaystyle \mathbb {R} }$ indexing is presented here for simplicity, though the interleaving distance can be readily adapted to more general settings, including multi-dimensional persistence modules.

Let ${\displaystyle \mathbb {U} }$ and ${\displaystyle \mathbb {V} }$ be persistence modules. Then for any ${\displaystyle \delta \in \mathbb {R} }$, a ${\displaystyle \delta }$-shift is a collection ${\displaystyle (\phi _{t}:U_{t}\to V_{t+\delta }\mid t\in \mathbb {R} )}$ of linear maps between the persistence modules that commute with the internal maps of ${\displaystyle \mathbb {U} }$ and ${\displaystyle \mathbb {V} }$.

The persistence modules ${\displaystyle \mathbb {U} }$ and ${\displaystyle \mathbb {V} }$ are said to be ${\displaystyle \delta }$-interleaved if there are ${\displaystyle \delta }$-shifts ${\displaystyle \phi _{t}:U_{t}\to V_{t+\delta }}$ and ${\displaystyle \psi _{t}:V_{t}\to U_{t+\delta }}$ such that the following diagrams commute for all ${\displaystyle s\leq t}$.

It follows from the definition that if ${\displaystyle \mathbb {U} }$ and ${\displaystyle \mathbb {V} }$ are ${\displaystyle \delta }$-interleaved for some ${\displaystyle \delta }$, then they are also ${\displaystyle (\delta +\varepsilon )}$-interleaved for any positive ${\displaystyle \varepsilon }$. 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 ${\displaystyle \mathbb {U} }$ and ${\displaystyle \mathbb {V} }$ is defined as ${\displaystyle d_{I}(\mathbb {U} ,\mathbb {V} )=\inf\{\delta \mid \mathbb {U} {\text{ and }}\mathbb {V} {\text{ are }}\delta {\text{-interleaved}}\}}$.

Properties

Metric properties

It can be shown that the interleaving distance satisfies the triangle inequality. Namely, given three persistence modules ${\displaystyle \mathbb {U} }$, ${\displaystyle \mathbb {V} }$, and ${\displaystyle \mathbb {W} }$, the inequality ${\displaystyle d_{I}(\mathbb {U} ,\mathbb {W} )\leq d_{I}(\mathbb {U} ,\mathbb {V} )+d_{I}(\mathbb {V} ,\mathbb {W} )}$ 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 ${\displaystyle \delta }$ 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.

References

1. Chazal, Frédéric; Cohen-Steiner, David; Glisse, Marc; Guibas, Leonidas J.; Oudot, Steve Y. (2009-06-08). "Proximity of persistence modules and their diagrams". Proceedings of the twenty-fifth annual symposium on Computational geometry. SCG '09. New York, NY, USA: Association for Computing Machinery. pp. 237–246. doi:10.1145/1542362.1542407. ISBN 978-1-60558-501-7. S2CID 840484.
2. Nelson, Bradley J.; Luo, Yuan (2022-01-31). "Topology-Preserving Dimensionality Reduction via Interleaving Optimization". arXiv:2201.13012 .
3. "Interleaving Distance between Merge Trees « Publications « Dmitriy Morozov". mrzv.org. Retrieved 2023-04-07.
4. Meehan, Killian; Meyer, David (2017-10-29). "Interleaving Distance as a Limit". arXiv:1710.11489 .
5. Munch, Elizabeth; Stefanou, Anastasios (2019), Gasparovic, Ellen; Domeniconi, Carlotta (eds.), "The ℓ ∞-Cophenetic Metric for Phylogenetic Trees As an Interleaving Distance", Research in Data Science, vol. 17, Cham: Springer International Publishing, pp. 109–127, doi:10.1007/978-3-030-11566-1_5, ISBN 978-3-030-11565-4, S2CID 4708500, retrieved 2023-04-07
6. de Silva, Vin; Munch, Elizabeth; Stefanou, Anastasios (2018-05-30). "Theory of interleavings on categories with a flow". arXiv:1706.04095 .
7. Lesnick, Michael (2015-06-01). "The Theory of the Interleaving Distance on Multidimensional Persistence Modules". Foundations of Computational Mathematics. 15 (3): 613–650. arXiv:1106.5305. doi:10.1007/s10208-015-9255-y. ISSN 1615-3383. S2CID 254158297.
8. ^ Chazal, Frédéric; de Silva, Vin; Glisse, Marc; Oudot, Steve (2016). The Structure and Stability of Persistence Modules. SpringerBriefs in Mathematics. Cham: Springer International Publishing. pp. 67–83. doi:10.1007/978-3-319-42545-0. ISBN 978-3-319-42543-6. S2CID 2460562.
9. Scoccola, Luis (2020-07-15). "Locally Persistent Categories And Metric Properties Of Interleaving Distances". Electronic Thesis and Dissertation Repository.
10. Bjerkevik, Håvard Bakke; Botnan, Magnus Bakke; Kerber, Michael (2019-10-09). "Computing the interleaving distance is NP-hard". arXiv:1811.09165 .
11. Bjerkevik, Håvard Bakke; Botnan, Magnus Bakke (2018-04-30). "Computational Complexity of the Interleaving Distance". arXiv:1712.04281 .

• Computational topology
• Data analysis