Finding the homology of submanifolds with high confidence from random samples

Research output: Journal Publications and ReviewsRGC 21 - Publication in refereed journalpeer-review

347 Scopus Citations
View graph of relations

Author(s)

Detail(s)

Original languageEnglish
Pages (from-to)419-441
Journal / PublicationDiscrete and Computational Geometry
Volume39
Issue number1-3
Publication statusPublished - Mar 2008
Externally publishedYes

Abstract

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. © 2008 Springer Science+Business Media, LLC.

Citation Format(s)

Finding the homology of submanifolds with high confidence from random samples. / Niyogi, Partha; Smale, Stephen; Weinberger, Shmuel.
In: Discrete and Computational Geometry, Vol. 39, No. 1-3, 03.2008, p. 419-441.

Research output: Journal Publications and ReviewsRGC 21 - Publication in refereed journalpeer-review