×

zbMATH — the first resource for mathematics

The theory of the interleaving distance on multidimensional persistence modules. (English) Zbl 1335.55006
Roughly speaking, one-dimensional persistent topology is about filtered spaces, indexed by real numbers [H. Edelsbrunner and J. Harer, Contemp. Math. 453, 257–282 (2008; Zbl 1145.55007)]. One of the main tools is the persistence module, a diagram of vector spaces also indexed by real numbers, usually attached to a filtration through homology [A. Zomorodian and G. Carlsson, Discrete Comput. Geom. 33, No. 2, 249–274 (2005; Zbl 1069.55003)]. A persistence module (PM) \(M\), in turn, can be dealt with through a barcode \(\mathcal B_M\), a collection of intervals which characterizes \(M\) if its vector spaces are finite dimensional [G. Carlsson et al., Int. J. Shape Model. 11, No. 2, 149–187 (2005; Zbl 1092.68688)].
Essentially, two PMs \(M\) and \(N\) are \(\varepsilon\)-interleaved if they correspond up to \(\varepsilon\)-shifts; if \(0 \leq \varepsilon \leq \varepsilon'\) and \(M, N\) are \(\varepsilon\)-interleaved, then they are also \(\varepsilon'\)-interleaved. The interleaving distance \(d_I\) between \(M\) and \(N\) is the infimum of such \(\varepsilon\); \(d_I\) is an extended pseudometric [F. Chazal et al., “Proximity of persistence modules and their diagrams”, in: Proceedings of the 25th annual symposium on computational geometry, SCG 2009, Aarhus, Denmark, June 8–10, 2009. New York, NY: Association for Computing Machinery (ACM). xii, 413 p. (2009; Zbl 1271.68008)].
The present paper extends the theory of \(d_I\) to the case of multidimensional indexing of the PMs and of the filtrations [G. Carlsson and A. Zomorodian, Discrete Comput. Geom. 42, No. 1, 71–93 (2009; Zbl 1187.55004)], where the PMs have a more tricky structure. The first relevant result is, however, in the 1D case: it is a new proof of the isometry theorem, the equality between \(d_I(M, N)\) and the bottleneck distance of the corresponding barcodes.
The second important result is a characterization of \(\varepsilon\)-interleaving of PMs with nD indexing: it reflects upon \(\varepsilon\)-shifts of generators and relators of the modules.
The universality result is a corollary of the characterization; it says that for multidimensional PMs over a prime field \(d_I\) is stable and optimal; it generalizes a result of [M. d’Amico et al., Acta Appl. Math. 109, No. 2, 527–554 (2010; Zbl 1198.68224)] and makes use of the natural pseudodistance between spaces endowed with filtering functions, defined in the nD case in [P. Frosini and M. Mulazzani, Bull. Belg. Math. Soc. - Simon Stevin 6, No. 3, 455–464 (1999; Zbl 0937.55010)]. It has a beautiful topological proof and is conjectured to hold for any field.
The fourth main result of the paper asserts that, also in the nD case, the set of real numbers \(\varepsilon\) for which two finitely presented PMs are \(\varepsilon\)-interleaved is closed.
Priorities and contributions are duly acknowledged. Well-chosen, simple examples clarify the concepts. The extensive use of the categorical setting requires an attentive reading but grants indisputable and general results.

MSC:
55N99 Homology and cohomology theories in algebraic topology
54E35 Metric spaces, metrizability
68R99 Discrete mathematics in relation to computer science
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] Adcock, Aaron; Rubin, Daniel; Carlsson, Gunnar, Classification of hepatic lesions using the matching metric, Computer Vision and Image Understanding, 121, 36-42, (2014)
[2] Atiyah, Michael F, On the Krull-Schmidt theorem with application to sheaves, Bulletin de la Société Mathématique de France, 84, 307-317, (1956) · Zbl 0072.18101
[3] U. Bauer and M. Lesnick. Induced matchings of barcodes and the algebraic stability of persistence. In Proceedings of the 2014 Annual Symposium on Computational Geometry, page 355. ACM, 2014. Extended version to appear in Discrete and Computational Geometry. · Zbl 1405.68398
[4] Biasotti, S; Cerri, A; Frosini, P; Giorgi, D; Landi, C, Multidimensional size functions for shape comparison, Journal of Mathematical Imaging and Vision, 32, 161-179, (2008)
[5] A. Blumberg and M. Lesnick. Universality of the homotopy interleaving distance. In preparation, 2015. · Zbl 1335.55006
[6] P. Bubenik, V. de Silva, and J. Scott. Metrics for generalized persistence modules. Foundations of Computational Mathematics, 2014. doi:10.1007/s10208-014-9229-5. · Zbl 1345.55006
[7] Bubenik, P; Scott, J, Categorification of persistent homology, Discrete & Computational Geometry, 51, 600-627, (2014) · Zbl 1295.55005
[8] Carlsson, E; Carlsson, G; Silva, V; Fortune, S, An algebraic topological method for feature identification, International Journal of Computational Geometry and Applications, 16, 291-314, (2006) · Zbl 1098.65024
[9] Carlsson, G, Topological pattern recognition for point cloud data, Acta Numerica, 23, 289-368, (2014) · Zbl 1398.68615
[10] G. Carlsson, V. de Silva, and D. Morozov. Zigzag persistent homology and real-valued functions. In Proceedings of the 25th annual symposium on Computational geometry, pages 247-256. ACM, 2009. · Zbl 1380.68385
[11] Carlsson, G; Ishkhanov, T; Silva, V; Zomorodian, A, On the local behavior of spaces of natural images, International Journal of Computer Vision, 76, 1-12, (2008)
[12] G. Carlsson and F. Mémoli. Multiparameter hierarchical clustering methods. Classification as a Tool for Research, pages 63-70, 2010. · Zbl 1187.55004
[13] Carlsson, G; Zomorodian, A, The theory of multidimensional persistence, Discrete and Computational Geometry, 42, 71-93, (2009) · Zbl 1187.55004
[14] G. Carlsson, A. Zomorodian, A. Collins, and L. Guibas. Persistence barcodes for shapes. In Proceedings of the 2004 Eurographics/ACM SIGGRAPH symposium on Geometry processing, pages 124-135. ACM, 2004. · Zbl 1092.68688
[15] Cerri, Andrea; Fabio, Barbara; Ferri, Massimo; Frosini, Patrizio; Landi, Claudia, Betti numbers in multidimensional persistent homology are stable functions, Mathematical Methods in the Applied Sciences, 36, 1543-1557, (2013) · Zbl 1278.55012
[16] F. Chazal, D. Cohen-Steiner, M. Glisse, L.J. Guibas, and S.Y. Oudot. Proximity of persistence modules and their diagrams. In Proceedings of the 25th annual symposium on Computational geometry, pages 237-246. ACM, 2009. · Zbl 1380.68387
[17] F. Chazal, D. Cohen-Steiner, L.J. Guibas, F. Mémoli, and S.Y. Oudot. Gromov-Hausdorff stable signatures for shapes using persistence. In Proceedings of the Symposium on Geometry Processing, pages 1393-1403. Eurographics Association, 2009.
[18] F. Chazal, D. Cohen-Steiner, and Q. Mérigot. Geometric inference for probability measures. Foundations of Computational Mathematics, pages 1-19, 2011. · Zbl 1230.62074
[19] F. Chazal, W. Crawley-Boevey, and V. de Silva. The observable structure of persistence modules. arXiv preprint arXiv:1405.5644, 2014. · Zbl 1377.55015
[20] F. Chazal, V. de Silva, M. Glisse, and S. Oudot. The structure and stability of persistence modules. arXiv preprint arXiv:1207.3674, 2012. · Zbl 1362.55002
[21] Chazal, F; Guibas, L; Oudot, S; Skraba, P, Persistence-based clustering in Riemannian manifolds, Journal of the ACM (JACM), 60, 41, (2013) · Zbl 1281.68176
[22] F. Chazal, L.J. Guibas, S.Y. Oudot, and P. Skraba. Analysis of scalar fields over point cloud data. In Proceedings of the twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1021-1030. Society for Industrial and Applied Mathematics, 2009. · Zbl 1230.94002
[23] Cohen-Steiner, D; Edelsbrunner, H; Harer, J, Stability of persistence diagrams, Discrete and Computational Geometry, 37, 103-120, (2007) · Zbl 1117.54027
[24] Cohen-Steiner, D; Edelsbrunner, H; Harer, J; Mileyko, Y, Lipschitz functions have \(L_p\)-stable persistence, Foundations of Computational Mathematics, 10, 127-139, (2010) · Zbl 1192.55007
[25] D. Cohen-Steiner, H. Edelsbrunner, and D. Morozov. Vines and vineyards by updating persistence in linear time. In Proceedings of the twenty-second annual symposium on Computational geometry, pages 119-126. ACM, 2006. · Zbl 1153.68388
[26] W. Crawley-Boevey. Decomposition of pointwise finite-dimensional persistence modules. arXiv preprint arXiv:1210.0819, 2012. · Zbl 1345.16015
[27] J. Curry. Sheaves, cosheaves and applications. Ph.D. Dissertation, University of Pennsylvania, 2014. · Zbl 0072.18101
[28] d’Amico, M; Frosini, P; Landi, C, Natural pseudo-distance and optimal matching between reduced size functions, Acta applicandae mathematicae, 109, 527-554, (2010) · Zbl 1198.68224
[29] Vin de Silva, Elizabeth Munch, and Amit Patel. Categorified reeb graphs. arXiv preprintarXiv:1501.04147, 2015. · Zbl 1350.68271
[30] Derksen, H; Weyman, J, Quiver representations, Notices of the AMS, 52, 200-206, (2005) · Zbl 1143.16300
[31] D.S. Dummit and R.M. Foote. Abstract algebra. Wiley, 1999. · Zbl 0943.00001
[32] H. Edelsbrunner and J. Harer. Computational topology: an introduction. American Mathematical Society, 2010. · Zbl 1193.55001
[33] D. Eisenbud. Commutative algebra with a view toward algebraic geometry. Springer, 1995. · Zbl 0819.13001
[34] P. Frosini. Stable comparison of multidimensional persistent homology groups with torsion. Acta Applicandae Mathematicae, pages 1-12, 2010.
[35] Frosini, P; Mulazzani, M, Size homotopy groups for computation of natural size distances, Bulletin of the Belgian Mathematical Society Simon Stevin, 6, 455-464, (1999) · Zbl 0937.55010
[36] Gabriel, Peter, Unzerlegbare darstellungen i, Manuscripta Mathematica, 6, 71-103, (1972) · Zbl 0232.08001
[37] A. Hatcher. Algebraic topology. Cambridge University Press, 2002. · Zbl 1044.55001
[38] T. Ishkhanov. A topological method for shape comparison. In Computer Vision and Pattern Recognition Workshops, 2008. CVPRW’08. IEEE Computer Society Conference on, pages 1-4. IEEE, 2008. · Zbl 0232.08001
[39] S. Lang. Algebra, revised third edition. Graduate Texts in Mathematics, 2002.
[40] M. Lesnick. The optimality of the interleaving distance on multidimensional persistence modules. Arxiv preprint arXiv:1106.5305v2, 2011.
[41] M. Lesnick. Multidimensional interleavings and applications to topological inference. Ph.D. Dissertation, Stanford University, 2012.
[42] C. Li, M. Ovsjanikov, and F. Chazal. Persistence-based structural recognition. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 1995-2002, 2013.
[43] Morozov, D; Beketayev, K; Weber, G, Interleaving distance between merge trees, Discrete and Computational Geometry, 49, 22-45, (2013) · Zbl 1272.68414
[44] Verri, A; Uras, C; Frosini, P; Ferri, M, On the use of size functions for shape analysis, Biological Cybernetics, 70, 99-107, (1993) · Zbl 0789.92030
[45] L. Wasserman. All of statistics: a concise course in statistical inference. Springer Verlag, 2004. · Zbl 1053.62005
[46] Webb, Cary, Decomposition of graded modules, Proceedings of the American Mathematical Society, 94, 565-571, (1985) · Zbl 0581.13008
[47] Zomorodian, A; Carlsson, G, Computing persistent homology, Discrete and Computational Geometry, 33, 249-274, (2005) · Zbl 1069.55003
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.