Expected Complexity of Persistent Homology Computation via Matrix Reduction

arXiv2111.02125MaRDI QIDQ6505233FDOQ6505233

Authors: Barbara Giunti, Guillaume Houry, Michael Kerber, Matthias Söls 

Abstract: We study the algorithmic complexity of computing persistent homology of a randomly chosen filtration. Specifically, we prove upper bounds for the average fill-up (number of non-zero entries) of the boundary matrix on Erd"os-R'enyi and Vietoris-Rips filtrations after matrix reduction. Our bounds show that, in both cases, the reduced matrix is expected to be significantly sparser than what the general worst-case predicts. Our method is based on previous results on the expected first Betti numbers of corresponding complexes. We establish a link between these results to the fill-up of the boundary matrix. Our bound for Vietoris-Rips complexes is asymptotically tight up to logarithmic factors. We also provide an Erd"os-R'enyi filtration realising the worst-case.

This page was built for publication: Expected Complexity of Persistent Homology Computation via Matrix Reduction

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6505233)