Fitting a manifold of large reach to noisy data

Let $\mathcal{M}\subset {\mathbb{R}}^n$ be a $C^2$-smooth compact submanifold of dimension $d$. Assume that the volume of $\mathcal{M}$ is at most $V$ and the reach (i.e. the normal injectivity radius) of $\mathcal{M}$ is greater than $\tau$. Moreover, let $\mu$ be a probability measure on $\mathcal{M}$ whose density on $\mathcal{M}$ is a strictly positive Lipschitz-smooth function. Let $x_j\in \mathcal{M}$, $j=1,2,\dots ,N$ be $N$ independent random samples from distribution $\mu$. Also, let ${\xi }_j$, $j=1,2,\dots ,N$ be independent random samples from a Gaussian random variable in ${\mathbb{R}}^n$ having covariance ${\sigma }^{2}I$, where $\sigma$ is less than a certain specified function of $d,V$ and $\tau$. We assume that we are given the data points $y_j=x_j+{\xi }_j,$ $j=1,2,\dots ,N$, modelling random points of $\mathcal{M}$ with measurement noise. We develop an algorithm which produces from these data, with high probability, a $d$ dimensional submanifold ${\mathcal M}_o\subset {\mathbb R}^n$whoseHausdorffdistanceto${\mathcal M}$islessthan$Cd\sigma^2/\tau$andwhosereachisgreaterthan$c{\tau}/d^6$ with universal constants $C,c>0$. The number $N$ of random samples required depends almost linearly on $n$, polynomially on ${\sigma }^{-1}$ and exponentially on $d$.