Expected Complexity of Persistence Barcode Computation via Matrix Reduction
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2021
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866914020499390464 |
|---|---|
| author | Giunti, Barbara Houry, Guillaume Kerber, Michael Söls, Matthias |
| author_facet | Giunti, Barbara Houry, Guillaume Kerber, Michael Söls, Matthias |
| contents | We study the algorithmic complexity of computing the persistence barcode of a randomly generated filtration. We provide a general technique to bound the expected complexity of reducing the boundary matrix in terms of the density of its reduced form. We apply this technique finding upper bounds for the average fill-in (number of non-zero entries) of the boundary matrix on Čech, Vietoris--Rips and Erdős--Rényi filtrations after matrix reduction, thus obtaining bounds on the expected complexity of the barcode computation. Our method is based on previous results on the expected Betti numbers of the corresponding complexes. Our fill-in bounds for Čech and Vietoris--Rips complexes are asymptotically tight up to a logarithmic factor. In particular, both our fill-in and computation bounds are better than the worst-case estimates. We also provide an Erdős--Rényi filtration realising the worst-case fill-in and computation. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2111_02125 |
| institution | arXiv |
| publishDate | 2021 |
| record_format | arxiv |
| spellingShingle | Expected Complexity of Persistence Barcode Computation via Matrix Reduction Giunti, Barbara Houry, Guillaume Kerber, Michael Söls, Matthias Algebraic Topology Computational Complexity We study the algorithmic complexity of computing the persistence barcode of a randomly generated filtration. We provide a general technique to bound the expected complexity of reducing the boundary matrix in terms of the density of its reduced form. We apply this technique finding upper bounds for the average fill-in (number of non-zero entries) of the boundary matrix on Čech, Vietoris--Rips and Erdős--Rényi filtrations after matrix reduction, thus obtaining bounds on the expected complexity of the barcode computation. Our method is based on previous results on the expected Betti numbers of the corresponding complexes. Our fill-in bounds for Čech and Vietoris--Rips complexes are asymptotically tight up to a logarithmic factor. In particular, both our fill-in and computation bounds are better than the worst-case estimates. We also provide an Erdős--Rényi filtration realising the worst-case fill-in and computation. |
| title | Expected Complexity of Persistence Barcode Computation via Matrix Reduction |
| topic | Algebraic Topology Computational Complexity |
| url | https://arxiv.org/abs/2111.02125 |