AF:Small: Improved Algorithms for Topological Data Analysis

In recent years, topological data analysis (TDA) has evolved as an emerging area in data science. The technique works by extracting hidden connectivity among the data points dictated by topology. This information is more global in nature and thus become a robust signature for data.

Over the last two decades, this technique has been studied from various angles and has been used to learn from data in a wide variety of applications. However, commonly used algorithms in TDA have been limited to data that vary by a single parameter. To handle more complex and diverse data, extensions of the original notions have started to appear in the TDA literature.

Although a great deal of mathematical theory behind these extensions got developed, the same cannot be said about the algorithmic advances. The main thrust of this project is to address this gap. The resulting TDA methodologies can complement and augment traditional data analysis approaches in fields such as machine learning and statistical data analysis.

The educational aspect of the project will be enriched by the synergy between mathematics and computer science. Graduate students supported by the project will be trained to develop skills in mathematics and theoretical computer science, most notably in algorithms and topology, write efficient and usable software, and analyze real-world data sets. It is planned to provide best practice in recruiting and mentoring students from underrepresented groups.

The research engagement will be broadened via workshops or tutorials. Software tools will be developed for prototypical uses by the research and industrial community. This will not only equip the participants in the project with the twin skill at developing theories alongside coding but also enhance the use of TDA in applications.

Although traditional topological data analysis (TDA) techniques involving 1-parameter persistence is well understood from both mathematical and algorithmic point of view at the moment, the same is not true for its higher order or more general extensions. We propose to study three such extensions in this project, namely, (I) Zigzag persistence which allows not only additions but also deletions in the simplicial filtrations, (II) Multi-parameter persistence which allows more than one parameter akin to multivariate analysis, and (III) Combinatorial dynamical systems persistence which allows merging the theory of persistence with the theory of discretized vector fields.

Each of these three areas is in a stage where mathematics has advanced to a point where more algorithmic ideas are required to bring the mathematical theory to practice. The investigator has actively worked on the algorithmic aspect of TDA and has made significant contributions in that direction. Time is ripe to strengthen this effort to the three extensions mentioned with the overarching goal of developing actionable and practical tools.

The geometric and topological ideas behind the proposed work represent novel directions and inject new ideas and perspectives to the important field of computational data analysis. In particular, the effort is likely to inspire novel mathematical concepts alongside algorithm designs to address various challenges appearing in the aforementioned topics.

This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.