Expected Complexity of Persistence Barcode Computation via Matrix Reduction

Abstract

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.

Version accepted for publication in Journal of Applied and Computational Topology. Extended version of the previous conference article "Average complexity of matrix reduction for clique filtrations" by Giunti, Houry, Kerber