Get 20M+ Full-Text Papers For Less Than $1.50/day. Start a 14-Day Trial for You or Your Team.

Learn More →

Generalized persistence algorithm for decomposing multiparameter persistence modules

Generalized persistence algorithm for decomposing multiparameter persistence modules The classical persistence algorithm computes the unique decomposition of a persistence module implicitly given by an input simplicial filtration. Based on matrix reduction, this algorithm is a cornerstone of the emergent area of topological data analysis. Its input is a simplicial filtration defined over the integers Z\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$${\mathbb {Z}}$$\end{document} giving rise to a 1-parameter persistence module. It has been recognized that multiparameter version of persistence modules given by simplicial filtrations over d-dimensional integer grids Zd\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$${\mathbb {Z}}^d$$\end{document} is equally or perhaps more important in data science applications. However, in the multiparameter setting, one of the main challenges is that topological summaries based on algebraic structure such as decompositions and bottleneck distances cannot be as efficiently computed as in the 1-parameter case because there is no known extension of the persistence algorithm to multiparameter persistence modules. We present an efficient algorithm to compute the unique decomposition of a finitely presented persistence module M defined over the multiparameter Zd\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$${\mathbb {Z}}^d$$\end{document}. The algorithm first assumes that the module is presented with a set of N generators and relations that are distinctly graded. Based on a generalized matrix reduction technique it runs in O(N2ω+1)\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$O(N^{2\omega +1})$$\end{document} time where ω<2.373\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$\omega <2.373$$\end{document} is the exponent of matrix multiplication. This is much better than the well known algorithm called Meataxe which runs in O~(N6(d+1))\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$${\tilde{O}}(N^{6(d+1)})$$\end{document} time on such an input. In practice, persistence modules are usually induced by simplicial filtrations. With such an input consisting of n simplices, our algorithm runs in O(n(d-1)(2ω+1))\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$O(n^{(d-1)(2\omega + 1)})$$\end{document} time for d≥2\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$d\ge 2$$\end{document}. For the special case of zero dimensional homology, it runs in time O(n2ω+1)\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$O(n^{2\omega +1})$$\end{document}. http://www.deepdyve.com/assets/images/DeepDyve-Logo-lg.png Journal of Applied and Computational Topology Springer Journals

Generalized persistence algorithm for decomposing multiparameter persistence modules

Download PDF
52 pages

Loading next page...
 
/lp/springer-journals/generalized-persistence-algorithm-for-decomposing-multiparameter-0y5j1eFsAY
Publisher
Springer Journals
Copyright
Copyright © The Author(s), under exclusive licence to Springer Nature Switzerland AG 2022
ISSN
2367-1726
eISSN
2367-1734
DOI
10.1007/s41468-022-00087-5
Publisher site
See Article on Publisher Site

Abstract

The classical persistence algorithm computes the unique decomposition of a persistence module implicitly given by an input simplicial filtration. Based on matrix reduction, this algorithm is a cornerstone of the emergent area of topological data analysis. Its input is a simplicial filtration defined over the integers Z\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$${\mathbb {Z}}$$\end{document} giving rise to a 1-parameter persistence module. It has been recognized that multiparameter version of persistence modules given by simplicial filtrations over d-dimensional integer grids Zd\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$${\mathbb {Z}}^d$$\end{document} is equally or perhaps more important in data science applications. However, in the multiparameter setting, one of the main challenges is that topological summaries based on algebraic structure such as decompositions and bottleneck distances cannot be as efficiently computed as in the 1-parameter case because there is no known extension of the persistence algorithm to multiparameter persistence modules. We present an efficient algorithm to compute the unique decomposition of a finitely presented persistence module M defined over the multiparameter Zd\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$${\mathbb {Z}}^d$$\end{document}. The algorithm first assumes that the module is presented with a set of N generators and relations that are distinctly graded. Based on a generalized matrix reduction technique it runs in O(N2ω+1)\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$O(N^{2\omega +1})$$\end{document} time where ω<2.373\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$\omega <2.373$$\end{document} is the exponent of matrix multiplication. This is much better than the well known algorithm called Meataxe which runs in O~(N6(d+1))\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$${\tilde{O}}(N^{6(d+1)})$$\end{document} time on such an input. In practice, persistence modules are usually induced by simplicial filtrations. With such an input consisting of n simplices, our algorithm runs in O(n(d-1)(2ω+1))\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$O(n^{(d-1)(2\omega + 1)})$$\end{document} time for d≥2\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$d\ge 2$$\end{document}. For the special case of zero dimensional homology, it runs in time O(n2ω+1)\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$O(n^{2\omega +1})$$\end{document}.

Journal

Journal of Applied and Computational Topology – Springer Journals

Published: Sep 1, 2022

Keywords: Multiparameter persistence; Computational topology; Topological data analysis; Persistence module; Indecomposables; Matrix reduction; Presentations; 55-08; 55U30; 18G90

References

  • On the Krull–Schmidt theorem with application to sheaves
    Atiyah, M
  • Computing the interleaving distance is NP-hard
    Bjerkevik, HB; Botnan, MB; Kerber, M
  • Algebraic stability of zigzag persistence modules
    Botnan, MB; Lesnick, M
  • Phat—persistent homology algorithms toolbox
    Bauer, U; Kerber, M; Reininghaus, J; Wagner, H
  • Triangular factorization and inversion by fast matrix multiplication
    Bunch, JR; Hopcroft, JE
  • Topology and data
    Carlsson, G
  • The theory of multidimensional persistence
    Carlsson, G; Zomorodian, A
  • Betti numbers in multidimensional persistent homology are stable functions
    Cerri, A; Fabio, BD; Ferri, M; Frosini, P; Landi, C
  • Decomposition of exact pfd persistence bimodules
    Cochoy, J; Oudot, SY
  • Stability of persistence diagrams
    Cohen-Steiner, D; Edelsbrunner, H; Harer, J
  • The representation theorem of persistence revisited and generalized
    Corbet, R; Kerber, M
  • Ueber die theorie der algebraischen formen
    Hilbert, D
  • Testing modules for irreducibility
    Holt, DF; Rees, S
  • A generalization of the fast lup matrix decomposition algorithm and applications
    Ibarra, OH; Moran, S; Hui, R
  • Generalized persistence diagrams for persistence modules over posets
    Kim, W; Mémoli, F
  • The theory of the interleaving distance on multidimensional persistence modules
    Lesnick, M
  • Visualizing high-dimensional data: advances in the past decade
    Liu, S; Maljovec, D; Wang, B; Bremer, PT; Pascucci, V
  • On minimal graded free resolutions
    Römer, T
  • Linear-size approximations to the vietoris-rips filtration
    Sheehy, DR
  • Computing persistent homology
    Zomorodian, A; Carlsson, G