[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

The Theory of the Interleaving Distance on Multidimensional Persistence Modules

  • Published:
Foundations of Computational Mathematics Aims and scope Submit manuscript

Abstract

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1

Similar content being viewed by others

References

  1. Aaron Adcock, Daniel Rubin, and Gunnar Carlsson. Classification of hepatic lesions using the matching metric. Computer Vision and Image Understanding, 121:36–42, 2014.

    Article  Google Scholar 

  2. 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.

    MATH  MathSciNet  Google Scholar 

  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.

  4. 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.

    Article  MathSciNet  Google Scholar 

  5. A. Blumberg and M. Lesnick. Universality of the homotopy interleaving distance. In preparation, 2015.

  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.

  7. P. Bubenik and J. Scott. Categorification of persistent homology. Discrete & Computational Geometry, 51(3):600–627, 2014.

    Article  MATH  MathSciNet  Google Scholar 

  8. 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.

    Article  MATH  MathSciNet  Google Scholar 

  9. G. Carlsson. Topological pattern recognition for point cloud data. Acta Numerica, 23:289–368, May 2014.

    Article  MathSciNet  Google Scholar 

  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.

  11. 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.

    Article  Google Scholar 

  12. G. Carlsson and F. Mémoli. Multiparameter hierarchical clustering methods. Classification as a Tool for Research, pages 63–70, 2010.

  13. G. Carlsson and A. Zomorodian. The theory of multidimensional persistence. Discrete and Computational Geometry, 42(1):71–93, 2009.

    Article  MATH  MathSciNet  Google Scholar 

  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.

  15. 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.

    Article  MATH  MathSciNet  Google Scholar 

  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.

  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.

  19. F. Chazal, W. Crawley-Boevey, and V. de Silva. The observable structure of persistence modules. arXiv preprint arXiv:1405.5644, 2014.

  20. F. Chazal, V. de Silva, M. Glisse, and S. Oudot. The structure and stability of persistence modules. arXiv preprint arXiv:1207.3674, 2012.

  21. F. Chazal, L. Guibas, S. Oudot, and P. Skraba. Persistence-based clustering in riemannian manifolds. Journal of the ACM (JACM), 60(6):41, 2013.

    Article  MathSciNet  Google Scholar 

  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.

  23. D. Cohen-Steiner, H. Edelsbrunner, and J. Harer. Stability of persistence diagrams. Discrete and Computational Geometry, 37(1):103–120, 2007.

    Article  MATH  MathSciNet  Google Scholar 

  24. 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.

    Article  MATH  MathSciNet  Google Scholar 

  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.

  26. W. Crawley-Boevey. Decomposition of pointwise finite-dimensional persistence modules. arXiv preprint arXiv:1210.0819, 2012.

  27. J. Curry. Sheaves, cosheaves and applications. Ph.D. Dissertation, University of Pennsylvania, 2014.

  28. 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.

    Article  MATH  MathSciNet  Google Scholar 

  29. Vin de Silva, Elizabeth Munch, and Amit Patel. Categorified reeb graphs. arXiv preprint arXiv:1501.04147, 2015.

  30. H. Derksen and J. Weyman. Quiver representations. Notices of the AMS, 52(2):200–206, 2005.

    MATH  MathSciNet  Google Scholar 

  31. D.S. Dummit and R.M. Foote. Abstract algebra. Wiley, 1999.

  32. H. Edelsbrunner and J. Harer. Computational topology: an introduction. American Mathematical Society, 2010.

  33. D. Eisenbud. Commutative algebra with a view toward algebraic geometry. Springer, 1995.

    MATH  Google Scholar 

  34. P. Frosini. Stable comparison of multidimensional persistent homology groups with torsion. Acta Applicandae Mathematicae, pages 1–12, 2010.

  35. 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.

    MATH  MathSciNet  Google Scholar 

  36. Peter Gabriel. Unzerlegbare darstellungen i. Manuscripta Mathematica, 6(1):71–103, 1972.

    Article  MATH  MathSciNet  Google Scholar 

  37. A. Hatcher. Algebraic topology. Cambridge University Press, 2002.

    MATH  Google Scholar 

  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.

  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. D. Morozov, K. Beketayev, and G. Weber. Interleaving distance between merge trees. Discrete and Computational Geometry, 49:22–45, 2013.

    Article  MATH  MathSciNet  Google Scholar 

  44. 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.

    Article  MATH  Google Scholar 

  45. L. Wasserman. All of statistics: a concise course in statistical inference. Springer Verlag, 2004.

    Book  Google Scholar 

  46. Cary Webb. Decomposition of graded modules. Proceedings of the American Mathematical Society, 94(4):565–571, 1985.

    Article  MATH  MathSciNet  Google Scholar 

  47. A. Zomorodian and G. Carlsson. Computing persistent homology. Discrete and Computational Geometry, 33(2):249–274, 2005.

    Article  MATH  MathSciNet  Google Scholar 

Download references

Acknowledgments

The first version of this paper was written while I was a graduate student. Discussions with my Ph.D. adviser Gunnar Carlsson catalyzed the research presented here in several ways. In addition, Gunnar served as a patient and helpful sounding board for the ideas of this paper. I thank him for his support and guidance. Thanks to Henry Adams, Peter Bubenik, Patrizio Frosini, Peter Landweber, Dmitriy Morozov, and the anonymous referees for useful corrections and helpful feedback on this work. Parts of the exposition in Sects. 1.1 and 3 benefited from edits done jointly with Ulrich Bauer on closely related material in [3]. The main result of William Crawley-Boevey’s paper [26] plays an important role in the present version of this work. I thank Bill for writing his paper and both Bill and Vin de Silva for enlightening discussions about structure theorems for \({\mathbb {R}}\)-graded persistence modules. Thanks to Stanford University, the Technion, the Institute for Advanced Study, and the Institute for Mathematics and its Applications for their support hospitality during the writing and revision of this paper. This work was supported by ONR grant N00014-09-1-0783 and NSF grant DMS-1128155. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author and do not necessarily reflect the views of the National Science Foundation.

Author information

Authors and Affiliations

  1. Institute for Mathematics and its Applications, Minneapolis, MN, USA

    Michael Lesnick

Authors
  1. Michael Lesnick
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Michael Lesnick.

Additional information

Communicated by Michael Todd.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Lesnick, M. The Theory of the Interleaving Distance on Multidimensional Persistence Modules. Found Comput Math 15, 613–650 (2015). https://doi.org/10.1007/s10208-015-9255-y

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10208-015-9255-y

Keywords

Mathematics Subject Classification

Search

Navigation