Therefore, the authors believe that a careful empirical exploration of questions one to three will be of substantial value. For example, while the persistence calculation is known to have matrix multiplication time complexity ( Milosavljević et al., 2011), in practice the computation runs almost always in linear time. However, even where theoretical results are available, strong empirical trends may suggest different or even contrary principles to the practitioner. Given the conceptual and computational complexity of these problems, the authors expect that formal answers are unlikely to be available in the near future. Q3 To what extent does choice of technique matter? For example, how often does the length of a length-weighted optimal cycle match the length of a uniform-weighted optimal cycle? And, how often are ℓ 1 optimal representatives ℓ 0 optimal?
Q2 What are the statistical properties of optimal cycle representatives? For example, how often does the support of a representative form a single loop in the underlying graph? And, how much do optimized cycles coming out of an optimization pipeline differ from the representative that went in? Q1 How do the computational costs of the various optimization techniques compare? How much do these costs depend on the choice of a particular linear solver? While some literature exists to inform this choice ( Dey et al., 2011 Escolar and Hiraoka, 2016 Obayashi, 2018), questions of basic importance remain, including: The problem of finding ℓ 1 optimal cycles with rational coefficients, can be formulated as a more tractable linear programming problem. 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 coefficients is thought to yield the most interpretable results, but ℓ 0 optimization is NP-hard, in general ( Chen and Freedman, 2010b). We conduct these optimizations via standard linear programming methods, applying general-purpose solvers to optimize over column bases of simplicial boundary matrices. In this work, we provide a study of the effectiveness and computational cost of several ℓ 1 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. 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. However, the non-uniqueness of these representatives creates ambiguity and can lead to many different interpretations of the same set of classes. 4Department of Mathematical Sciences, University of Delaware, Newark, DE, United StatesĬycle representatives of persistent homology classes can be used to provide descriptions of topological features in data.3Mathematical Institute, University of Oxford, Oxford, United Kingdom.2Department of Mathematics, Purdue University, West Lafayette, IN, United States.1Mathematics, Statistics, and Computer Science Department, Macalester College, Saint Paul, MN, United States.Lu Li 1, Connor Thompson 2, Gregory Henselman-Petrusek 3, Chad Giusti 4 and Lori Ziegelmeier 1*
0 kommentar(er)
