7 Search Results for "Lesnick, Michael"

Document
DOI: 10.4230/LIPIcs.SoCG.2023.15
Efficient Two-Parameter Persistence Computation via Cohomology

Authors: Ulrich Bauer, Fabian Lenzen, and Michael Lesnick

Published in: LIPIcs, Volume 258, 39th International Symposium on Computational Geometry (SoCG 2023)

Abstract
Clearing is a simple but effective optimization for the standard algorithm of persistent homology (ph), which dramatically improves the speed and scalability of ph computations for Vietoris-Rips filtrations. Due to the quick growth of the boundary matrices of a Vietoris-Rips filtration with increasing dimension, clearing is only effective when used in conjunction with a dual (cohomological) variant of the standard algorithm. This approach has not previously been applied successfully to the computation of two-parameter ph. We introduce a cohomological algorithm for computing minimal free resolutions of two-parameter ph that allows for clearing. To derive our algorithm, we extend the duality principles which underlie the one-parameter approach to the two-parameter setting. We provide an implementation and report experimental run times for function-Rips filtrations. Our method is faster than the current state-of-the-art by a factor of up to 20.
Cite as

Ulrich Bauer, Fabian Lenzen, and Michael Lesnick. Efficient Two-Parameter Persistence Computation via Cohomology. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 15:1-15:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{bauer_et_al:LIPIcs.SoCG.2023.15,
  author =	{Bauer, Ulrich and Lenzen, Fabian and Lesnick, Michael},
  title =	{{Efficient Two-Parameter Persistence Computation via Cohomology}},
  booktitle =	{39th International Symposium on Computational Geometry (SoCG 2023)},
  pages =	{15:1--15:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-273-0},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{258},
  editor =	{Chambers, Erin W. and Gudmundsson, Joachim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2023.15},
  URN =		{urn:nbn:de:0030-drops-178656},
  doi =		{10.4230/LIPIcs.SoCG.2023.15},
  annote =	{Keywords: Persistent homology, persistent cohomology, two-parameter persistence, clearing}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2022.24
The Universal 𝓁^p-Metric on Merge Trees

Authors: Robert Cardona, Justin Curry, Tung Lam, and Michael Lesnick

Published in: LIPIcs, Volume 224, 38th International Symposium on Computational Geometry (SoCG 2022)

Abstract
Adapting a definition given by Bjerkevik and Lesnick for multiparameter persistence modules, we introduce an 𝓁^p-type extension of the interleaving distance on merge trees. We show that our distance is a metric, and that it upper-bounds the p-Wasserstein distance between the associated barcodes. For each p ∈ [1,∞], we prove that this distance is stable with respect to cellular sublevel filtrations and that it is the universal (i.e., largest) distance satisfying this stability property. In the p = ∞ case, this gives a novel proof of universality for the interleaving distance on merge trees.
Cite as

Robert Cardona, Justin Curry, Tung Lam, and Michael Lesnick. The Universal 𝓁^p-Metric on Merge Trees. In 38th International Symposium on Computational Geometry (SoCG 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 224, pp. 24:1-24:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{cardona_et_al:LIPIcs.SoCG.2022.24,
  author =	{Cardona, Robert and Curry, Justin and Lam, Tung and Lesnick, Michael},
  title =	{{The Universal 𝓁^p-Metric on Merge Trees}},
  booktitle =	{38th International Symposium on Computational Geometry (SoCG 2022)},
  pages =	{24:1--24:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-227-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{224},
  editor =	{Goaoc, Xavier and Kerber, Michael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2022.24},
  URN =		{urn:nbn:de:0030-drops-160325},
  doi =		{10.4230/LIPIcs.SoCG.2022.24},
  annote =	{Keywords: merge trees, hierarchical clustering, persistent homology, Wasserstein distances, interleavings}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2022.58
The Degree-Rips Complexes of an Annulus with Outliers

Authors: Alexander Rolle

Published in: LIPIcs, Volume 224, 38th International Symposium on Computational Geometry (SoCG 2022)

Abstract
The degree-Rips bifiltration is the most computable of the parameter-free, density-sensitive bifiltrations in topological data analysis. It is known that this construction is stable to small perturbations of the input data, but its robustness to outliers is not well understood. In recent work, Blumberg-Lesnick prove a result in this direction using the Prokhorov distance and homotopy interleavings. Based on experimental evaluation, they argue that a more refined approach is desirable, and suggest the framework of homology inference. Motivated by these experiments, we consider a probability measure that is uniform with high density on an annulus, and uniform with low density on the disc inside the annulus. We compute the degree-Rips complexes of this probability space up to homotopy type, using the Adamaszek-Adams computation of the Vietoris-Rips complexes of the circle. These degree-Rips complexes are the limit objects for the Blumberg-Lesnick experiments. We argue that the homology inference approach has strong explanatory power in this case, and suggest studying the limit objects directly as a strategy for further work.
Cite as

Alexander Rolle. The Degree-Rips Complexes of an Annulus with Outliers. In 38th International Symposium on Computational Geometry (SoCG 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 224, pp. 58:1-58:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{rolle:LIPIcs.SoCG.2022.58,
  author =	{Rolle, Alexander},
  title =	{{The Degree-Rips Complexes of an Annulus with Outliers}},
  booktitle =	{38th International Symposium on Computational Geometry (SoCG 2022)},
  pages =	{58:1--58:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-227-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{224},
  editor =	{Goaoc, Xavier and Kerber, Michael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2022.58},
  URN =		{urn:nbn:de:0030-drops-160664},
  doi =		{10.4230/LIPIcs.SoCG.2022.58},
  annote =	{Keywords: multi-parameter persistent homology, stability, homology inference}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2021.27
Computing the Multicover Bifiltration

Authors: René Corbet, Michael Kerber, Michael Lesnick, and Georg Osang

Published in: LIPIcs, Volume 189, 37th International Symposium on Computational Geometry (SoCG 2021)

Abstract
Given a finite set A ⊂ ℝ^d, let Cov_{r,k} denote the set of all points within distance r to at least k points of A. Allowing r and k to vary, we obtain a 2-parameter family of spaces that grow larger when r increases or k decreases, called the multicover bifiltration. Motivated by the problem of computing the homology of this bifiltration, we introduce two closely related combinatorial bifiltrations, one polyhedral and the other simplicial, which are both topologically equivalent to the multicover bifiltration and far smaller than a Čech-based model considered in prior work of Sheehy. Our polyhedral construction is a bifiltration of the rhomboid tiling of Edelsbrunner and Osang, and can be efficiently computed using a variant of an algorithm given by these authors as well. Using an implementation for dimension 2 and 3, we provide experimental results. Our simplicial construction is useful for understanding the polyhedral construction and proving its correctness.
Cite as

René Corbet, Michael Kerber, Michael Lesnick, and Georg Osang. Computing the Multicover Bifiltration. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 27:1-27:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{corbet_et_al:LIPIcs.SoCG.2021.27,
  author =	{Corbet, Ren\'{e} and Kerber, Michael and Lesnick, Michael and Osang, Georg},
  title =	{{Computing the Multicover Bifiltration}},
  booktitle =	{37th International Symposium on Computational Geometry (SoCG 2021)},
  pages =	{27:1--27:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-184-9},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{189},
  editor =	{Buchin, Kevin and Colin de Verdi\`{e}re, \'{E}ric},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021.27},
  URN =		{urn:nbn:de:0030-drops-138260},
  doi =		{10.4230/LIPIcs.SoCG.2021.27},
  annote =	{Keywords: Bifiltrations, nerves, higher-order Delaunay complexes, higher-order Voronoi diagrams, rhomboid tiling, multiparameter persistent homology, denoising}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2020.64
Fast Algorithms for Minimum Cycle Basis and Minimum Homology Basis

Authors: Abhishek Rathod

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

Abstract
We study the problem of finding a minimum homology basis, that is, a shortest set of cycles that generates the 1-dimensional homology classes with ℤ₂ coefficients in a given simplicial complex K. This problem has been extensively studied in the last few years. For general complexes, the current best deterministic algorithm, by Dey et al. [Dey et al., 2018], runs in O(N^ω + N² g) time, where N denotes the number of simplices in K, g denotes the rank of the 1-homology group of K, and ω denotes the exponent of matrix multiplication. In this paper, we present two conceptually simple randomized algorithms that compute a minimum homology basis of a general simplicial complex K. The first algorithm runs in Õ(m^ω) time, where m denotes the number of edges in K, whereas the second algorithm runs in O(m^ω + N m^{ω-1}) time. We also study the problem of finding a minimum cycle basis in an undirected graph G with n vertices and m edges. The best known algorithm for this problem runs in O(m^ω) time. Our algorithm, which has a simpler high-level description, but is slightly more expensive, runs in Õ(m^ω) time.
Cite as

Abhishek Rathod. Fast Algorithms for Minimum Cycle Basis and Minimum Homology Basis. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 64:1-64:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{rathod:LIPIcs.SoCG.2020.64,
  author =	{Rathod, Abhishek},
  title =	{{Fast Algorithms for Minimum Cycle Basis and Minimum Homology Basis}},
  booktitle =	{36th International Symposium on Computational Geometry (SoCG 2020)},
  pages =	{64:1--64:11},
  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.64},
  URN =		{urn:nbn:de:0030-drops-122223},
  doi =		{10.4230/LIPIcs.SoCG.2020.64},
  annote =	{Keywords: Computational topology, Minimum homology basis, Minimum cycle basis, Simplicial complexes, Matrix computations}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2019.37
Chunk Reduction for Multi-Parameter Persistent Homology

Authors: Ulderico Fugacci and Michael Kerber

Published in: LIPIcs, Volume 129, 35th International Symposium on Computational Geometry (SoCG 2019)

Abstract
The extension of persistent homology to multi-parameter setups is an algorithmic challenge. Since most computation tasks scale badly with the size of the input complex, an important pre-processing step consists of simplifying the input while maintaining the homological information. We present an algorithm that drastically reduces the size of an input. Our approach is an extension of the chunk algorithm for persistent homology (Bauer et al., Topological Methods in Data Analysis and Visualization III, 2014). We show that our construction produces the smallest multi-filtered chain complex among all the complexes quasi-isomorphic to the input, improving on the guarantees of previous work in the context of discrete Morse theory. Our algorithm also offers an immediate parallelization scheme in shared memory. Already its sequential version compares favorably with existing simplification schemes, as we show by experimental evaluation.
Cite as

Ulderico Fugacci and Michael Kerber. Chunk Reduction for Multi-Parameter Persistent Homology. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 37:1-37:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{fugacci_et_al:LIPIcs.SoCG.2019.37,
  author =	{Fugacci, Ulderico and Kerber, Michael},
  title =	{{Chunk Reduction for Multi-Parameter Persistent Homology}},
  booktitle =	{35th International Symposium on Computational Geometry (SoCG 2019)},
  pages =	{37:1--37:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-104-7},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{129},
  editor =	{Barequet, Gill and Wang, Yusu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019.37},
  URN =		{urn:nbn:de:0030-drops-104413},
  doi =		{10.4230/LIPIcs.SoCG.2019.37},
  annote =	{Keywords: Multi-parameter persistent homology, Matrix reduction, Chain complexes}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2019.46
Exact Computation of the Matching Distance on 2-Parameter Persistence Modules

Authors: Michael Kerber, Michael Lesnick, and Steve Oudot

Published in: LIPIcs, Volume 129, 35th International Symposium on Computational Geometry (SoCG 2019)

Abstract
The matching distance is a pseudometric on multi-parameter persistence modules, defined in terms of the weighted bottleneck distance on the restriction of the modules to affine lines. It is known that this distance is stable in a reasonable sense, and can be efficiently approximated, which makes it a promising tool for practical applications. In this work, we show that in the 2-parameter setting, the matching distance can be computed exactly in polynomial time. Our approach subdivides the space of affine lines into regions, via a line arrangement. In each region, the matching distance restricts to a simple analytic function, whose maximum is easily computed. As a byproduct, our analysis establishes that the matching distance is a rational number, if the bigrades of the input modules are rational.
Cite as

Michael Kerber, Michael Lesnick, and Steve Oudot. Exact Computation of the Matching Distance on 2-Parameter Persistence Modules. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 46:1-46:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{kerber_et_al:LIPIcs.SoCG.2019.46,
  author =	{Kerber, Michael and Lesnick, Michael and Oudot, Steve},
  title =	{{Exact Computation of the Matching Distance on 2-Parameter Persistence Modules}},
  booktitle =	{35th International Symposium on Computational Geometry (SoCG 2019)},
  pages =	{46:1--46:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-104-7},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{129},
  editor =	{Barequet, Gill and Wang, Yusu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019.46},
  URN =		{urn:nbn:de:0030-drops-104505},
  doi =		{10.4230/LIPIcs.SoCG.2019.46},
  annote =	{Keywords: Topological Data Analysis, Multi-Parameter Persistence, Line arrangements}
}
  • Refine by Author
  • 4 Lesnick, Michael
  • 3 Kerber, Michael
  • 1 Bauer, Ulrich
  • 1 Cardona, Robert
  • 1 Corbet, René
  • Show More...

  • Refine by Classification
  • 5 Theory of computation → Computational geometry
  • 4 Mathematics of computing → Algebraic topology
  • 1 Computing methodologies → Shared memory algorithms
  • 1 Mathematics of computing → Combinatorial algorithms
  • 1 Mathematics of computing → Mathematical optimization
  • Show More...

  • Refine by Keyword
  • 1 Bifiltrations
  • 1 Chain complexes
  • 1 Computational topology
  • 1 Line arrangements
  • 1 Matrix computations
  • Show More...

  • Refine by Type
  • 7 document

  • Refine by Publication Year
  • 2 2019
  • 2 2022
  • 1 2020
  • 1 2021
  • 1 2023

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