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, 102 (2003), 88.  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.   Google Scholar

[3]

G. Carlsson, Topology and data,, Bulletin of the American Mathematical Society, 46 (2009), 255.  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, (2003), 177.   Google Scholar

[5]

H. Edelsbrunner and J. L. Harer, Computational Topology - an Introduction,, American Mathematical Society, (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.  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.   Google Scholar

[8]

A. Granas and J. Dugundji, Fixed Point Theory,, Springer-Verlag, (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.  doi: 10.1007/s10208-013-9145-0.  Google Scholar

[10]

T. Kaczynski, K. Mischaikow and M. Mrozek, Computational Homology,, Springer-Verlag, (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, (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.  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.  doi: 10.1090/S0002-9939-1957-0087106-9.  Google Scholar

[15]

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

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

[2]

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

[3]

G. Carlsson, Topology and data,, Bulletin of the American Mathematical Society, 46 (2009), 255.  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, (2003), 177.   Google Scholar

[5]

H. Edelsbrunner and J. L. Harer, Computational Topology - an Introduction,, American Mathematical Society, (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.  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.   Google Scholar

[8]

A. Granas and J. Dugundji, Fixed Point Theory,, Springer-Verlag, (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.  doi: 10.1007/s10208-013-9145-0.  Google Scholar

[10]

T. Kaczynski, K. Mischaikow and M. Mrozek, Computational Homology,, Springer-Verlag, (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, (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.  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.  doi: 10.1090/S0002-9939-1957-0087106-9.  Google Scholar

[15]

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

[1]

Eric Babson and Dmitry N. Kozlov. Topological obstructions to graph colorings. Electronic Research Announcements, 2003, 9: 61-68.

[2]

Antonio Rieser. A topological approach to spectral clustering. Foundations of Data Science, 2021  doi: 10.3934/fods.2021005
[3]

M. R. S. Kulenović, J. Marcotte, O. Merino. Properties of basins of attraction for planar discrete cooperative maps. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2721-2737. doi: 10.3934/dcdsb.2020202
[4]

Carlos Gutierrez, Nguyen Van Chau. A remark on an eigenvalue condition for the global injectivity of differentiable maps of $R^2$. Discrete & Continuous Dynamical Systems - A, 2007, 17 (2) : 397-402. doi: 10.3934/dcds.2007.17.397
[5]

Fumihiko Nakamura. Asymptotic behavior of non-expanding piecewise linear maps in the presence of random noise. Discrete & Continuous Dynamical Systems - B, 2018, 23 (6) : 2457-2473. doi: 10.3934/dcdsb.2018055
[6]

Yanqin Fang, Jihui Zhang. Multiplicity of solutions for the nonlinear Schrödinger-Maxwell system. Communications on Pure & Applied Analysis, 2011, 10 (4) : 1267-1279. doi: 10.3934/cpaa.2011.10.1267
[7]

Deren Han, Zehui Jia, Yongzhong Song, David Z. W. Wang. An efficient projection method for nonlinear inverse problems with sparsity constraints. Inverse Problems & Imaging, 2016, 10 (3) : 689-709. doi: 10.3934/ipi.2016017
[8]

Olena Naboka. On synchronization of oscillations of two coupled Berger plates with nonlinear interior damping. Communications on Pure & Applied Analysis, 2009, 8 (6) : 1933-1956. doi: 10.3934/cpaa.2009.8.1933
[9]

Jiangxing Wang. Convergence analysis of an accurate and efficient method for nonlinear Maxwell's equations. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2429-2440. doi: 10.3934/dcdsb.2020185
[10]

Manoel J. Dos Santos, Baowei Feng, Dilberto S. Almeida Júnior, Mauro L. Santos. Global and exponential attractors for a nonlinear porous elastic system with delay term. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2805-2828. doi: 10.3934/dcdsb.2020206
[11]

Thierry Cazenave, Ivan Naumkin. Local smooth solutions of the nonlinear Klein-gordon equation. Discrete & Continuous Dynamical Systems - S, 2021, 14 (5) : 1649-1672. doi: 10.3934/dcdss.2020448
[12]

Scipio Cuccagna, Masaya Maeda. A survey on asymptotic stability of ground states of nonlinear Schrödinger equations II. Discrete & Continuous Dynamical Systems - S, 2021, 14 (5) : 1693-1716. doi: 10.3934/dcdss.2020450
[13]

Irena PawŃow, Wojciech M. Zajączkowski. Global regular solutions to three-dimensional thermo-visco-elasticity with nonlinear temperature-dependent specific heat. Communications on Pure & Applied Analysis, 2017, 16 (4) : 1331-1372. doi: 10.3934/cpaa.2017065
[14]

Xiaoming Wang. Quasi-periodic solutions for a class of second order differential equations with a nonlinear damping term. Discrete & Continuous Dynamical Systems - S, 2017, 10 (3) : 543-556. doi: 10.3934/dcdss.2017027
[15]

Hong Yi, Chunlai Mu, Guangyu Xu, Pan Dai. A blow-up result for the chemotaxis system with nonlinear signal production and logistic source. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2537-2559. doi: 10.3934/dcdsb.2020194

 Impact Factor: 

Tools

Metrics

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

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences