{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:46:35Z","timestamp":1740109595888,"version":"3.37.3"},"reference-count":27,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2023,5,5]],"date-time":"2023-05-05T00:00:00Z","timestamp":1683244800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,5,5]],"date-time":"2023-05-05T00:00:00Z","timestamp":1683244800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"Narodowe Centrum Nauki, Max-Planck-Gesellschaft"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Discrete Comput Geom"],"published-print":{"date-parts":[[2024,4]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>In topological data analysis (TDA), persistence diagrams (PDs) have been a successful tool. To compare them, Wasserstein and bottleneck distances are commonly used. We address the shortcomings of these metrics and show a way to investigate them in a systematic way by introducing bottleneck profiles. This leads to a notion of discrete Prokhorov metrics for PDs as a generalization of the bottleneck distance. These metrics satisfy a stability result and can be used to bound Wasserstein metrics from above and from below. We provide algorithms to compute the newly introduced quantities and end with an discussion about experiments.<\/jats:p>","DOI":"10.1007\/s00454-023-00498-w","type":"journal-article","created":{"date-parts":[[2023,5,5]],"date-time":"2023-05-05T18:01:51Z","timestamp":1683309711000},"page":"1131-1164","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Bottleneck Profiles and Discrete Prokhorov Metrics for Persistence Diagrams"],"prefix":"10.1007","volume":"71","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5352-3102","authenticated-orcid":false,"given":"Pawe\u0142","family":"D\u0142otko","sequence":"first","affiliation":[],"role":[{"role":"author","vocab":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6500-6329","authenticated-orcid":false,"given":"Niklas","family":"Hellmer","sequence":"additional","affiliation":[],"role":[{"role":"author","vocab":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,5,5]]},"reference":[{"key":"498_CR1","unstructured":"Adams, H., Emerson, T., Kirby, M., Neville, R., Peterson, Ch., Shipman, P., Chepushtanova, S., Hanson, E., Motta, F., Ziegelmeier, L.: Persistence images: a stable vector representation of persistent homology. J. Mach. Learn. Res. 18, #\u00a08 (2017)"},{"key":"498_CR2","doi-asserted-by":"crossref","unstructured":"Atienza, N., Gonzalez-D\u00edaz, R., Soriano-Trigueros, M.: On the stability of persistent entropy and new summary functions for topological data analysis. Pattern Recognit. 107, #\u00a0107509 (2020)","DOI":"10.1016\/j.patcog.2020.107509"},{"issue":"4","key":"498_CR3","doi-asserted-by":"publisher","first-page":"745","DOI":"10.1007\/s10208-014-9201-4","volume":"14","author":"AJ Blumberg","year":"2014","unstructured":"Blumberg, A.J., Gal, I., Mandell, M.A., Pancia, M.: Robust statistics, hypothesis testing, and confidence intervals for persistent homology on metric measure spaces. Found. Comput. Math. 14(4), 745\u2013789 (2014)","journal-title":"Found. Comput. Math."},{"issue":"3\u20134","key":"498_CR4","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1007\/s41468-018-0022-4","volume":"2","author":"P Bubenik","year":"2018","unstructured":"Bubenik, P., Vergili, T.: Topological spaces of persistence modules and their properties. J. Appl. Comput. Topol. 2(3\u20134), 233\u2013269 (2018)","journal-title":"J. Appl. Comput. Topol."},{"key":"498_CR5","unstructured":"Carriere, M.: 3D shape segmentation using TDA. https:\/\/github.com\/MathieuCarriere\/sklearn-tda\/tree\/master\/example\/3DSeg"},{"issue":"1","key":"498_CR6","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1137\/19M1243932","volume":"4","author":"W Chach\u00f3lski","year":"2020","unstructured":"Chach\u00f3lski, W., Riihim\u00e4ki, H.: Metrics and stabilization in one parameter persistence. SIAM J. Appl. Algebra Geom. 4(1), 69\u201398 (2020)","journal-title":"SIAM J. Appl. Algebra Geom."},{"key":"498_CR7","doi-asserted-by":"publisher","first-page":"1393","DOI":"10.1111\/j.1467-8659.2009.01516.x","volume":"28","author":"F Chazal","year":"2009","unstructured":"Chazal, F., Cohen-Steiner, D., Guibas, L.J., M\u00e9moli, F., Oudot, S.Y.: Gromov\u2013Hausdorff stable signatures for shapes using persistence. Comput. Graph. Forum 28, 1393\u20131403 (2009)","journal-title":"Comput. Graph. Forum"},{"key":"498_CR8","doi-asserted-by":"crossref","unstructured":"Chen, X., Golovinskiy, A., Funkhouser, T.: A benchmark for 3D mesh segmentation. ACM Trans. Graph. 28(3), #\u00a073 (2009)","DOI":"10.1145\/1531326.1531379"},{"key":"498_CR9","doi-asserted-by":"crossref","unstructured":"Crawley-Boevey, W.: Decomposition of pointwise finite-dimensional persistence modules. J. Algebra Appl. 14(5), #\u00a01550066 (2015)","DOI":"10.1142\/S0219498815500668"},{"key":"498_CR10","unstructured":"Dlotko, P., Carriere, M., Royer, M.: Persistence representations. In: GUDHI User and Reference Manual, 3.4.1 edn (2021). https:\/\/gudhi.inria.fr\/doc\/latest\/group___persistence__representations.html"},{"key":"498_CR11","volume-title":"Computational Topology: An Introduction","author":"H Edelsbrunner","year":"2010","unstructured":"Edelsbrunner, H., Harer, J.L.: Computational Topology: An Introduction. American Mathematical Society, Providence (2010)"},{"issue":"1","key":"498_CR12","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s00453-001-0016-8","volume":"31","author":"A Efrat","year":"2001","unstructured":"Efrat, A., Itai, A., Katz, M.J.: Geometry helps in bottleneck matching and related problems. Algorithmica 31(1), 1\u201328 (2001)","journal-title":"Algorithmica"},{"issue":"3","key":"498_CR13","doi-asserted-by":"publisher","first-page":"419","DOI":"10.1111\/j.1751-5823.2002.tb00178.x","volume":"70","author":"AL Gibbs","year":"2002","unstructured":"Gibbs, A.L., Su, F.E.: On choosing and bounding probability metrics. Int. Stat. Rev. 70(3), 419\u2013435 (2002)","journal-title":"Int. Stat. Rev."},{"key":"498_CR14","unstructured":"Godi, F.: Bottleneck distance. In: GUDHI User and Reference Manual, 3.4.1 edn (2021). https:\/\/gudhi.inria.fr\/doc\/latest\/group__bottleneck__distance.html"},{"key":"498_CR15","series-title":"Graduate Texts in Mathematics","volume-title":"Classical Fourier Analysis","author":"L Grafakos","year":"2014","unstructured":"Grafakos, L.: Classical Fourier Analysis. Graduate Texts in Mathematics, vol. 249. Springer, New York (2014)"},{"key":"498_CR16","unstructured":"Gromov, M.: Metric Structures for Riemannian and Non-Riemannian Spaces. Modern Birkh\u00e4user Classics. Birkh\u00e4user, Boston (2007)"},{"key":"498_CR17","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1137\/0202019","volume":"2","author":"JE Hopcroft","year":"1973","unstructured":"Hopcroft, J.E., Karp, R.M.: An $$n^{5\/2}$$ algorithm for maximum matchings in bipartite graphs. SIAM J. Comput. 2, 225\u2013231 (1973)","journal-title":"SIAM J. Comput."},{"key":"498_CR18","doi-asserted-by":"crossref","unstructured":"Kerber, M., Morozov, D., Nigmetov, A.: Geometry helps to compare persistence diagrams. ACM J. Exp. Algorithmics 22, #\u00a01.4 (2017)","DOI":"10.1145\/3064175"},{"key":"498_CR19","unstructured":"Lacombe, T., Cuturi, M., Oudot, S.: Large scale computation of means and clusters for persistence diagrams using optimal transport (2018). arXiv:1805.08331"},{"key":"498_CR20","doi-asserted-by":"crossref","unstructured":"Mileyko, Yu., Mukherjee, S., Harer, J.: Probability measures on the space of persistence diagrams. Inverse Probl. 27(12), #\u00a0124007 (2011)","DOI":"10.1088\/0266-5611\/27\/12\/124007"},{"key":"498_CR21","first-page":"2825","volume":"12","author":"F Pedregosa","year":"2011","unstructured":"Pedregosa, F., Varoquaux, G., Gramfort, A., Michel, V., Thirion, B., Grisel, O., Blondel, M., Prettenhofer, P., Weiss, R., Dubourg, V., Vanderplas, J., Passos, A., Cournapeau, D., Brucher, M., Perrot, M., Duchesnay, \u00c9.: Scikit-learn: machine learning in Python. J. Mach. Learn. Res. 12, 2825\u20132830 (2011)","journal-title":"J. Mach. Learn. Res."},{"issue":"5\u20136","key":"498_CR22","doi-asserted-by":"publisher","first-page":"355","DOI":"10.1561\/2200000073","volume":"11","author":"G Peyr\u00e9","year":"2019","unstructured":"Peyr\u00e9, G., Cuturi, M.: Computational optimal transport: with applications to data science. Found. Trends Mach. Learn. 11(5\u20136), 355\u2013607 (2019)","journal-title":"Found. Trends Mach. Learn."},{"key":"498_CR23","doi-asserted-by":"crossref","unstructured":"Prokhorov, Yu.V.: Convergence of random processes and limit theorems in probability theory. Teor. Veroyatnost. i Primenen. 1, 177\u2013238 (1956). (in Russian)","DOI":"10.1137\/1101016"},{"key":"498_CR24","unstructured":"Rachev, S.T.: Probability Metrics and the Stability of Stochastic Models. Wiley Series in Probability and Mathematical Statistics: Applied Probability and Statistics. Wiley, Chichester (1991)"},{"key":"498_CR25","unstructured":"Schubert, E., Lenssen, L., Muhr, D.: k-medoids clustering with the FasterPAM algorithm. https:\/\/github.com\/kno10\/python-kmedoids"},{"key":"498_CR26","unstructured":"Schubert, E., Rousseeuw, P.J.: Fast and eager $$k$$-medoids clustering: $$O(k)$$ runtime improvement of the PAM, CLARA, and CLARANS algorithms. Inf. Syst. 101, #\u00a0101804 (2021)"},{"key":"498_CR27","series-title":"Graduate Studies in Mathematics","doi-asserted-by":"crossref","DOI":"10.1090\/gsm\/058","volume-title":"Topics in Optimal Transportation","author":"C Villani","year":"2003","unstructured":"Villani, C.: Topics in Optimal Transportation. Graduate Studies in Mathematics, vol. 58. American Mathematical Society, Providence (2003)"}],"container-title":["Discrete &amp; Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-023-00498-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00454-023-00498-w\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-023-00498-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,11]],"date-time":"2024-03-11T15:11:03Z","timestamp":1710169863000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00454-023-00498-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,5,5]]},"references-count":27,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2024,4]]}},"alternative-id":["498"],"URL":"https:\/\/doi.org\/10.1007\/s00454-023-00498-w","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"type":"print","value":"0179-5376"},{"type":"electronic","value":"1432-0444"}],"subject":[],"published":{"date-parts":[[2023,5,5]]},"assertion":[{"value":"2 February 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 July 2022","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"10 September 2022","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"5 May 2023","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}