Finding the Homology of Submanifolds with High Confidence from Random Samples

Recently there has been a lot of interest in geometrically motivated approaches to data analysis in high-dimensional spaces. We consider the case where data are drawn from sampling a probability distribution that has support on or near a submanifold of Euclidean space. We show how to “learn” the homology of the submanifold with high confidence. We discuss an algorithm to do this and provide learning-theoretic complexity bounds. Our bounds are obtained in terms of a condition number that limits the curvature and nearness to self-intersection of the submanifold. We are also able to treat the situation where the data are “noisy” and lie near rather than on the submanifold in question. The main results of this paper were first presented at a conference in honor of John Franks and Clark Robinson at Northwestern University in April 2003. These results were formally written as Technical Report No. TR-2004-08, Department of Computer Science, University of Chicago.