The field of topological data analysis (TDA) has been developed over the last decade, and has already found application in a wide variety of areas, from neuroscience to orthodontia.

A key tool in TDA is the persistence diagram, which provides a compact picture of the multi-scale topoogical information carreid by a point cloud or other embedded object. The algorithm for computing this diagram takes an ordered list of simplices as input, and then reduces a matrix indexed by the simplices. Unfortunately, the number of simplices in practical applications is often extremely high, and so the algorithm is prohibitively expensive, especially when compared with other 'big data' analysis methods.

In this talk, we describe two ways to drastically reduce the number of input simplices, and hence reduce the overall running time of the algorithm. The first algorithm uses ideas from Discrete Morse Theory, returns a correct answer, and achieves large speedups in practice (despite no theoretical results to guarantee this). The second algorithm uses ideas from cover-trees, as well as the algebraic concept of a chain homotopy, to provide a family of approximate diagrams, of guaranteed quality, with theoretical bounds on running time that are achieved in practice. These algorithms, especially when used in tandem, allow for the computation of persistence diagrams on datasets of realistic size.

This is joint work with John Harer, Jurgen Slaczedek, Mauro Maggionni, and Sam Gerber.

Paul Bendich is currently a senior research scientist at Duke University, and was previously at the Institute for Science and Technology Austria. He received his Ph.D. in 2008 from Duke. His research interests include applied algebraic topology, statistics, and machine learning.