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.