Niyogi, P.; Smale, S.; Weinberger, S. A topological view of unsupervised learning from noisy data. (English) Zbl 1230.62085 SIAM J. Comput. 40, No. 3, 646-663 (2011). Summary: We take a topological view of unsupervised learning. From this point of view, clustering may be interpreted as trying to find the number of connected components of any underlying geometrically structured probability distribution in a certain sense that we will make precise. We construct a geometrically structured probability distribution that seems appropriate for modeling data in very high dimensions. A special case of our construction is the mixture of Gaussians where there is Gaussian noise concentrated around a finite set of points (the means). More generally we consider Gaussian noise concentrated around a low dimensional manifold and discuss how to recover the homology of this underlying geometric core from data that do not lie on it. We show that if the variance of the Gaussian noise is small in a certain sense, then the homology can be learned with high confidence by an algorithm that has a weak (linear) dependence on the ambient dimension. Our algorithm has a natural interpretation as a spectral learning algorithm using a combinatorial Laplacian of a suitable data-derived simplicial complex. Cited in 46 Documents MSC: 62H30 Classification and discrimination; cluster analysis (statistical aspects) 62-07 Data analysis (statistics) (MSC2010) 68T99 Artificial intelligence 52B55 Computational aspects related to convexity 57N99 Topological manifolds 62G99 Nonparametric inference 65Y20 Complexity and performance of numerical algorithms Keywords:manifolds PDFBibTeX XMLCite \textit{P. Niyogi} et al., SIAM J. Comput. 40, No. 3, 646--663 (2011; Zbl 1230.62085) Full Text: DOI