CRII: AF: Efficiently Computing and Updating Topological Descriptors for Data Analysis

Harnessing the power of data has been a driving force for computing, especially in recent years when breakthroughs in data science enable computers to perform tasks never seen before. However, as the data becomes more and more complex, there is also a growing need for more advanced techniques to uncover the hidden structures of data. Using tools in a branch of mathematics, namely topology, Topological Data Analysis (TDA) aims at revealing the 'shape' of data that are otherwise not easily captured by traditional methods. However, the computational complexity of some important data descriptors proposed in TDA is not very well-understood, which is a major obstacle to their wider applications. This project aims at devising efficient algorithms for computing these important data descriptors. Efficient software for the computation will be developed, which is a necessary step for promoting applications. Efforts of the project will help train undergraduate or graduate students by enabling them to cultivate mathematical and algorithmic thinking through the software development process. Two foci of this project are the following descriptors revolving around persistent homology (a cornerstone of TDA) and its extension zigzag persistence: (i) representatives for topological persistence; (ii) vines and vineyard from updating the standard and zigzag persistence. Novel data structures dedicated to the computation will be devised. From the study, a deeper connection between the mathematical objects and their algorithmic interpretation can be established, which can have further implications on the computational front of TDA. 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.