Reconstructing functions from random samples (Q2513916)

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.