American Institute of Mathematical Sciences

Advanced
  • Previous Article
    Detecting isolated spectrum of transfer and Koopman operators with Fourier analytic tools
  • JCD Home
  • This Issue
  • Next Article
    Necessary and sufficient condition for the global stability of a delayed discrete-time single neuron model
June  2014, 1(2): 233-248. doi: 10.3934/jcd.2014.1.233

Reconstructing functions from random samples

Steve Ferry 1, , Konstantin Mischaikow 2, and  Vidit Nanda 3,

1. 

Department of Mathematics, Rutgers University, Piscataway, NJ 08854, United States
2. 

Rutgers University, 110 Frelinghusen Road, Piscataway, NJ 08854, United States
3. 

Department of Mathematics, University of Pennsylvania, Philadelphia, PA 19104, United States

Received  May 2012 Revised  May 2013 Published  December 2014

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.
Keywords: nonlinear maps, Homology, homotopy, topological inference..
Mathematics Subject Classification: Primary: 55U05, 55U10, 55U15; Secondary: 62-0.
Citation: Steve Ferry, Konstantin Mischaikow, Vidit Nanda. Reconstructing functions from random samples. Journal of Computational Dynamics, 2014, 1 (2) : 233-248. doi: 10.3934/jcd.2014.1.233
References:
[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.  Google Scholar

[2]

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

[3]

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

[4]

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.  Google Scholar

[5]

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

[6]

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.  Google Scholar

[7]

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

[8]

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

[9]

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.  Google Scholar

[10]

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

[11]

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

[12]

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

[13]

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.  Google Scholar

[14]

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.  Google Scholar

[15]

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

show all references

References:
[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.  Google Scholar

[2]

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

[3]

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

[4]

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.  Google Scholar

[5]

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

[6]

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.  Google Scholar

[7]

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

[8]

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

[9]

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.  Google Scholar

[10]

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

[11]

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

[12]

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

[13]

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.  Google Scholar

[14]

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.  Google Scholar

[15]

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

[1]

Dongkui Ma, Min Wu. Topological pressure and topological entropy of a semigroup of maps. Discrete & Continuous Dynamical Systems, 2011, 31 (2) : 545-557 . doi: 10.3934/dcds.2011.31.545
[2]

Boris Hasselblatt, Zbigniew Nitecki, James Propp. Topological entropy for nonuniformly continuous maps. Discrete & Continuous Dynamical Systems, 2008, 22 (1&2) : 201-213. doi: 10.3934/dcds.2008.22.201
[3]

Xin Li, Feng Bao, Kyle Gallivan. A drift homotopy implicit particle filter method for nonlinear filtering problems. Discrete & Continuous Dynamical Systems - S, 2021  doi: 10.3934/dcdss.2021097
[4]

Dante Carrasco-Olivera, Roger Metzger Alvan, Carlos Arnoldo Morales Rojas. Topological entropy for set-valued maps. Discrete & Continuous Dynamical Systems - B, 2015, 20 (10) : 3461-3474. doi: 10.3934/dcdsb.2015.20.3461
[5]

José S. Cánovas. Topological sequence entropy of $\omega$–limit sets of interval maps. Discrete & Continuous Dynamical Systems, 2001, 7 (4) : 781-786. doi: 10.3934/dcds.2001.7.781
[6]

José M. Amigó, Ángel Giménez. Formulas for the topological entropy of multimodal maps based on min-max symbols. Discrete & Continuous Dynamical Systems - B, 2015, 20 (10) : 3415-3434. doi: 10.3934/dcdsb.2015.20.3415
[7]

Daniel Wilczak, Piotr Zgliczyński. Topological method for symmetric periodic orbits for maps with a reversing symmetry. Discrete & Continuous Dynamical Systems, 2007, 17 (3) : 629-652. doi: 10.3934/dcds.2007.17.629
[8]

Zalman Balanov, Carlos García-Azpeitia, Wieslaw Krawcewicz. On variational and topological methods in nonlinear difference equations. Communications on Pure & Applied Analysis, 2018, 17 (6) : 2813-2844. doi: 10.3934/cpaa.2018133
[9]

Radu Saghin. Note on homology of expanding foliations. Discrete & Continuous Dynamical Systems - S, 2009, 2 (2) : 349-360. doi: 10.3934/dcdss.2009.2.349
[10]

Joanna Tyrcha, John Hertz. Network inference with hidden units. Mathematical Biosciences & Engineering, 2014, 11 (1) : 149-165. doi: 10.3934/mbe.2014.11.149
[11]

Xueting Tian, Paulo Varandas. Topological entropy of level sets of empirical measures for non-uniformly expanding maps. Discrete & Continuous Dynamical Systems, 2017, 37 (10) : 5407-5431. doi: 10.3934/dcds.2017235
[12]

Ghassen Askri. Li-Yorke chaos for dendrite maps with zero topological entropy and ω-limit sets. Discrete & Continuous Dynamical Systems, 2017, 37 (6) : 2957-2976. doi: 10.3934/dcds.2017127
[13]

Steven M. Pederson. Non-turning Poincaré map and homoclinic tangencies in interval maps with non-constant topological entropy. Conference Publications, 2001, 2001 (Special) : 295-302. doi: 10.3934/proc.2001.2001.295
[14]

Wacław Marzantowicz, Feliks Przytycki. Estimates of the topological entropy from below for continuous self-maps on some compact manifolds. Discrete & Continuous Dynamical Systems, 2008, 21 (2) : 501-512. doi: 10.3934/dcds.2008.21.501
[15]

Mickaël D. Chekroun. Topological instabilities in families of semilinear parabolic problems subject to nonlinear perturbations. Discrete & Continuous Dynamical Systems - B, 2018, 23 (9) : 3723-3753. doi: 10.3934/dcdsb.2018075
[16]

Deng Lu, Maria De Iorio, Ajay Jasra, Gary L. Rosner. Bayesian inference for latent chain graphs. Foundations of Data Science, 2020, 2 (1) : 35-54. doi: 10.3934/fods.2020003
[17]

Sahani Pathiraja, Sebastian Reich. Discrete gradients for computational Bayesian inference. Journal of Computational Dynamics, 2019, 6 (2) : 385-400. doi: 10.3934/jcd.2019019
[18]

Octav Cornea and Francois Lalonde. Cluster homology: An overview of the construction and results. Electronic Research Announcements, 2006, 12: 1-12.

[19]

Xiaoqi Wei, Guo-Wei Wei. Homotopy continuation for the spectra of persistent Laplacians. Foundations of Data Science, 2021  doi: 10.3934/fods.2021017
[20]

Jin-Won Kim, Amirhossein Taghvaei, Yongxin Chen, Prashant G. Mehta. Feedback particle filter for collective inference. Foundations of Data Science, 2021, 3 (3) : 543-561. doi: 10.3934/fods.2021018

 Impact Factor: 

Tools

Metrics

  • PDF downloads (173)
  • HTML views (0)
  • Cited by (3)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences | Privacy Policy