Reconstructing functions from random samples

Steve Ferry; Konstantin Mischaikow; Vidit Nanda

doi:10.3934/jcd.2014.1.233

Article Contents

2014, Volume 1, Issue 2: 233-248. Doi: 10.3934/jcd.2014.1.233

This issue Previous Article Necessary and sufficient condition for the global stability of a delayed discrete-time single neuron model Next Article Detecting isolated spectrum of transfer and Koopman operators with Fourier analytic tools

Reconstructing functions from random samples

1.
Department of Mathematics, Rutgers University, Piscataway, NJ 08854
2.
Rutgers University, 110 Frelinghusen Road, Piscataway, NJ 08854
3.
Department of Mathematics, University of Pennsylvania, Philadelphia, PA 19104

Received: May 2012

Revised: May 2013

Published online: December 2014

Abstract / Introduction Related Papers Cited by

Abstract

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:

Mathematics Subject Classification: Primary: 55U05, 55U10, 55U15; Secondary: 62-07.

Citation:

Related Papers

Cited by

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.