The Theory of the Interleaving Distance on Multidimensional Persistence Modules
Tóm tắt
In 2009, Chazal et al. introduced
$$\epsilon $$
-interleavings of persistence modules.
$$\epsilon $$
-interleavings induce a pseudometric
$$d_\mathrm{I}$$
on (isomorphism classes of) persistence modules, the interleaving distance. The definitions of
$$\epsilon $$
-interleavings and
$$d_\mathrm{I}$$
generalize readily to multidimensional persistence modules. In this paper, we develop the theory of multidimensional interleavings, with a view toward applications to topological data analysis. We present four main results. First, we show that on 1-D persistence modules,
$$d_\mathrm{I}$$
is equal to the bottleneck distance
$$d_\mathrm{B}$$
. This result, which first appeared in an earlier preprint of this paper, has since appeared in several other places, and is now known as the isometry theorem. Second, we present a characterization of the
$$\epsilon $$
-interleaving relation on multidimensional persistence modules. This expresses transparently the sense in which two
$$\epsilon $$
-interleaved modules are algebraically similar. Third, using this characterization, we show that when we define our persistence modules over a prime field,
$$d_\mathrm{I}$$
satisfies a universality property. This universality result is the central result of the paper. It says that
$$d_\mathrm{I}$$
satisfies a stability property generalizing one which
$$d_\mathrm{B}$$
is known to satisfy, and that in addition, if
$$d$$
is any other pseudometric on multidimensional persistence modules satisfying the same stability property, then
$$d\le d_\mathrm{I}$$
. We also show that a variant of this universality result holds for
$$d_\mathrm{B}$$
, over arbitrary fields. Finally, we show that
$$d_\mathrm{I}$$
restricts to a metric on isomorphism classes of finitely presented multidimensional persistence modules.
Tài liệu tham khảo
Aaron Adcock, Daniel Rubin, and Gunnar Carlsson. Classification of hepatic lesions using the matching metric. Computer Vision and Image Understanding, 121:36–42, 2014.
Michael F Atiyah. On the krull-schmidt theorem with application to sheaves. Bulletin de la Société Mathématique de France, 84:307–317, 1956.
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.
S. Biasotti, A. Cerri, P. Frosini, D. Giorgi, and C. Landi. Multidimensional size functions for shape comparison. Journal of Mathematical Imaging and Vision, 32(2):161–179, 2008.
A. Blumberg and M. Lesnick. Universality of the homotopy interleaving distance. In preparation, 2015.
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.
P. Bubenik and J. Scott. Categorification of persistent homology. Discrete & Computational Geometry, 51(3):600–627, 2014.
E. Carlsson, G. Carlsson, V. de Silva, and S. Fortune. An algebraic topological method for feature identification. International Journal of Computational Geometry and Applications, 16(4):291–314, 2006.
G. Carlsson. Topological pattern recognition for point cloud data. Acta Numerica, 23:289–368, May 2014.
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.
G. Carlsson, T. Ishkhanov, V. de Silva, and A. Zomorodian. On the local behavior of spaces of natural images. International Journal of Computer Vision, 76(1):1–12, 2008.
G. Carlsson and F. Mémoli. Multiparameter hierarchical clustering methods. Classification as a Tool for Research, pages 63–70, 2010.
G. Carlsson and A. Zomorodian. The theory of multidimensional persistence. Discrete and Computational Geometry, 42(1):71–93, 2009.
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.
Andrea Cerri, Barbara Di Fabio, Massimo Ferri, Patrizio Frosini, and Claudia Landi. Betti numbers in multidimensional persistent homology are stable functions. Mathematical Methods in the Applied Sciences, 36(12):1543–1557, 2013.
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.
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.
F. Chazal, D. Cohen-Steiner, and Q. Mérigot. Geometric inference for probability measures. Foundations of Computational Mathematics, pages 1–19, 2011.
F. Chazal, W. Crawley-Boevey, and V. de Silva. The observable structure of persistence modules. arXiv preprint arXiv:1405.5644, 2014.
F. Chazal, V. de Silva, M. Glisse, and S. Oudot. The structure and stability of persistence modules. arXiv preprint arXiv:1207.3674, 2012.
F. Chazal, L. Guibas, S. Oudot, and P. Skraba. Persistence-based clustering in riemannian manifolds. Journal of the ACM (JACM), 60(6):41, 2013.
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.
D. Cohen-Steiner, H. Edelsbrunner, and J. Harer. Stability of persistence diagrams. Discrete and Computational Geometry, 37(1):103–120, 2007.
D. Cohen-Steiner, H. Edelsbrunner, J. Harer, and Y. Mileyko. Lipschitz functions have \(L_p\)-stable persistence. Foundations of Computational Mathematics, 10(2):127–139, 2010.
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.
W. Crawley-Boevey. Decomposition of pointwise finite-dimensional persistence modules. arXiv preprint arXiv:1210.0819, 2012.
J. Curry. Sheaves, cosheaves and applications. Ph.D. Dissertation, University of Pennsylvania, 2014.
M. d’Amico, P. Frosini, and C. Landi. Natural pseudo-distance and optimal matching between reduced size functions. Acta applicandae mathematicae, 109(2):527–554, 2010.
Vin de Silva, Elizabeth Munch, and Amit Patel. Categorified reeb graphs. arXiv preprint arXiv:1501.04147, 2015.
H. Derksen and J. Weyman. Quiver representations. Notices of the AMS, 52(2):200–206, 2005.
D.S. Dummit and R.M. Foote. Abstract algebra. Wiley, 1999.
H. Edelsbrunner and J. Harer. Computational topology: an introduction. American Mathematical Society, 2010.
D. Eisenbud. Commutative algebra with a view toward algebraic geometry. Springer, 1995.
P. Frosini. Stable comparison of multidimensional persistent homology groups with torsion. Acta Applicandae Mathematicae, pages 1–12, 2010.
P. Frosini and M. Mulazzani. Size homotopy groups for computation of natural size distances. Bulletin of the Belgian Mathematical Society Simon Stevin, 6(3):455–464, 1999.
Peter Gabriel. Unzerlegbare darstellungen i. Manuscripta Mathematica, 6(1):71–103, 1972.
A. Hatcher. Algebraic topology. Cambridge University Press, 2002.
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.
S. Lang. Algebra, revised third edition. Graduate Texts in Mathematics, 2002.
M. Lesnick. The optimality of the interleaving distance on multidimensional persistence modules. Arxiv preprint arXiv:1106.5305v2, 2011.
M. Lesnick. Multidimensional interleavings and applications to topological inference. Ph.D. Dissertation, Stanford University, 2012.
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.
D. Morozov, K. Beketayev, and G. Weber. Interleaving distance between merge trees. Discrete and Computational Geometry, 49:22–45, 2013.
A. Verri, C. Uras, P. Frosini, and M. Ferri. On the use of size functions for shape analysis. Biological Cybernetics, 70(2):99–107, 1993.
L. Wasserman. All of statistics: a concise course in statistical inference. Springer Verlag, 2004.
Cary Webb. Decomposition of graded modules. Proceedings of the American Mathematical Society, 94(4):565–571, 1985.
A. Zomorodian and G. Carlsson. Computing persistent homology. Discrete and Computational Geometry, 33(2):249–274, 2005.