Average Complexity of Matrix Reduction for Clique Filtrations
Barbara Giunti, Guillaume Houry, Michael Kerber · 2022
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ös-Rényi 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 a link between the fillup of the boundary matrix and expected Betti numbers of random filtrations. Our bound for Vietoris-Rips complexes is asymptotically tight up to logarithmic factors. We also provide an Erdös-Rényi filtration realising the worst-case.