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]

Fabian Ziltener. Note on coisotropic Floer homology and leafwise fixed points. Electronic Research Archive, , () : -. doi: 10.3934/era.2021001
[2]

Álvaro Castañeda, Pablo González, Gonzalo Robledo. Topological Equivalence of nonautonomous difference equations with a family of dichotomies on the half line. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2020278
[3]

Tian Ma, Shouhong Wang. Topological phase transition III: Solar surface eruptions and sunspots. Discrete & Continuous Dynamical Systems - B, 2021, 26 (1) : 501-514. doi: 10.3934/dcdsb.2020350
[4]

Mark F. Demers. Uniqueness and exponential mixing for the measure of maximal entropy for piecewise hyperbolic maps. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 217-256. doi: 10.3934/dcds.2020217
[5]

Claudio Bonanno, Marco Lenci. Pomeau-Manneville maps are global-local mixing. Discrete & Continuous Dynamical Systems - A, 2021, 41 (3) : 1051-1069. doi: 10.3934/dcds.2020309
[6]

Jann-Long Chern, Sze-Guang Yang, Zhi-You Chen, Chih-Her Chen. On the family of non-topological solutions for the elliptic system arising from a product Abelian gauge field theory. Discrete & Continuous Dynamical Systems - A, 2020, 40 (6) : 3291-3304. doi: 10.3934/dcds.2020127
[7]

Guoyuan Chen, Yong Liu, Juncheng Wei. Nondegeneracy of harmonic maps from $ {{\mathbb{R}}^{2}} $ to $ {{\mathbb{S}}^{2}} $. Discrete & Continuous Dynamical Systems - A, 2020, 40 (6) : 3215-3233. doi: 10.3934/dcds.2019228
[8]

Magdalena Foryś-Krawiec, Jiří Kupka, Piotr Oprocha, Xueting Tian. On entropy of $ \Phi $-irregular and $ \Phi $-level sets in maps with the shadowing property. Discrete & Continuous Dynamical Systems - A, 2021, 41 (3) : 1271-1296. doi: 10.3934/dcds.2020317
[9]

Gunther Uhlmann, Jian Zhai. Inverse problems for nonlinear hyperbolic equations. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 455-469. doi: 10.3934/dcds.2020380
[10]

Predrag S. Stanimirović, Branislav Ivanov, Haifeng Ma, Dijana Mosić. A survey of gradient methods for solving nonlinear optimization. Electronic Research Archive, 2020, 28 (4) : 1573-1624. doi: 10.3934/era.2020115
[11]

Thomas Bartsch, Tian Xu. Strongly localized semiclassical states for nonlinear Dirac equations. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 29-60. doi: 10.3934/dcds.2020297
[12]

Hua Chen, Yawei Wei. Multiple solutions for nonlinear cone degenerate elliptic equations. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2020272
[13]

Eduard Feireisl, Elisabetta Rocca, Giulio Schimperna, Arghir Zarnescu. Weak sequential stability for a nonlinear model of nematic electrolytes. Discrete & Continuous Dynamical Systems - S, 2021, 14 (1) : 219-241. doi: 10.3934/dcdss.2020366
[14]

D. R. Michiel Renger, Johannes Zimmer. Orthogonality of fluxes in general nonlinear reaction networks. Discrete & Continuous Dynamical Systems - S, 2021, 14 (1) : 205-217. doi: 10.3934/dcdss.2020346
[15]

Kimie Nakashima. Indefinite nonlinear diffusion problem in population genetics. Discrete & Continuous Dynamical Systems - A, 2020, 40 (6) : 3837-3855. doi: 10.3934/dcds.2020169
[16]

Matthieu Alfaro, Isabeau Birindelli. Evolution equations involving nonlinear truncated Laplacian operators. Discrete & Continuous Dynamical Systems - A, 2020, 40 (6) : 3057-3073. doi: 10.3934/dcds.2020046
[17]

Abdelghafour Atlas, Mostafa Bendahmane, Fahd Karami, Driss Meskine, Omar Oubbih. A nonlinear fractional reaction-diffusion system applied to image denoising and decomposition. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020321
[18]

Xuefei He, Kun Wang, Liwei Xu. Efficient finite difference methods for the nonlinear Helmholtz equation in Kerr medium. Electronic Research Archive, 2020, 28 (4) : 1503-1528. doi: 10.3934/era.2020079
[19]

Thierry Cazenave, Ivan Naumkin. Local smooth solutions of the nonlinear Klein-gordon equation. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020448
[20]

Zhiyan Ding, Qin Li, Jianfeng Lu. Ensemble Kalman Inversion for nonlinear problems: Weights, consistency, and variance bounds. Foundations of Data Science, 2020  doi: 10.3934/fods.2020018

 Impact Factor: 

Tools

Metrics

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

Other articles
by authors

[Back to Top]

Copyright © 2020 American Institute of Mathematical Sciences