Wednesday 16th January 2008

Steve Oudot (INRIA Futur, GEOMETRICA, Saclay, France)

Towards Persistence-Based Reconstruction in Euclidean Space

Abstract
Manifold reconstruction has been extensively studied among the computational geometry community for the last decade or so, especially in two and three dimensions. Recently, significant improvements were made in higher dimensions, leading to new methods to reconstruct large classes of compact subsets of Euclidean space $\R^d$. However, the complexities of these methods scale up exponentially with d, which makes them impractical in medium or high dimensions, even for handling low-dimensional submanifolds. In this talk, we will introduce a novel approach that stands in-between classical reconstruction and topological estimation, and whose complexity scales up with the intrinsic dimension of the data. Specifically, our algorithm combines two paradigms: greedy refinement, and topological persistence. It builds a set of landmarks iteratively, while maintaining nested pairs of complexes, whose images in $\R^d$ lie close to the data, and whose persistent homology eventually coincides with the one of the underlying shape. When the data points are sufficiently densely sampled from a smooth $m$-submanifold of $\R^d$, our method retrieves the homology of the submanifold in time at most $c(m)n5$, where $n$ is the size of the input and $c(m)$ is a constant depending solely on $m$. It can also provably well handle a wide range of compact subsets of $\R^d$, though with worse complexities. Along the way to proving the correctness of our algorithm, we will present new results on \v Cech, Rips, and witness complex filtrations in Euclidean spaces. Specifically, we will show how previous results on unions of balls can be transposed to \v Cech filtrations. Moreover, we will propose a simple framework for studying the properties of filtrations that are intertwined with the \v Cech filtration, among which are the Rips and witness complex filtrations. Finally, we will investigate further on witness complexes and quantify a conjecture of Carlsson and de Silva, which states that witness complex filtrations should have cleaner persistence barcodes than \v Cech or Rips filtrations, at least on smooth submanifolds of Euclidean spaces.