1 Search Results for "Lebovici, Vadim"

Document
DOI: 10.4230/LIPIcs.SoCG.2020.22
On Rectangle-Decomposable 2-Parameter Persistence Modules

Authors: Magnus Bakke Botnan, Vadim Lebovici, and Steve Oudot

Published in: LIPIcs, Volume 164, 36th International Symposium on Computational Geometry (SoCG 2020)

Abstract
This paper addresses two questions: (1) can we identify a sensible class of 2-parameter persistence modules on which the rank invariant is complete? (2) 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: (a) 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; (b) 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 condition is key to the efficiency of our algorithms, and it generalizes previous conditions from the class of block-decomposable modules to the larger one of rectangle-decomposable modules. It also admits an algebraic formulation that turns out to be a weaker version of the one for block-decomposability. Our analysis focuses on the case of modules indexed over finite grids, the more general cases are left as future work.
Cite as

Magnus Bakke Botnan, Vadim Lebovici, and Steve Oudot. On Rectangle-Decomposable 2-Parameter Persistence Modules. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 22:1-22:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{botnan_et_al:LIPIcs.SoCG.2020.22,
  author =	{Botnan, Magnus Bakke and Lebovici, Vadim and Oudot, Steve},
  title =	{{On Rectangle-Decomposable 2-Parameter Persistence Modules}},
  booktitle =	{36th International Symposium on Computational Geometry (SoCG 2020)},
  pages =	{22:1--22:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-143-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{164},
  editor =	{Cabello, Sergio and Chen, Danny Z.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.22},
  URN =		{urn:nbn:de:0030-drops-121802},
  doi =		{10.4230/LIPIcs.SoCG.2020.22},
  annote =	{Keywords: topological data analysis, multiparameter persistence, rank invariant}
}
  • Refine by Author
  • 1 Botnan, Magnus Bakke
  • 1 Lebovici, Vadim
  • 1 Oudot, Steve

  • Refine by Classification
  • 1 Mathematics of computing → Algebraic topology

  • Refine by Keyword
  • 1 multiparameter persistence
  • 1 rank invariant
  • 1 topological data analysis

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2020

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact