On Rectangle-Decomposable 2-Parameter Persistence Modules

Autor: Botnan, Magnus Bakke, Lebovici, Vadim, Oudot, Steve, Cabello, Sergio, Chen, Danny Z.
Přispěvatelé: Mathematics, Vrije Universiteit Amsterdam [Amsterdam] (VU), Understanding the Shape of Data (DATASHAPE), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Inria Saclay - Ile de France, Institut National de Recherche en Informatique et en Automatique (Inria), Sergio Cabello, Danny Z. Chen, Schloss Dagstuhl--Leibniz-Zentrum für Informatik, La Géometrie au Service du Numérique (GEOMERIX), Laboratoire d'informatique de l'École polytechnique [Palaiseau] (LIX), École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)-École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)-Inria Saclay - Ile de France, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Institut Polytechnique de Paris (IP Paris), Cabello, Sergio, Chen, Danny Z.
Jazyk: angličtina
Rok vydání: 2022
Předmět:
Zdroj: Discrete and Computational Geometry, 68(4), 1078-1101. Springer New York
Leibniz International Proceedings in Informatics
SoCG 2020-36th International Symposium on Computational Geometry
SoCG 2020-36th International Symposium on Computational Geometry, Sergio Cabello; Danny Z. Chen, Jun 2020, Zurich, Switzerland. pp.22:1-22:16, ⟨10.4230/LIPIcs.SoCG.2020.22⟩
Botnan, M B, Lebovici, V & Oudot, S 2022, ' On Rectangle-Decomposable 2-Parameter Persistence Modules ', Discrete and Computational Geometry, vol. 68, no. 4, pp. 1078-1101 . https://doi.org/10.1007/s00454-022-00383-y
Discrete and Computational Geometry
Discrete and Computational Geometry, 2022, 68 (4), pp.1078-1101. ⟨10.1007/s00454-022-00383-y⟩
36th International Symposium on Computational Geometry, SoCG 2020: [Proceedings], 1-16
STARTPAGE=1;ENDPAGE=16;TITLE=36th International Symposium on Computational Geometry, SoCG 2020
Botnan, M B, Lebovici, V & Oudot, S 2020, On rectangle-decomposable 2-parameter persistence modules . in S Cabello & D Z Chen (eds), 36th International Symposium on Computational Geometry, SoCG 2020 : [Proceedings] . Leibniz International Proceedings in Informatics, LIPIcs, vol. 164, Schloss Dagstuhl-Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, pp. 1-16, 36th International Symposium on Computational Geometry, SoCG 2020, Zurich, Switzerland, 23/06/20 . https://doi.org/10.4230/LIPIcs.SoCG.2020.22
ISSN: 0179-5376
1868-8969
1432-0444
DOI: 10.4230/LIPIcs.SoCG.2020.22⟩
Popis: This paper addresses two questions: (a) can we identify a sensible class of 2-parameter persistence modules on which the rank invariant is complete? (b) can we determine efficiently whether a given 2-parameter persistence module belongs to this class? We provide positive answers to both questions, and our class of interest is that of rectangle-decomposable modules. Our contributions include: on the one hand, a proof that the rank invariant is complete on rectangle-decomposable modules, together with an inclusion-exclusion formula for counting the multiplicities of the summands; on the other hand, algorithms to check whether a module induced in homology by a bifiltration is rectangle-decomposable, and to decompose it in the affirmative, with a better complexity than state-of-the-art decomposition methods for general 2-parameter persistence modules. Our algorithms are backed up by a new structure theorem, whereby a 2-parameter persistence module is rectangle-decomposable if, and only if, its restrictions to squares are. This local characterization is key to the efficiency of our algorithms, and it generalizes previous conditions derived for the smaller class of block-decomposable modules. It also admits an algebraic formulation that turns out to be a weaker version of the one for block-decomposability. By contrast, we show that general interval-decomposability does not admit such a local characterization, even when locality is understood in a broad sense. Our analysis focuses on the case of modules indexed over finite grids, the more general cases are left as future work.
Comment: This is the final version to be published in DCG. Changed the algorithm in Section 3 for computing the rank invariant, which was incorrect. The new algorithm reduces to computing 1-parameter vineyards along a family of paths in the grid. It was first proposed in the PhD thesis of D. Morozov
Databáze: OpenAIRE
Externí odkaz: