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

Reconstructing functions from random samples

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.
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, 102 (2003), 88. doi: 10.1016/S0097-3165(03)00015-3.

[2]

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

[3]

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

[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, (2003), 177.

[5]

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

[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. doi: 10.1007/978-3-540-39658-1_57.

[7]

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

[8]

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

[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. doi: 10.1007/s10208-013-9145-0.

[10]

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

[11]

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

[12]

J. R. Munkres, Elements of Algebraic Topology,, Addison-Wesley, (1984).

[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. doi: 10.1007/s00454-008-9053-2.

[14]

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

[15]

E. H. Spanier, Algebraic Topology,, Springer-Verlag, (1981).

show all references

References:
[1]

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

[2]

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

[3]

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

[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, (2003), 177.

[5]

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

[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. doi: 10.1007/978-3-540-39658-1_57.

[7]

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

[8]

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

[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. doi: 10.1007/s10208-013-9145-0.

[10]

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

[11]

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

[12]

J. R. Munkres, Elements of Algebraic Topology,, Addison-Wesley, (1984).

[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. doi: 10.1007/s00454-008-9053-2.

[14]

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

[15]

E. H. Spanier, Algebraic Topology,, Springer-Verlag, (1981).

[1]

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

[2]

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

[3]

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

[4]

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

[5]

José S. Cánovas. Topological sequence entropy of $\omega$–limit sets of interval maps. Discrete & Continuous Dynamical Systems - A, 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 - A, 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]

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

[11]

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

[12]

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

[13]

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

[14]

Mickaël D. Chekroun. Topological instabilities in families of semilinear parabolic problems subject to nonlinear perturbations. Discrete & Continuous Dynamical Systems - B, 2018, 22 (11) : 1-30. doi: 10.3934/dcdsb.2018075

[15]

Oliver J. Maclaren, Helen M. Byrne, Alexander G. Fletcher, Philip K. Maini. Models, measurement and inference in epithelial tissue dynamics. Mathematical Biosciences & Engineering, 2015, 12 (6) : 1321-1340. doi: 10.3934/mbe.2015.12.1321

[16]

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

[17]

William Chad Young, Adrian E. Raftery, Ka Yee Yeung. A posterior probability approach for gene regulatory network inference in genetic perturbation data. Mathematical Biosciences & Engineering, 2016, 13 (6) : 1241-1251. doi: 10.3934/mbe.2016041

[18]

Sonja Hohloch. Transport, flux and growth of homoclinic Floer homology. Discrete & Continuous Dynamical Systems - A, 2012, 32 (10) : 3587-3620. doi: 10.3934/dcds.2012.32.3587

[19]

Sarah Day; William D. Kalies; Konstantin Mischaikow and Thomas Wanner. Probabilistic and numerical validation of homology computations for nodal domains. Electronic Research Announcements, 2007, 13: 60-73.

[20]

Al Momin. Contact homology of orbit complements and implied existence. Journal of Modern Dynamics, 2011, 5 (3) : 409-472. doi: 10.3934/jmd.2011.5.409

 Impact Factor: 

Metrics

  • PDF downloads (6)
  • HTML views (0)
  • Cited by (0)

Other articles
by authors

[Back to Top]