Reconstructing functions from random samples
Let \({\mathcal X}\subset{\mathbb R}^n\) be a compact smooth manifold, and \(X\subset{\mathcal X}\) a finite set of independent, identically distributed (i.i.d.) uniformly sampled points. Denote the union of the collection of balls of radius \(\epsilon\) centered at points from \(X\) by \({\mathcal U}_\epsilon(X)\), and denote the nerve of this collection by \(N_\epsilon(X)\). \textit{P. Niyogi} et al. [in: Twentieth anniversary volume: Discrete and computational geometry. New York, NY: Springer. 417--439 (2009; Zbl 1177.62003)] showed that if \(0<\delta\leq 1\), then \({\mathcal U}_{\epsilon}(X)\) is homotopy equivalent to \({\mathcal X}\) with probability of at least \(1-\delta\), provided that the size of \(X\) is sufficiently large (an explicit bound is provided), and that \(\epsilon\) is not too large (an explicit bound, which depends only on the largest radius for which the normal bundle of \({\mathcal X}\) in \({\mathbb R}^n\) is an embedding, is also provided). The authors of the article extend this result to sampled functions between two sampled manifolds. Let \({\mathcal Y}\subset{\mathbb R}^m\) be another compact smooth manifold with i.i.d. uniformly sampled points \(Y\), and \(f:{\mathcal X}\rightarrow{\mathcal Y}\) a Lipschitz continuous function. It is shown that if \(0<\delta_{\mathcal X}\leq 1\) and \(0<\delta_{\mathcal Y}\leq 1\), and if the Lipschitz constant of \(f\) is not too large, then a simplicial map \(\phi:N_{\epsilon_X}(X)\rightarrow N_{\epsilon_Y}(Y)\) that induces the same map as \(f\) in homology with probability at least \((1-\delta_{\mathcal X})(1-\delta_{\mathcal Y})\) can be constructed, provided that the sizes of \(X\) and \(Y\) are sufficiently large, and that \(\epsilon_{\mathcal X}\) and \(\epsilon_{\mathcal Y}\) are not too large. Moreover, the construction involves only \(X\), \(Y\), and the restriction \(f|X\) of \(f\) to \(X\). This result is shown to hold even if the samples are noisy: if \(X\) and \(Y\) are only assumed to lie in \({\mathcal U}_{r_{\mathcal X}}(X)\) and \({\mathcal U}_{r_{\mathcal Y}}(Y)\), respectively, for sufficiently small radii \(r_{\mathcal X}\) and \(r_{\mathcal Y}\), and that the measured values of \(f|X\) are sufficiently close to their actual values.
- A Vietoris Mapping Theorem for Homotopy
- Algorithms - ESA 2003
- Combinatorial algebraic topology
- Computational homology
- Computational topology. An introduction
- Discrete Morse theoretic algorithms for computing homology of complexes and maps
- Finding the homology of submanifolds with high confidence from random samples
- scientific article; zbMATH DE number 4102053 (Why is no real title available?)
- scientific article; zbMATH DE number 1961543 (Why is no real title available?)
- scientific article; zbMATH DE number 3296014 (Why is no real title available?)
- Nerves, fibers and homotopy groups
- On the imbedding of systems of compacta in simplicial complexes
- Three examples of applied and computational homology
- Topology and data
- Čech-Delaunay gradient flow and homology inference for self-maps
- Implicit manifold reconstruction
- Finding the homology of submanifolds with high confidence from random samples
- Recovering a function from a finite number of moments
- Reconstruction of Entire Functions From Irregularly Spaced Sample Points
- Conley index approach to sampled dynamics
- Sampling \(C^1\)-submanifolds of \(\mathbb{H}^n\)
- Spacetimes as topological spaces, and the need to take methods of general topology more seriously
- Implicit manifold reconstruction
- A unified view on the functorial nerve theorem and its variations
- Function recovery on manifolds using scattered data
- Topological inference of the Conley index
- Local reconstruction of a function from a non-uniform sampled data
This page was built for publication: Reconstructing functions from random samples
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2513916)
