2021/04/25 by Matthew Piekenbrock, Piekenbrock, Matthew, José A. Perea +1 · 1 citation
Computer Science · Medicine · #55-08 (Secondary) #68Uxx (Primary) 55N31 #Advanced Neuroimaging Techniques and Applications #Algebraic Topology (math.AT) #Computational Geometry (cs.CG) #Data Visualization and Analytics #FOS: Computer and information sciences #FOS: Mathematics #Topological and Geometric Data Analysis
paper · pdf · doi:10.48550/arxiv.2104.12285
openalex publication_date 2021/04/25 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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(m2) 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.