Algorithms for topological analysis of data

The goal of research presented in this thesis is to develop and implement algorithms which can be used to determine topological structure of large data sets. There are many sources of high dimensional data which are believed to be structured but are hard to visualize. One is often presented with samples from the data which must be associated or connected in order to understand the global picture. Topological analysis is a tool to capture this structure in a qualitative fashion. Two new methods for topological analysis of data are presented: (1) A computational method for extracting simple descriptions of high dimensional data sets in the form of simplicial complexes. The method is called Mapper, and is based on the idea of partial clustering of the data guided by a set of functions defined on the data. The proposed method is not dependent on any particular clustering algorithm. We implement this method and present a few sample applications in which simple descriptions of the data present important information about its structure. (2) An algorithm for determining topological features which persist even when many parameters are varied. The idea of persistence was introduced by Edelsbrunner and colleagues, but it was restricted to the variation of a single spatial parameter for data in up to 3 dimensions. This was later refined to work for any metric space by Carlsson and Zomorodian, but it still only tracked the persistence of features as a spatial scale parameter is varied. The method presented here, called Multidimensional Persistence, tracks persistent topological features even across the variation of many parameters. We present the theoretical structure and details about our implementation of the procedure. We also present a few sample applications where the method is useful.