Finding the homology of submanifolds with high confidence from random samples. (English) Zbl 1148.68048

Summary: 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.


68T05 Learning and adaptive systems in artificial intelligence
60D05 Geometric probability and stochastic geometry
62-07 Data analysis (statistics) (MSC2010)
Full Text: DOI


[1] Amenta, N.; Bern, M., Surface reconstruction by Voronoi filtering, Discrete Comput. Geom., 22, 481-504, (1999) · Zbl 0939.68138
[2] Amenta, N.; Choi, S.; Dey, T. K.; Leekha, N., A simple algorithm for homeomorphic surface reconstruction, Int. J. Comput. Geom. Appl., 12, 125-141, (2002) · Zbl 1152.68653
[3] Belkin, M.; Niyogi, P., Semisupervised learning on Riemannian manifolds, Mach. Learn., 56, 209-239, (2004) · Zbl 1089.68086
[4] Bjorner, A.; Graham, R. (ed.); Grotschel, M. (ed.); Lovasz, L. (ed.), Topological methods, 1819-1872, (1995), Amsterdam · Zbl 0851.52016
[5] Chazal, F., Lieutier, A.: Weak feature size and persistent homology: computing homology of solids in ℝ \(n\) from noisy data samples. Preprint · Zbl 1380.68388
[6] Cheng, S.W., Dey, T.K., Ramos, E.A.: Manifold reconstruction from point samples. In: Proceedings of ACM-SIAM Symposium on Discrete Algorithms, pp. 1018-1027 (2005) · Zbl 1297.68235
[7] Cohen-Steiner, D., Edelsbrunner, H., Harer, J.: Stability of persistence diagrams. In: Proceedings of the 21st Symposium on Computational Geometry, pp. 263-271 (2005) · Zbl 1387.68252
[8] Dey, T. K.; Edelsbrunner, H.; Guha, S.; Chazelle, B. (ed.); Goodman, J. E. (ed.); Pollack, R. (ed.), Computational topology, No. 223, 109-143, (1999), Providence
[9] Do Carmo, M.P.: Riemannian Geometry. Birkhäuser, Basel (1992) · Zbl 0752.53001
[10] Donoho, D., Grimes, C.: Hessian eigenmaps: new locally-linear embedding techniques for high-dimensional data. Preprint. Department of Statistics, Stanford University (2003) · Zbl 1130.62337
[11] Edelsbrunner, H.; Mucke, E. P., Three-dimensional alpha shapes, ACM Trans. Graph., 13, 43-72, (1994) · Zbl 0806.68107
[12] Fischer, K., Gaertner, B., Kutz, M.: Fast smallest-enclosing-ball computation in high dimensions. In: Proceedings of the 11th Annual European Symposium on Algorithms (ESA), pp. 630-641 (2003) · Zbl 1266.68190
[13] Friedman, J., Computing Betti numbers via combinatorial laplacians, Algorithmica, 21, 331-346, (1998) · Zbl 0911.57021
[14] Kaczynski, T., Mischaikow, K., Mrozek, M.: Computational Homology. Springer, New York (2004) · Zbl 1039.55001
[15] Munkres, J.: Elements of Algebraic Topology. Addison-Wesley, Menlo Park (1984) · Zbl 0673.55001
[16] Roweis, S. T.; Saul, L. K., Nonlinear dimensionality reduction by locally linear embedding, Science, 290, 2323-2326, (2000)
[17] Tenenbaum, J. B.; Silva, V.; Langford, J. C., A global geometric framework for nonlinear dimensionality reduction, Science, 290, 2319-2323, (2000)
[18] Valiant, L. G., A theory of the learnable, Commun. ACM, 27, 1134-1142, (1984) · Zbl 0587.68077
[19] Website for smallest enclosing ball algorithm. http://www2.inf.ethz.ch/personal/gaertner/miniball.html
[20] Zomorodian, A.; Carlsson, G., Computing persistent homology, Discrete Comput. Geom., 33, 249-274, (2005) · Zbl 1069.55003
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.