Reconstructing functions from random samples

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

Abstract
Related Papers

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.
[2]	K. Borsuk, On the imbedding of systems of compacta in simplicial complexes, Fundamenta Mathematicae, 35 (1948), 217-234.
[3]	G. Carlsson, Topology and data, Bulletin of the American Mathematical Society, 46 (2009), 255-308. 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, Geometry and Software Systems, (2003), 177-206.
[5]	H. Edelsbrunner and J. L. Harer, Computational Topology - an Introduction, American Mathematical Society, Providence, RI, 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-641. 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-125.
[8]	A. Granas and J. Dugundji, Fixed Point Theory, Springer-Verlag, New York, 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-184. doi: 10.1007/s10208-013-9145-0.
[10]	T. Kaczynski, K. Mischaikow and M. Mrozek, Computational Homology, Springer-Verlag, New York, 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, Menlo Park, 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-441. 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-610. doi: 10.1090/S0002-9939-1957-0087106-9.
[15]	E. H. Spanier, Algebraic Topology, Springer-Verlag, New York, 1981. Corrected reprint.

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.
[2]	K. Borsuk, On the imbedding of systems of compacta in simplicial complexes, Fundamenta Mathematicae, 35 (1948), 217-234.
[3]	G. Carlsson, Topology and data, Bulletin of the American Mathematical Society, 46 (2009), 255-308. 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, Geometry and Software Systems, (2003), 177-206.
[5]	H. Edelsbrunner and J. L. Harer, Computational Topology - an Introduction, American Mathematical Society, Providence, RI, 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-641. 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-125.
[8]	A. Granas and J. Dugundji, Fixed Point Theory, Springer-Verlag, New York, 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-184. doi: 10.1007/s10208-013-9145-0.
[10]	T. Kaczynski, K. Mischaikow and M. Mrozek, Computational Homology, Springer-Verlag, New York, 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, Menlo Park, 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-441. 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-610. doi: 10.1090/S0002-9939-1957-0087106-9.
[15]	E. H. Spanier, Algebraic Topology, Springer-Verlag, New York, 1981. Corrected reprint.

[1]	Dongkui Ma, Min Wu. Topological pressure and topological entropy of a semigroup of maps. Discrete and 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 and 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 and Continuous Dynamical Systems - S, 2022, 15 (4) : 727-746. doi: 10.3934/dcdss.2021097
[4]	Dante Carrasco-Olivera, Roger Metzger Alvan, Carlos Arnoldo Morales Rojas. Topological entropy for set-valued maps. Discrete and 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 and 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 and 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 and 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 and Applied Analysis, 2018, 17 (6) : 2813-2844. doi: 10.3934/cpaa.2018133
[9]	Radu Saghin. Note on homology of expanding foliations. Discrete and 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 and 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 and 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 and 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 and Continuous Dynamical Systems - B, 2018, 23 (9) : 3723-3753. doi: 10.3934/dcdsb.2018075
[16]	Octav Cornea and Francois Lalonde. Cluster homology: An overview of the construction and results. Electronic Research Announcements, 2006, 12: 1-12.
[17]	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
[18]	Sahani Pathiraja, Sebastian Reich. Discrete gradients for computational Bayesian inference. Journal of Computational Dynamics, 2019, 6 (2) : 385-400. doi: 10.3934/jcd.2019019
[19]	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
[20]	Xiaoqi Wei, Guo-Wei Wei. Homotopy continuation for the spectra of persistent Laplacians. Foundations of Data Science, 2021, 3 (4) : 677-700. doi: 10.3934/fods.2021017

Impact Factor:

Tools

Metrics

Other articles
by authors

on AIMS
Steve Ferry Konstantin Mischaikow Vidit Nanda
on Google Scholar
Steve Ferry Konstantin Mischaikow Vidit Nanda

[Back to Top]