Fitting a manifold of large reach to noisy data
Let M⊂Rn be a C2-smooth compact submanifold of dimension d. Assume that the volume of M is at most V and the reach (i.e. the normal injectivity radius) of M is greater than τ. Moreover, let μ be a probability measure on M whose density on M is a strictly positive Lipschitz-smooth function. Let xj∈M, j=1,2,…,N be N independent random samples from distribution μ. Also, let ξj, j=1,2,…,N be independent random samples from a Gaussian random variable in Rn having covariance σ2I, where σ is less than a certain specified function of d,V and τ. We assume that we are given the data points yj=xj+ξj, j=1,2,…,N, modelling random points of M with measurement noise. We develop an algorithm which produces from these data, with high probability, a d dimensional submanifold Mo⊂Rn whose Hausdorff distance to M is less than Cdσ2/τ and whose reach is greater than cτ/d6 with universal constants C,c>0. The number N of random samples required depends almost linearly on n, polynomially on σ−1 and exponentially on d.