Advanced Search
Article Contents
Article Contents

Reconstructing functions from random samples

Abstract Related Papers Cited by
  • From a sufficiently large point sample lying on a compact Riemannian submanifold of Euclidean space, one can construct a simplicial complex which is homotopy-equivalent to that manifold with high confidence. We describe a corresponding result for a Lipschitz-continuous function between two such manifolds. That is, we outline the construction of a simplicial map which recovers the induced maps on homotopy and homology groups with high confidence using only finite sampled data from the domain and range, as well as knowledge of the image of every point sampled from the domain. We provide explicit bounds on the size of the point samples required for such reconstruction in terms of intrinsic properties of the domain, the co-domain and the function. This reconstruction is robust to certain types of bounded sampling and evaluation noise.
    Mathematics Subject Classification: Primary: 55U05, 55U10, 55U15; Secondary: 62-07.


    \begin{equation} \\ \end{equation}
  • [1]

    A. Bjorner, Nerves, fibers and homotopy groups, Journal of Combinatorial Theory, Series A, 102 (2003), 88-93.doi: 10.1016/S0097-3165(03)00015-3.


    K. Borsuk, On the imbedding of systems of compacta in simplicial complexes, Fundamenta Mathematicae, 35 (1948), 217-234.


    G. Carlsson, Topology and data, Bulletin of the American Mathematical Society, 46 (2009), 255-308.doi: 10.1090/S0273-0979-09-01249-X.


    J.-G. Dumas, F. Heckenbach, B. D. Saunders and V. Welker, Computing simplicial homology based on efficient Smith normal form algorithms, Proceedings of Algebra, Geometry and Software Systems, (2003), 177-206.


    H. Edelsbrunner and J. L. Harer, Computational Topology - an Introduction, American Mathematical Society, Providence, RI, 2010.


    K. Fischer, B. Gaertner and M. Kutz, Fast-smallest-enclosing-ball computation in high dimensions, Proceedings of the $11^{th}$ Annual European Symposium on Algorithms (ESA), 2832 (2003), 630-641.doi: 10.1007/978-3-540-39658-1_57.


    R. Ghrist, Three examples of applied and computational homology, Nieuw Archief voor Wiskunde, 9 (2008), 122-125.


    A. Granas and J. Dugundji, Fixed Point Theory, Springer-Verlag, New York, 2003.doi: 10.1007/978-0-387-21593-8.


    S. Harker, K. Mischaikow, M. Mrozek and V. Nanda, Discrete Morse theoretic algorithms for computing homology of complexes and maps, Foundations of Computational Mathematics, 14 (2014), 151-184.doi: 10.1007/s10208-013-9145-0.


    T. Kaczynski, K. Mischaikow and M. Mrozek, Computational Homology, Springer-Verlag, New York, 2004.doi: 10.1007/b97315.


    D. Kozlov, Combinatorial Algebraic Topology, Springer, 2008.doi: 10.1007/978-3-540-71962-5.


    J. R. Munkres, Elements of Algebraic Topology, Addison-Wesley, Menlo Park, 1984.


    P. Niyogi, S. Smale and S. Weinberger, Finding the homology of submanifolds with high confidence from random samples, Discrete and Computational Geometry, 39 (2008), 419-441.doi: 10.1007/s00454-008-9053-2.


    S. Smale, A Vietoris mapping theorem for homotopy, Proceedings of the American mathematical society, 8 (1957), 604-610.doi: 10.1090/S0002-9939-1957-0087106-9.


    E. H. Spanier, Algebraic Topology, Springer-Verlag, New York, 1981. Corrected reprint.

  • 加载中

Article Metrics

HTML views() PDF downloads(227) Cited by(0)

Access History

Other Articles By Authors



    DownLoad:  Full-Size Img  PowerPoint