Barcodes of towers and a streaming algorithm for persistent homology (Q2415383): Difference between revisions

In this paper the computational problem is to compute the barcode of a given tower efficiently. The authors show that any tower can be efficiently converted into a small filtration with the same barcode. Using a simple variant of their coning strategy, they obtain a filtration whose size is only marginally larger than the length of the tower in the worst case. They also show that a variant of this approach yields a filtration that is asymptotically only marginally larger than the tower and can be efficiently computed by a streaming algorithm, both in theory and in practice. Experimental evaluations show that their approach can efficiently handle towers with billions of complexes. They tested their implementation on various challenging data sets. The source code of the implementation is available at \url{https://bitbucket.org/schreiberh/sophia/} and the software was named Sophia.