TY - GEN
T1 - Average Complexity of Matrix Reduction for Clique Filtrations
AU - Giunti, Barbara
AU - Houry, Guillaume
AU - Kerber, Michael
N1 - Publisher Copyright: © 2022 Owner/Author.
PY - 2022/7/4
Y1 - 2022/7/4
N2 - 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.
AB - 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.
KW - average complexity
KW - matrix reduction
KW - persistence algorithm
UR - https://www.scopus.com/pages/publications/85134250354
U2 - 10.1145/3476446.3535474
DO - 10.1145/3476446.3535474
M3 - Conference contribution
T3 - Proceedings of the International Symposium on Symbolic and Algebraic Computation, ISSAC
SP - 187
EP - 196
BT - ISSAC 2022 - Proceedings of the 2022 International Symposium on Symbolic and Algebraic Computation47th International Symposium on Symbolic and Algebraic Computation, ISSAC 2022
A2 - Hashemi, Amir
PB - Association for Computing Machinery
T2 - 47th International Symposium on Symbolic and Algebraic Computation, ISSAC 2022
Y2 - 4 July 2022 through 7 July 2022
ER -