
Zigzag Persistence via Reflections and Transpositions
Clément Maria and Steve Y. Oudot
Proc. ACMSIAM Symposium on Discrete Algorithms (SODA),
January 2015.
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 worstcase 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 "weakdiamond", 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{mozzpvrt14conf
, author = "Cl\'ement Maria and Steve Y. Oudot"
, title = "{Z}igzag {Persistence} via {R}eflections and {T}ranspositions"
, booktitle = "Proc. ACMSIAM Symposium on Discrete Algorithms (SODA)"
, pages = "181199"
, month = "January"
, year = "2015"
}

