Universality of the homotopy interleaving distance

Blumberg, Andrew; Lesnick, Michael

doi:10.1090/tran/8738

Universality of the homotopy interleaving distance
HTML articles powered by AMS MathViewer

by Andrew J. Blumberg and Michael Lesnick

Trans. Amer. Math. Soc. 376 (2023), 8269-8307

DOI: https://doi.org/10.1090/tran/8738

Published electronically: September 14, 2023

PDF

Abstract:

As a step towards establishing homotopy-theoretic foundations for topological data analysis (TDA), we introduce and study homotopy interleavings between filtered topological spaces. These are homotopy-invariant analogues of interleavings, objects commonly used in TDA to articulate stability and inference theorems. Intuitively, whereas a strict interleaving between filtered spaces $X$ and $Y$ certifies that $X$ and $Y$ are approximately isomorphic, a homotopy interleaving between $X$ and $Y$ certifies that $X$ and $Y$ are approximately weakly equivalent.

The main results of this paper are that homotopy interleavings induce an extended pseudometric $d_{HI}$ on filtered spaces, and that this is the universal pseudometric satisfying natural stability and homotopy invariance axioms. To motivate these axioms, we also observe that $d_{HI}$ (or more generally, any pseudometric satisfying these two axioms and an additional “homology bounding” axiom) can be used to formulate lifts of several fundamental TDA theorems from the algebraic (homological) level to the level of filtered spaces.

Finally, we consider the problem of establishing a persistent Whitehead theorem in terms of homotopy interleavings. We provide a counterexample to a naive formulation of the result.

References

M. A. Batan, M. Pamuk, and H. Varli. 2019. Persistent homotopy, Preprint, arXiv:1909.08865.
U. Bauer, M. Kerber, F. Roll, and A. Rolle. A unified view on the functorial nerve theorem and its variations, Expositiones Mathematicae (2023)
Ulrich Bauer and Michael Lesnick, Induced matchings and the algebraic stability of persistence barcodes, J. Comput. Geom. 6 (2015), no. 2, 162–191. MR 3333456, DOI 10.20382/jocg.v6i2a9
Håvard Bakke Bjerkevik, On the stability of interval decomposable persistence modules, Discrete Comput. Geom. 66 (2021), no. 1, 92–121. MR 4270636, DOI 10.1007/s00454-021-00298-0
H. B. Bjerkevik and M. Lesnick. 2021. $\ell ^{p}$-Distances on multiparameter persistence modules, Preprint, arXiv:2106.13589.
A. J. Blumberg and M. Lesnick, Stability of 2-parameter persistent homology, Foundations of Computational Mathematics (2022)
Andrew J. Blumberg and Michael A. Mandell, Quantitative homotopy theory in topological data analysis, Found. Comput. Math. 13 (2013), no. 6, 885–911. MR 3124944, DOI 10.1007/s10208-013-9177-5
Omer Bobrowski, Sayan Mukherjee, and Jonathan E. Taylor, Topological consistency via kernel estimation, Bernoulli 23 (2017), no. 1, 288–328. MR 3556774, DOI 10.3150/15-BEJ744
Jean-Daniel Boissonnat, Leonidas J. Guibas, and Steve Y. Oudot, Manifold reconstruction in arbitrary dimensions using witness complexes, Discrete Comput. Geom. 42 (2009), no. 1, 37–70. MR 2506737, DOI 10.1007/s00454-009-9175-1
Magnus Bakke Botnan and William Crawley-Boevey, Decomposition of persistence modules, Proc. Amer. Math. Soc. 148 (2020), no. 11, 4581–4596. MR 4143378, DOI 10.1090/proc/14790
Magnus Bakke Botnan and Michael Lesnick, Algebraic stability of zigzag persistence modules, Algebr. Geom. Topol. 18 (2018), no. 6, 3133–3204. MR 3868218, DOI 10.2140/agt.2018.18.3133
Magnus Bakke Botnan and Gard Spreemann, Approximating persistent homology in Euclidean space through collapses, Appl. Algebra Engrg. Comm. Comput. 26 (2015), no. 1-2, 73–101. MR 3320906, DOI 10.1007/s00200-014-0247-y
B. Brehm and H. Hardering. 2018. Sparips, Preprint, arXiv:1807.09982.
Morten Brun and Nello Blaser, Sparse Dowker nerves, J. Appl. Comput. Topol. 3 (2019), no. 1-2, 1–28. MR 3988211, DOI 10.1007/s41468-019-00028-9
Peter Bubenik, Vin de Silva, and Jonathan Scott, Metrics for generalized persistence modules, Found. Comput. Math. 15 (2015), no. 6, 1501–1531. MR 3413628, DOI 10.1007/s10208-014-9229-5
Gunnar Carlsson, Topological pattern recognition for point cloud data, Acta Numer. 23 (2014), 289–368. MR 3202240, DOI 10.1017/S0962492914000051
Gunnar Carlsson, Tigran Ishkhanov, Vin de Silva, and Afra Zomorodian, On the local behavior of spaces of natural images, Int. J. Comput. Vis. 76 (2008), no. 1, 1–12. MR 3715451, DOI 10.1007/s11263-007-0056-x
Gunnar Carlsson, Gurjeet Singh, and Afra Zomorodian, Computing multidimensional persistence, J. Comput. Geom. 1 (2010), no. 1, 72–100. MR 2770959, DOI 10.20382/jocg.v1i1a6
N.J. Cavanna, M. Jahanseir, and D. R. Sheehy. 2015. A geometric perspective on sparse filtrations, Proceedings of the Canadian Conference on Computational Geometry.
Joseph Minhow Chan, Gunnar Carlsson, and Raul Rabadan, Topology of viral evolution, Proc. Natl. Acad. Sci. USA 110 (2013), no. 46, 18566–18571. MR 3153945, DOI 10.1073/pnas.1313480110
F. Chazal, D. Cohen-Steiner, M. Glisse, L. J. Guibas, and S. Y. Oudot. 2009. Proximity of persistence modules and their diagrams, Proceedings of the 25th Annual Symposium on Computational Geometry, SCG ’09, ACM, New York, NY, USA, pp. 237–246.
F. Chazal, D. Cohen-Steiner, L. J. Guibas, F. Mémoli, and S. Y. Oudot. 2009. Gromov–Hausdorff stable signatures for shapes using persistence, Proceedings of the Symposium on Geometry Processing, SGP ’09, Eurographics Association, Aire-la-Ville, Switzerland, Switzerland, pp. 1393–1403.
Frédéric Chazal, William Crawley-Boevey, and Vin de Silva, The observable structure of persistence modules, Homology Homotopy Appl. 18 (2016), no. 2, 247–265. MR 3575998, DOI 10.4310/HHA.2016.v18.n2.a14
Frédéric Chazal, Vin de Silva, Marc Glisse, and Steve Oudot, The structure and stability of persistence modules, SpringerBriefs in Mathematics, Springer, [Cham], 2016. MR 3524869, DOI 10.1007/978-3-319-42545-0
Frédéric Chazal, Vin de Silva, and Steve Oudot, Persistence stability for geometric complexes, Geom. Dedicata 173 (2014), 193–214. MR 3275299, DOI 10.1007/s10711-013-9937-z
Frédéric Chazal, Leonidas J. Guibas, Steve Y. Oudot, and Primoz Skraba, Persistence-based clustering in Riemannian manifolds, J. ACM 60 (2013), no. 6, Art. 41, 38. MR 3144911, DOI 10.1145/2535927
Frédéric Chazal and Steve Y. Oudot, Towards persistence-based reconstruction in Euclidean spaces, Computational geometry (SCG’08), ACM, New York, 2008, pp. 232–241. MR 2504289, DOI 10.1145/1377676.1377719
Aruni Choudhary, Michael Kerber, and Sharath Raghvendra, Improved topological approximations by digitization, Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, Philadelphia, PA, 2019, pp. 2675–2688. MR 3909635, DOI 10.1137/1.9781611975482.166
Aruni Choudhary, Michael Kerber, and Sharath Raghvendra, Polynomial-sized topological approximations using the permutahedron, Discrete Comput. Geom. 61 (2019), no. 1, 42–80. MR 3925543, DOI 10.1007/s00454-017-9951-2
Aruni Choudhary, Michael Kerber, and Sharath Raghvendra, Improved approximate rips filtrations with shifted integer lattices and cubical complexes, J. Appl. Comput. Topol. 5 (2021), no. 3, 425–458. MR 4298670, DOI 10.1007/s41468-021-00072-4
Samir Chowdhury and Facundo Mémoli, A functorial Dowker theorem and persistent homology of asymmetric networks, J. Appl. Comput. Topol. 2 (2018), no. 1-2, 115–175. MR 3873182, DOI 10.1007/s41468-018-0020-6
Denis-Charles Cisinski, Locally constant functors, Math. Proc. Cambridge Philos. Soc. 147 (2009), no. 3, 593–614. MR 2557145, DOI 10.1017/S030500410900262X
David Cohen-Steiner, Herbert Edelsbrunner, and John Harer, Stability of persistence diagrams, Discrete Comput. Geom. 37 (2007), no. 1, 103–120. MR 2279866, DOI 10.1007/s00454-006-1276-5
Jean-Marc Cordier and Timothy Porter, Vogt’s theorem on categories of homotopy coherent diagrams, Math. Proc. Cambridge Philos. Soc. 100 (1986), no. 1, 65–90. MR 838654, DOI 10.1017/S0305004100065877
William Crawley-Boevey, Decomposition of pointwise finite-dimensional persistence modules, J. Algebra Appl. 14 (2015), no. 5, 1550066, 8. MR 3323327, DOI 10.1142/S0219498815500668
V. De Silva and G. Carlsson. 2004. Topological estimation using witness complexes. Proceedings of the First Eurographics Conference on Point-Based Graphics, pp. 157–166.
V. de Silva, E. Munch, and A. Stefanou, Theory of interleavings on categories with a flow, Theory Appl. Categ. 33 (2018), Paper No. 21, 583–607. MR 3812461
T. K. Dey, F. Fan, and Y. Wang. 2014. Computing topological persistence for simplicial maps. Proceedings of the Thirtieth Annual Symposium on Computational Geometry, pp. 345–354.
Tamal K. Dey, Dayu Shi, and Yusu Wang, SimBa: an efficient tool for approximating Rips-filtration persistence via simplicial batch collapse, ACM J. Exp. Algorithmics 24 (2019), Art. 1.5, 16. MR 3915534, DOI 10.1145/3284360
D. Dugger, 2008. A primer on homotopy colimits, Preprint, Revised January 2017.
William G. Dwyer, Philip S. Hirschhorn, Daniel M. Kan, and Jeffrey H. Smith, Homotopy limit functors on model categories and homotopical categories, Mathematical Surveys and Monographs, vol. 113, American Mathematical Society, Providence, RI, 2004. MR 2102294, DOI 10.1090/surv/113
W. G. Dwyer and J. Spaliński, Homotopy theories and model categories, Handbook of algebraic topology, North-Holland, Amsterdam, 1995, pp. 73–126. MR 1361887, DOI 10.1016/B978-044481779-2/50003-1
Herbert Edelsbrunner and John L. Harer, Computational topology, American Mathematical Society, Providence, RI, 2010. An introduction. MR 2572029, DOI 10.1090/mbk/069
Patrizio Frosini, Claudia Landi, and Facundo Mémoli, The persistent homotopy type distance, Homology Homotopy Appl. 21 (2019), no. 2, 231–259. MR 3923782, DOI 10.4310/HHA.2019.v21.n2.a13
R. Ghrist and G. Henselman-Petrusek. 2021. Saecular persistence. Preprint, arXiv:2112.04927.
Philip S. Hirschhorn, Model categories and their localizations, Mathematical Surveys and Monographs, vol. 99, American Mathematical Society, Providence, RI, 2003. MR 1944041, DOI 10.1090/surv/099
Mark Hovey, Model categories, Mathematical Surveys and Monographs, vol. 63, American Mathematical Society, Providence, RI, 1999. MR 1650134
Daniel C. Isaksen, A model structure on the category of pro-simplicial sets, Trans. Amer. Math. Soc. 353 (2001), no. 7, 2805–2841. MR 1828474, DOI 10.1090/S0002-9947-01-02722-2
J. F. Jardine, 2020. Persistent homotopy theory, Preprint, arXiv:2002.10013.
E. Lanari and L. Scoccola, Rectification of interleavings and a persistent Whitehead theorem, Algebraic & Geometric Topology 23 (2023), no. 2, 803–832
Michael Phillip Lesnick, Multidimensional Interleavings and Applications to Topological Inference, ProQuest LLC, Ann Arbor, MI, 2012. Thesis (Ph.D.)–Stanford University. MR 4172343
Michael Lesnick, The theory of the interleaving distance on multidimensional persistence modules, Found. Comput. Math. 15 (2015), no. 3, 613–650. MR 3348168, DOI 10.1007/s10208-015-9255-y
David Letscher, On persistent homotopy, knotted complexes and the Alexander module, Proceedings of the 3rd Innovations in Theoretical Computer Science Conference, ACM, New York, 2012, pp. 428–441. MR 3388406
Jacob Lurie, Higher topos theory, Annals of Mathematics Studies, vol. 170, Princeton University Press, Princeton, NJ, 2009. MR 2522659, DOI 10.1515/9781400830558
Saunders Mac Lane, Categories for the working mathematician, 2nd ed., Graduate Texts in Mathematics, vol. 5, Springer-Verlag, New York, 1998. MR 1712872
M. A. Mandell, J. P. May, S. Schwede, and B. Shipley, Model categories of diagram spectra, Proc. London Math. Soc. (3) 82 (2001), no. 2, 441–512. MR 1806878, DOI 10.1112/S0024611501012692
J. P. May, A concise course in algebraic topology, Chicago Lectures in Mathematics, University of Chicago Press, Chicago, IL, 1999. MR 1702278
J. P. May and K. Ponto, More concise algebraic topology, Chicago Lectures in Mathematics, University of Chicago Press, Chicago, IL, 2012. Localization, completion, and model categories. MR 2884233
F. Mémoli, 2012. Metric geometry and persistent homology, Presentation, ATMCS 5 (Algebraic and Topological Methods in Computer Science), Edinburgh.
F. Mémoli, 2012. Persistence homology and metric geometry, Presentation, Banff Workshop on Topological Data Analysis and Machine Learning Theory, Recording at http://www.birs.ca/events/2012/5-day-workshops/12w5081/videos/.
Facundo Mémoli, Distances between datasets, Modern approaches to discrete curvature, Lecture Notes in Math., vol. 2184, Springer, Cham, 2017, pp. 115–132. MR 3727577
F. Mémoli and L. Zhou. 2019. Persistent homotopy groups of metric spaces, Preprint, arXiv:1912.12399.
Partha Niyogi, Stephen Smale, and Shmuel Weinberger, Finding the homology of submanifolds with high confidence from random samples, Discrete Comput. Geom. 39 (2008), no. 1-3, 419–441. MR 2383768, DOI 10.1007/s00454-008-9053-2
Amit Patel, Generalized persistence diagrams, J. Appl. Comput. Topol. 1 (2018), no. 3-4, 397–419. MR 3975559, DOI 10.1007/s41468-018-0012-6
Daniel Quillen, Higher algebraic $K$-theory. I, Algebraic $K$-theory, I: Higher $K$-theories (Proc. Conf., Battelle Memorial Inst., Seattle, Wash., 1972) Lecture Notes in Math., Vol. 341, Springer, Berlin-New York, 1973, pp. 85–147. MR 338129
Emily Riehl, Categorical homotopy theory, New Mathematical Monographs, vol. 24, Cambridge University Press, Cambridge, 2014. MR 3221774, DOI 10.1017/CBO9781107261457
E. Riehl, 2017. Category theory in context, Courier Dover Publications.
E. Riehl, 2018. Homotopy coherent structures, Preprint, arXiv:1801.07404.
L. N. Scoccola, 2020. Locally persistent categories and metric properties of interleaving distances, Ph.D. Thesis, The University of Western Ontario.
Donald R. Sheehy, Linear-size approximations to the Vietoris-Rips filtration, Discrete Comput. Geom. 49 (2013), no. 4, 778–796. MR 3068574, DOI 10.1007/s00454-013-9513-1
Donald R. Sheehy, A sparse Delaunay filtration, 37th International Symposium on Computational Geometry, LIPIcs. Leibniz Int. Proc. Inform., vol. 189, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2021, pp. Art. No. 58, 16. MR 4287065
M. Shulman, 2006. Homotopy limits and colimits and enriched homotopy theory, Preprint, math/0610194.
J. Smith, A homotopy commutative diagram that cannot be strictified, MathOverflow, http://mathoverflow.net/q/82516 (version: 2011-12-02).
N. P. Strickland, 2009. The category of CGWH spaces, Preprint.
Hirosi Toda, Composition methods in homotopy groups of spheres, Annals of Mathematics Studies, No. 49, Princeton University Press, Princeton, NJ, 1962. MR 143217
Rainer M. Vogt, Homotopy limits and colimits, Math. Z. 134 (1973), 11–52. MR 331376, DOI 10.1007/BF01219090
Afra Zomorodian and Gunnar Carlsson, Computing persistent homology, Discrete Comput. Geom. 33 (2005), no. 2, 249–274. MR 2121296, DOI 10.1007/s00454-004-1146-y