Constructing Simplicial Complexes over Topological Spaces
Milka N Doktorova · 2012
Topological data analysis usually begins by constructing a combinatorial structure, such as a simplicial complex, to approximate the lost topology of a sampled point set. Current techniques often assume the input is embedded in a Euclidean space, so these methods do not extend to non-Euclidean or nonmetric spaces. Moreover, complexes suffer from the curse of dimensionality and may get very large even for small input. In this paper, we present an oracle-based framework and algorithms that construct high-dimensional simplicial complexes over arbitrary topological spaces. Using the minimum-sized representation for the simplicial complexes, we design a novel top-down algorithm and analyze it both theoretically and experimentally. We compare its performance to other algorithmic approaches, building up to 27-dimensional complexes on a standard desktop machine. Finally, we apply our framework to problems from three domains: Google search, word composition, and protein structure.