AF: Small: Homological Methods for Big Enough Data

我们如何知道大数据是否足够大？随着算法从数据中做出越来越多的决策，我们也需要这些算法来确保我们的决策是充分知情的，即有足够的数据。同调传感器网络理论是拓扑数据分析的一个分支，最初是为了测试传感器集合是否覆盖感兴趣的领域而创建的，但同样的理论可以测试数据集是否“覆盖”一个潜在的决策空间。同调方法可以补充、扩展甚至取代统计方法，从而使人们对数据集的完备性有信心。由于它们是拓扑的，因此它们可以提供健壮的签名或数据摘要，这些签名或摘要对于广泛的隐式或显式转换是不变的。本项目旨在扩展同调传感器网络的理论和算法基础，使其适用于数据分析。更广泛的影响包括加强理论计算机科学（TCS）和应用代数拓扑之间的联系，扩大拓扑方法和工具适用的数据分析范围。PI将通过在本科和研究生课程中结合组合拓扑的先进概念来培训本科生和研究生的研究人员。PI还将通过说明性视频和开源软件教育更大的TCS和数据分析社区。该建议的具体目的是将同构传感器网络的保证扩展到适用于非光滑集、k覆盖和动态覆盖。第二个具体目标是通过扩展所谓的持久神经定理和定义新的近同胚类来捕捉数据中未知转换的现实，同时仍然提供理论保证，将这些算法结果推回到数据分析问题的抽样理论的理论基础中。第三个具体目标是开发从传统上被称为“拓扑噪声”的信息中提取信息的算法，因为简单的实验表明，尽管它不携带拓扑信息，但它确实携带有用的几何信息，可用于分类和推理。

How do we know if big data is big enough? As algorithms make more and more decisions from data, we also need these algorithms to assure us that the decisions were well-informed, i.e. that enough data went into them. The theory of homological sensor networks, a branch of topological data analysis, was originally created to test if a collection of sensors covers a domain of interest, but the same theory can test if a data set "covers" an underlying decision space. Homological methods can complement, extend, and even replace statistical methods to give confidence in the completeness of a data set. Because they are topological, they can give robust signatures or summaries of data that are invariant to a wide range of implicit or explicit transformations. This project aims to extend the theoretical and algorithmic foundations of the homological sensor networks to be applicable in data analysis. Broader impacts include strengthening connections between theoretical computer science (TCS) and applied algebraic topology, and widening the range of data analyses to which topological methods and tools apply.The PI will train both undergraduate and graduate researchers by incorporating advanced concepts in combinatorial topology in undergraduate and graduate curricula. The PI will also educate the larger TCS and data analysis communities through expository videos and open source software.The specific aim of the proposal is to extend guarantees on homological sensor networks to apply to non-smooth sets, k-coverage, and dynamic coverage. A second specific aim is to push these algorithmic results back into the theoretical foundations of the sampling theories that underlie data analysis problems, by extending the so-called Persistent Nerve Theorem and defining new classes of near-homeomorphisms to capture the realities of unknown transformations in data while still providing theoretical guarantees. The third specific aim is to develop algorithms that extract information from what was traditionally called "topological noise" as simple experiments reveal that although it doesn't carry topological information, it does carry useful geometric information that may be used for classification and inference.