Move Schedules: Fast persistence computations in coarse dynamic settings

• Published in: arXiv.org 2023-10
• Main Authors: Piekenbrock, Matthew, Perea, Jose A
• Format: Article
• Language: English
• Subjects: Algorithms; Computation; Decomposition; Empirical analysis; Homology; Lower bounds; Matrix reduction; Schedules
• ISSN: 2331-8422

Matrix reduction is the standard procedure for computing the persistent homology of a filtered simplicial complex with \(m\) simplices. Its output is a particular decomposition of the total boundary matrix, from which the persistence diagrams and generating cycles are derived. Persistence diagrams are known to vary continuously with respect to their input, motivating the study of their computation for time-varying filtered complexes. Computing persistence dynamically can be reduced to maintaining a valid decomposition under adjacent transpositions in the filtration order. Since there are \(O(m^2)\) such transpositions, this maintenance procedure exhibits limited scalability and is often too fine for many applications. We propose a coarser strategy for maintaining the decomposition over a 1-parameter family of filtrations. By reduction to a particular longest common subsequence problem, we show that the minimal number of decomposition updates \(d\) can be found in \(O(m \log \log m)\) time and \(O(m)\) space, and that the corresponding sequence of permutations -- which we call a schedule -- can be constructed in \(O(d m \log m)\) time. We also show that, in expectation, the storage needed to employ this strategy is actually sublinear in \(m\). Exploiting this connection, we show experimentally that the decrease in operations to compute diagrams across a family of filtrations is proportional to the difference between the expected quadratic number of states and the proposed sublinear coarsening. Applications to video data, dynamic metric space data, and multiparameter persistence are also presented.