Homological Illusions of Persistence and Stability

Dmitriy Morozov.
Ph.D. Thesis, Duke University, 2008.
PDF Thesis

In this thesis we explore and extend the theory of persistent homology, which captures topological features of a function by pairing its critical values. The result is represented by a collection of points in the extended plane called persistence diagram.

We start with the question of ridding the function of topological noise as suggested by its persistence diagram. We give an algorithm for hierarchically finding such epsilon-simplifications on 2-manifolds as well as answer the question of when it is impossible to simplify a function in higher dimensions.

We continue by examining time-varying functions. The original algorithm computes the persistence pairing from an ordering of the simplices in a triangulation and takes worst-case time cubic in the number of simplices. We describe how to maintain the pairing in linear time per transposition of consecutive simplices. A side effect of the update algorithm is an elementary proof of the stability of persistence diagrams. We introduce a parametrized family of persistence diagrams called persistence vineyards and illustrate the concept with a vineyard describing a folding of a small peptide. We also base a simple algorithm to compute the rank invariant of a collection of functions on the update procedure.

Guided by the desire to reconstruct stratified spaces from noisy samples, we use the vineyard of the distance function restricted to a 1-parameter family of neighborhoods of a point to assess the local homology of a sampled stratified space at that point. We prove the correctness of this assessment under the assumption of a sufficiently dense sample. We also give an algorithm that constructs the vineyard and makes the local assessment in time at most cubic in the size of the Delaunay triangulation of the point sample.

Finally, to refine the measurement of local homology the thesis extends the notion of persistent homology to sequences of kernels, images, and cokernels of maps induced by inclusions in a filtration of pairs of spaces. Specifically, we note that persistence in this context is well defined, we prove that the persistence diagrams are stable, and we explain how to compute them. Additionally, we use image persistence to cope with functions on noisy domains.

Power cell
Paul Bendich, David Cohen-Steiner, Herbert Edelsbrunner, John Harer, and Dmitriy Morozov. Inferring Local Homology from Sampled Stratified Spaces. Proceedings of the Symposium on Foundations of Computer Science, pages 536-546, Providence, Rhode Island, October 2007.
David Cohen-Steiner, Herbert Edelsbrunner and John Harer. Stability of persistence diagrams. In "Proc. 21st Ann. Sympos. Comput. Geom., 2005", 263-271.
David Cohen-Steiner, Herbert Edelsbrunner, John Harer, and Dmitriy Morozov. Persistent Homology for Kernels, Images, and Cokernels. Manuscript, Department of Computer Science, Duke University, Durham, North Carolina, 2008.
David Cohen-Steiner, Herbert Edelsbrunner and Dmitriy Morozov. Vines and vineyards by updating persistence in linear time. Proceedings of the 22nd Annual ACM Symposium on Computational Geometry, pages 119-126, New York, NY, USA, 2006.
Herbert Edelsbrunner, David Letscher and Afra Zomorodian. Topological persistence and simplification. Discrete Comput. Geom. 28 (2002), 511-533.
Herbert Edelsbrunner, Valerio Pascucci, and Dmitriy Morozov. Persistence-Sensitive Simplification of Functions on 2-Manifolds. Proceedings of the Annual Symposium on Computational Geometry, pages 127-134, New York, New York, June 2006.