Probabilistic convergence and stability of random mapper graphs (Q2240090): Difference between revisions

The Mapper algorithm, first described by \textit{G. Singh}, \textit{F. Mémoli} and \textit{G. Carlsson} in [``Topological methods for the analysis of high dimensional data sets and 3D object recognition'', in: Eurographics Symposium on Point-Based Graphics, 91--100 (2007)], constitutes one of the staples of topological data analysis and is almost omnipresent in topology-driven data analysis applications. Its connection to Reeb spaces (and Reeb graphs) was recently remarked upon. This paper addresses three aspects, namely a formal description of the information captured by Mapper, its stability properties~(with respect to perturbations of the input function but also with respect to perturbations of the input parameters), and its convergence as the number of points goes to infinity. In addition to these formal properties, which are addressed in a probabilistic setting using an auxiliary construction referred to as the \textit{enhanced Mapper graph}, this paper also provides insights about the overall approximation quality of Mapper graphs arising from non-manifold spaces. A concrete algorithm is provided for the enhanced Mapper graph, and its connection to the `classical' Mapper graph is shown.