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

利用数据的力量一直是计算的驱动力，特别是近年来，数据科学的突破使计算机能够执行前所未有的任务。然而，随着数据变得越来越复杂，也越来越需要更先进的技术来揭示数据的隐藏结构。拓扑数据分析（TDA）使用数学分支（即拓扑学）中的工具，旨在揭示传统方法难以捕获的数据的“形状”。然而，TDA中提出的一些重要的数据描述符的计算复杂性并没有得到很好的理解，这是它们更广泛应用的主要障碍。这个项目旨在设计有效的算法来计算这些重要的数据描述符。将开发有效的计算软件，这是促进应用的必要步骤。本项目的两个重点是围绕持久同源性（TDA的基石）及其扩展zigzag持久性的描述符：（i）拓扑持久性的代表;（ii）更新标准和zigzag持久性的葡萄树和葡萄园。将设计专用于计算的新数据结构。通过这项研究，可以在数学对象及其算法解释之间建立更深层次的联系，这可能对TDA的计算前沿产生进一步的影响。该奖项反映了NSF的法定使命，并通过使用基金会的智力评估被认为值得支持优点和更广泛的影响审查标准。

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.