Open Collections

Computing Interleaving and Bottleneck Distance for 2-D Interval Decomposable Modules

Banff International Research Station for Mathematical Innovation and Discovery

Computation of the interleaving distance between persistence modules is a central task in topological data analysis. For $1$-D persistence modules, thanks to the isometry theorem, this can be done by computing the bottleneck distance with known efficient algorithms. The question is open for most $n$-D persistence modules, $n>1$, because of the well recognized complications of the indecomposables. Here, we consider a reasonably complicated class called {\em $2$-D interval decomposable} modules whose indecomposables may have a description of non-constant complexity. We present a polynomial time algorithm to compute the interleaving distance between two such indecomposables. This leads to a polynomial time algorithm for computing the bottleneck distance between two $2$-D interval decomposable modules, which bounds their interleaving distance from above. We give another algorithm to compute a new distance called {\em dimension distance} that bounds it from below.

Mathematics; Algebraic topology; Statistics

video/mp4

Author affiliation: Ohio State University

2019-03-24

Attribution-NonCommercial-NoDerivatives 4.0 International

http://hdl.handle.net/2429/69144

Unreviewed

http://creativecommons.org/licenses/by-nc-nd/4.0/