Abstract:

We introduce a simple algorithm for computing zigzag persistence, designed in the same spirit as the standard persistence algorithm. Our algorithm reduces a single matrix, maintains an explicit set of chains encoding the persistent homology of the current zigzag, and updates it under simplex insertions and removals. The total worst-case running time matches the usual cubic bound.
A noticeable difference with the standard persistence algorithm is that we do not insert or remove new simplices "at the end" of the zigzag, but rather "in the middle". To do so, we use arrow reflections and transpositions, in the same spirit as reflection functors in quiver theory. Our analysis introduces a new kind of reflection called the "weak-diamond", for which we are able to predict the changes in the interval decomposition and associated compatible bases. Arrow transpositions have been studied previously in the context of standard persistent homology, and we extend the study to the context of zigzag persistence. For both types of transformations, we provide simple procedures to update the interval decomposition and associated compatible homology basis.

Bibtex:

@inproceedings{mo-zzpvrt-14-conf
, author = "Cl\'ement Maria and Steve Y. Oudot"
, title =  "{Z}igzag {Persistence} via {R}eflections and {T}ranspositions"
, booktitle = "Proc. ACM-SIAM Symposium on Discrete Algorithms (SODA)"
, pages = "181--199"
, month = "January"
, year = "2015"
}