Phase Transitions in Random Čech Complexes

Wednesday, October 9, 2013 - 2:00pm - 2:50pm
Keller 3-180
Omer Bobrowski (Duke University)
In manifold learning, one wishes to infer geometric and topological features of an unknown manifold, embedded in a d-dimensional Euclidean space, from a finite (random) point cloud. One topological invariant of a considerable interest is the homology of the underlying space.

A common method for recovering the homology of a manifold from a set of random samples, is to cover each point with a d-dimensional ball, and study the union of these balls. By the Nerve Lemma, this method is equivalent to studying the homology of the Čech complex generated from the random point cloud.

In this talk we discuss the limiting behavior of random Čech complexes, as the sample size goes to infinity, and the radius of the balls goes to zero. We show that the limiting behavior exhibits multiple phase transitions at different levels, depending on the rate at which the radius of the balls goes to zero. We present the different regimes and phase transitions discovered so far, and observe the nicely ordered fashion in which homology groups of different dimensions appear and vanish.

One interesting consequence of this analysis, is a simple sufficient condition under which the random Čech complex successfully recovers the homology of the original manifold.
MSC Code: