Minimal Cycle Representatives in Persistent Homology Using Linear Programming: An Empirical Study With User's Guide.
Minimal Cycle Representatives in Persistent Homology Using Linear Programming: An Empirical Study With User's Guide.
复制标题
DOI：
10.3389/frai.2021.681117
复制
发表时间：
2021
影响因子：
4
通讯作者：
Ziegelmeier L
中科院分区：
文献类型：
--
作者：
Li L;Thompson C;Henselman-Petrusek G;Giusti C;Ziegelmeier L
持久同源类的循环代表可以用于提供数据中拓扑特征的描述。然而，这些代表的非唯一性造成了歧义，并可能导致对同一组类的许多不同解释。解决这个问题的一种方法是针对在数据上下文中有意义的一些度量来优化代表的选择。在这项工作中，我们提供了一个研究的有效性和计算成本的几个最小化的优化程序构造的同调循环基的持续同调有理系数在一维，包括均匀加权和长度加权的边缘损失算法，以及均匀加权和面积加权的三角形损失算法。我们通过标准的线性规划方法进行这些优化，应用通用求解器优化单纯边界矩阵的列基。我们的主要发现是：1）优化在减少循环代表的大小方面是有效的，尽管减少的程度根据底层数据的维度和分布而变化，2）在我们考虑的大多数数据集中，优化循环代表的基的计算成本超过计算这样的基的成本，3）线性求解器的选择对优化循环的计算时间很重要，4）对于大多数循环代表，使用Guidelines线性求解器，求解整数规划的计算时间并不显著长于求解线性规划的计算时间，5）引人注目的是，无论是否需要整数解，我们几乎总是获得具有相同成本的解，并且几乎所有找到的解都有条目，因此，也是限制性优化问题的解决方案，6）我们在埃尔德什-雷尼随机团复合体中获得了与真实世界和合成点云数据中的生成元定性不同的结果。
Cycle representatives of persistent homology classes can be used to provide descriptions of topological features in data. However, the non-uniqueness of these representatives creates ambiguity and can lead to many different interpretations of the same set of classes. One approach to solving this problem is to optimize the choice of representative against some measure that is meaningful in the context of the data. In this work, we provide a study of the effectiveness and computational cost of several minimization optimization procedures for constructing homological cycle bases for persistent homology with rational coefficients in dimension one, including uniform-weighted and length-weighted edge-loss algorithms as well as uniform-weighted and area-weighted triangle-loss algorithms. We conduct these optimizations via standard linear programming methods, applying general-purpose solvers to optimize over column bases of simplicial boundary matrices. Our key findings are: 1) optimization is effective in reducing the size of cycle representatives, though the extent of the reduction varies according to the dimension and distribution of the underlying data, 2) the computational cost of optimizing a basis of cycle representatives exceeds the cost of computing such a basis, in most data sets we consider, 3) the choice of linear solvers matters a lot to the computation time of optimizing cycles, 4) the computation time of solving an integer program is not significantly longer than the computation time of solving a linear program for most of the cycle representatives, using the Gurobi linear solver, 5) strikingly, whether requiring integer solutions or not, we almost always obtain a solution with the same cost and almost all solutions found have entries in and therefore, are also solutions to a restricted optimization problem, and 6) we obtain qualitatively different results for generators in Erdős-Rényi random clique complexes than in real-world and synthetic point cloud data.