{{Short description|Measure of distance between persistence modules}} thumb|400x400px|A 1-interleaving between two <math>\mathbb Z</math>-indexed persistence modules M and N, represented as a diagram of vector spaces and linear maps between them. 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.<ref>{{Cite book |last1=Chazal |first1=Frédéric |last2=Cohen-Steiner |first2=David |last3=Glisse |first3=Marc |last4=Guibas |first4=Leonidas J. |last5=Oudot |first5=Steve Y. |title=Proceedings of the twenty-fifth annual symposium on Computational geometry |chapter=Proximity of persistence modules and their diagrams |date=2009-06-08 |chapter-url=https://doi.org/10.1145/1542362.1542407 |series=SCG '09 |location=New York, NY, USA |publisher=Association for Computing Machinery |pages=237–246 |doi=10.1145/1542362.1542407 |isbn=978-1-60558-501-7|s2cid=840484 |url=https://inria.hal.science/hal-02292996 }}</ref> since then, it and its generalizations have been a central consideration in the study of applied algebraic topology and topological data analysis.<ref>{{Cite arXiv |last1=Nelson |first1=Bradley J. |last2=Luo |first2=Yuan |date=2022-01-31 |title=Topology-Preserving Dimensionality Reduction via Interleaving Optimization |class=cs.LG |eprint=2201.13012}}</ref><ref>{{Cite web |title=Interleaving Distance between Merge Trees « Publications « Dmitriy Morozov |url=https://mrzv.org/publications/interleaving-distance-merge-trees/ |access-date=2023-04-07 |website=mrzv.org}}</ref><ref>{{Cite arXiv |last1=Meehan |first1=Killian |last2=Meyer |first2=David |date=2017-10-29 |title=Interleaving Distance as a Limit |class=math.AT |eprint=1710.11489}}</ref><ref>{{Citation |last1=Munch |first1=Elizabeth |title=The ℓ ∞-Cophenetic Metric for Phylogenetic Trees As an Interleaving Distance |date=2019 |url=http://link.springer.com/10.1007/978-3-030-11566-1_5 |work=Research in Data Science |volume=17 |pages=109–127 |editor-last=Gasparovic |editor-first=Ellen |access-date=2023-04-07 |place=Cham |publisher=Springer International Publishing |language=en |doi=10.1007/978-3-030-11566-1_5 |isbn=978-3-030-11565-4 |last2=Stefanou |first2=Anastasios |s2cid=4708500 |editor2-last=Domeniconi |editor2-first=Carlotta|url-access=subscription }}</ref><ref>{{Cite arXiv |last1=de Silva |first1=Vin |last2=Munch |first2=Elizabeth |last3=Stefanou |first3=Anastasios |date=2018-05-30 |title=Theory of interleavings on categories with a flow |class=math.CT |eprint=1706.04095}}</ref>

== Definition == A ''persistence module'' <math>\mathbb V</math> is a collection <math>(V_t \mid t \in \mathbb R)</math> of vector spaces indexed over the real line, along with a collection <math>(v^s_t : V_s \to V_t \mid s\leq t)</math> of linear maps such that <math>v^t_t</math> is always an isomorphism, and the relation <math>v^s_t \circ v^r_s = v^r_t</math> is satisfied for every <math>r\leq s \leq t</math>. The case of <math>\mathbb R</math> indexing is presented here for simplicity, though the interleaving distance can be readily adapted to more general settings, including multi-dimensional persistence modules.<ref>{{Cite journal |last=Lesnick |first=Michael |date=2015-06-01 |title=The Theory of the Interleaving Distance on Multidimensional Persistence Modules |url=https://doi.org/10.1007/s10208-015-9255-y |journal=Foundations of Computational Mathematics |language=en |volume=15 |issue=3 |pages=613–650 |doi=10.1007/s10208-015-9255-y |arxiv=1106.5305 |s2cid=254158297 |issn=1615-3383}}</ref>

Let <math>\mathbb U</math> and <math>\mathbb V</math> be persistence modules. Then for any <math>\delta \in \mathbb R</math>, a ''<math>\delta</math>-shift'' is a collection <math>(\phi_t : U_t \to V_{t+\delta} \mid t \in \mathbb R)</math> of linear maps between the persistence modules that commute with the internal maps of <math>\mathbb U</math> and <math>\mathbb V</math>.

The persistence modules <math>\mathbb U</math> and <math>\mathbb V</math> are said to be <math>\delta</math>-interleaved if there are <math>\delta</math>-shifts <math>\phi_t: U_t \to V_{t+ \delta}</math> and <math>\psi_t: V_t \to U_{t+ \delta}</math> such that the following diagrams commute for all <math>s \leq t</math>. center|frameless|300x300px It follows from the definition that if <math>\mathbb U</math> and <math>\mathbb V</math> are <math>\delta</math>-interleaved for some <math>\delta</math>, then they are also <math>(\delta + \varepsilon)</math>-interleaved for any positive <math>\varepsilon</math>. 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 <math>\mathbb U</math> and <math>\mathbb V</math> is defined as <math>d_I (\mathbb U, \mathbb V) = \inf \{\delta \mid \mathbb U \text{ and } \mathbb V \text{ are } \delta\text{-interleaved}\}</math>.<ref name=":0">{{Cite book |last1=Chazal |first1=Frédéric |url=http://link.springer.com/10.1007/978-3-319-42545-0 |title=The Structure and Stability of Persistence Modules |last2=de Silva |first2=Vin |last3=Glisse |first3=Marc |last4=Oudot |first4=Steve |date=2016 |publisher=Springer International Publishing |isbn=978-3-319-42543-6 |series=SpringerBriefs in Mathematics |location=Cham |pages=67–83 |doi=10.1007/978-3-319-42545-0|arxiv=1207.3674 |s2cid=2460562 }}</ref>

== Properties ==

=== Metric properties === It can be shown that the interleaving distance satisfies the triangle inequality. Namely, given three persistence modules <math>\mathbb U</math>, <math>\mathbb V</math>, and <math>\mathbb W</math>, the inequality <math>d_I (\mathbb U, \mathbb W) \leq d_I (\mathbb U, \mathbb V) + d_I (\mathbb V, \mathbb W)</math> is satisfied.<ref name=":0" />

On the other hand, there are examples of persistence modules that are not isomorphic but that have interleaving distance zero. Furthermore, if no suitable <math>\delta</math> 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.<ref>{{Cite thesis |last=Scoccola |first=Luis |date=2020-07-15 |title=Locally Persistent Categories And Metric Properties Of Interleaving Distances |url=https://ir.lib.uwo.ca/etd/7119 |journal=Electronic Thesis and Dissertation Repository}}</ref>

=== 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.<ref>{{Cite arXiv |last1=Bjerkevik |first1=Håvard Bakke |last2=Botnan |first2=Magnus Bakke |last3=Kerber |first3=Michael |date=2019-10-09 |title=Computing the interleaving distance is NP-hard |class=cs.CG |eprint=1811.09165}}</ref><ref>{{Cite arXiv |last1=Bjerkevik |first1=Håvard Bakke |last2=Botnan |first2=Magnus Bakke |date=2018-04-30 |title=Computational Complexity of the Interleaving Distance |class=cs.CG |eprint=1712.04281}}</ref>

== References ==

<references /> Category:Computational topology Category:Data analysis