Debabrota Basu (6/17/20): Epsilon-net induced lazy witness complex for topological data analysis
Title: Epsilon-net induced lazy witness complex for efficient topological data analysis
Abstract: Inefficient scalability of persistent homology computation on simplicial representations restrains practical application of TDA. The lazy witness complex economically defines an approximate representation using a few selected points, called landmarks. Though landmarks dictate the effectiveness and efficiency of this approximation, the literature lacked any landmark selection method with theoretical guarantees. We address this problem by defining "epsilon-net", which is an adoption of epsilon-cover. We prove that epsilon-net, as a choice of landmarks, is an epsilon-approximate representation and the induced lazy witness complex is a (3log3)-approximation of the induced Rips complex. We prove an upper bound on the size of epsilon-net. Furthermore, we propose iterative algorithms to construct epsilon-net landmarks for point clouds and graphs. These algorithms have log-linear time and linear space complexities with respect to the size of the epsilon-net. Our results improve upon state-of-the-art approximations in complexity and/or approximation ratio.