Stability and Minimax Optimality of Tangential Delaunay Complexes for Manifold Reconstruction

We consider the problem of optimality in manifold reconstruction. A random sample \(\mathbb {X}_n = \{X_1,\ldots ,X_n\}\subset \mathbb {R}^D\) composed of points close to a d-dimensional submanifold M, with or without outliers drawn in the ambient space, is observed. Based on the tangential Delaunay complex (Discrete Comput Geom 51(1):221–267 2014), we construct an estimator \(\widehat{M}\) that is ambient isotopic and Hausdorff-close to M with high probability. The estimator \(\widehat{M}\) is built from existing algorithms. In a model with additive noise of small amplitude, we show that this estimator is asymptotically minimax optimal for the Hausdorff distance over a class of submanifolds satisfying a reach constraint. Therefore, even with no a priori information on the tangent spaces of M, our estimator based on Tangential Delaunay Complexes is optimal. This shows that the optimal rate of convergence can be achieved through existing algorithms. A similar result is also derived in a model with outliers. A geometric interpolation result is derived, showing that the Tangential Delaunay Complex is stable with respect to noise and perturbations of the tangent spaces. In the process, a decluttering procedure and a tangent space estimator both based on local principal component analysis (PCA) are studied.

We would like to thank Jean-Daniel Boissonnat, Frédéric Chazal, Pascal Massart, and Steve Oudot for their insight and the interest they brought to this work. We are also grateful to the reviewers whose comments helped enhancing substantially this paper. This work was supported by ANR project TopData ANR-13-BS01-0008 and by the Advanced Grant of the European Research Council GUDHI (Geometric Understanding in Higher Dimensions). E. Aamari was supported by the Conseil régional d’Île-de-France under a doctoral allowance of its program Réseau de Recherche Doctoral en Mathématiques de l’Île-de-France (RDM-IdF).

Authors and Affiliations

1. Laboratoire de Mathématiques d’Orsay, Univ. Paris-Sud, CNRS, Université Paris-Saclay, 91405, Orsay, France

   Eddie Aamari

2. DataShape, Inria Saclay, 91120, Palaiseau, France

   Eddie Aamari

3. Université Paris Diderot, 75013, Paris, France

   Clément Levrard

Corresponding author

Correspondence to Eddie Aamari.

Editor in Charge: Kenneth Clarkson

Appendix

A Interpolation Theorem

This section is devoted to prove the interpolation results of Sect. 4.1. For the sake of completeness, let us state a stability result for the reach with respect to \(\mathscr {C}^2\)-diffeomorphisms.

Lemma 7.1

([22, Thm. 4.19]) Let \(A \subset \mathbb {R}^D\) with \(\mathrm {reach}(A) \ge \rho > 0\) and \( \Phi :\mathbb {R}^D \rightarrow \mathbb {R}^D\) be a \(\mathscr {C}^1\)-diffeomorphism such that \( \Phi \),\( \Phi ^{-1}\), and \({d}\Phi \) are Lipschitz with Lipschitz constants K,N and R respectively. Then

Writing \(\phi _\ell (\cdot ) = \phi (\cdot /\ell )\), we recall that \({\psi _j(a)} = (R_j-I_D)(a - \pi (p_j)) + (p_j - \pi (p_j)) \) and

Let us denote \(b_1 = \sup _x \left\| {d}_x \phi \right\| \), \(b_2 = \sup _x \Vert {{d}^2_x \phi }\Vert _\mathrm {op}\), and write \(C_1 = 1+b_1\), \(C_2 = b_2+2b_1\). Straightforward computation yields \(C_1 \le 7/2\) and \(C_2 \le 28\).

Proof of Lemma 4.2

First notice that the sum appearing in (1) consists of at most one term. Indeed, since \(\phi \equiv 0\) outside \(\mathscr {B}(0,1)\), if \(\phi _\ell (a-\pi (p_j) ) \ne 0\) for some \(j \in \{1,\ldots ,q\}\), then \(\Vert {a - \pi (p_j)}\Vert \le \ell \). Consequently, for all \(i \ne j\),

where we used that \( 6 \eta \le \ell \le \delta / 3\). Therefore, \(\phi _\ell (a-\pi (p_i) ) = 0\) for all \(i\ne j\). In other words, if a \(p_j\) actually appears in \(\Phi (a)\) then the others do not.

Global diffeomorphism: As the sum in (1) is at most composed of one term, chain rule yields

where the last line follows from \(b_1 \le 5/2\), \(6 \eta \le \ell \) and \(\theta \le \pi /64\). Therefore, \({d}_a \Phi \) is invertible for all \(a\in \mathbb {R}^D\), and \(({d}_a \Phi )^{-1} = \sum _{i=0}^\infty (I_D- {d}_a \Phi )^i\). \( \Phi \) is a local diffeomorphism according to the local inverse function theorem. Moreover, \(\left\| \Phi (a)\right\| \rightarrow \infty \) as \(\left\| a\right\| \rightarrow \infty \), so that \( \Phi \) is a global \(\mathscr {C^\infty }\)-diffeomorphism by the Hadamard–Cacciopoli theorem [17].

Differentials estimates: (i) First order: From the estimates above,

(ii) Inverse: Write for all \(a \in \mathbb {R}^D\):

where the first inequality holds since \(\left\| {d}_a \Phi - {{I_D}}\right\| _\mathrm {op} < 1\), and \(\left\| \cdot \right\| _\mathrm {op}\) is sub-multiplicative.

(iii) Second order: Again, since the sum (1) includes at most one term,

\(\square \)

Proof of Theorem 4.1

Set \(\ell = \delta /3\) and \(M' = \Phi (M)\).

• Interpolation: For all j, \(p_j = \Phi (\pi (p_j)) \in M'\) by construction since \(\phi _\ell (0)=1\).

• Tangent spaces: Since \({d}_x \phi _l|_{x=0} = 0\), for all \(j \in \{1,\ldots ,q \}\), \({d}_a \Phi |_{a=\pi (p_j)} = R_j\). Thus,

  $$\begin{aligned} T_{p_j} {M}'&= T_{ \Phi (\pi (p_j))} \Phi (M) = {d}_a \Phi |_{a=\pi (p_j)} (T_{\pi (p_j)} M )= R_j (T_{\pi (p_j)} M ) = T_j, \end{aligned}$$

  by definition of \(R_j\).

• Proximity to M: The bound on \(d_H(M,M') = d_H\bigl (M, \Phi (M) \bigr )\) follows from the correspondence

  $$\begin{aligned} \left\| \Phi (a) - a\right\|&\le \sup _{a \in \mathbb {R}^D}\max _{1\le j\le q} \phi _\ell (a-\pi (p_j) ) \left\| \psi _j(a)\right\| \le \ell \theta + \eta \le \delta \theta + \eta . \end{aligned}$$

• Isotopy: Consider the continuous family of maps

  $$\begin{aligned} \Phi _{(t)}(a) = a + t \sum _{j = 1}^q \phi _\ell (a-\pi (p_j) ) {\psi _j(a)} , \end{aligned}$$

  for \(0 \le t \le 1\). Since \( \Phi _{(t)} - {{I_D}} = t ( \Phi - {{I_D}})\), the arguments above show that \( \Phi _{(t)}\) is a global diffeomorphism of \(\mathbb {R}^D\) for all \(t \in [0,1]\). Moreover, \( \Phi _{(0)} = {{I_D}}\) and \( \Phi _{(1)} = \Phi \). Thus, \(M = \Phi _{(0)}(M)\) and \(M' = \Phi _{(1)}(M)\) are ambient isotopic.

• Reach lower bound: The differentials estimates of order 1 and 2 of \( \Phi \) translate into estimates on Lipschitz constants of \( \Phi , \Phi ^{-1}\) and \({d}\Phi \). Applying Lemma 7.1 leads to

  $$\begin{aligned} \mathrm {reach}(M')&\ge \dfrac{( 1-C_1 ({\eta }/{\ell } + \theta ) )^2}{({1+ C_1 ({\eta }/{\ell } + \theta )})/{\rho }+ C_2 ({\eta }/{\ell ^2} +{\theta }/{\ell })}\\&= \rho \cdot \dfrac{( 1-C_1 ({\eta }/{\ell } + \theta ) )^2}{1+ C_1 ({\eta }/{\ell } + \theta )+ C_2 ({\eta }/{\ell ^2} +{\theta }/{\ell }) \rho }. \end{aligned}$$

  Now, replace \(\ell \) by its value \(\delta /3\), and write \(c_1 = 3 C_1 \le 21/2 \le 11\) and \(c_2 = 3^2 C_2 \le 252\). We derive

  $$\begin{aligned} \mathrm {reach}(M')&\ge \biggl (1-2c_1 \biggl (\frac{\eta }{\delta } + \theta \biggr ) \biggr ) \biggl ( 1 - c_1 \biggl (\frac{\eta }{\delta } + \theta \biggr ) - c_2 \biggl (\frac{\eta }{\delta ^2} + \frac{\theta }{\delta } \biggr ) \rho \biggr ) \rho \\&\ge \biggl ( 1 - 3 c_1 \biggl (\frac{\eta }{\delta } + \theta \biggr ) - c_2 \biggl (\frac{\eta }{\delta ^2} + \frac{\theta }{\delta } \biggr ) \rho \biggr ) \rho \\&\ge \biggl ( 1 - (3 c_1 +c_2) \biggl (\frac{\eta }{\delta ^2} + \frac{\theta }{\delta } \biggr ) \rho \biggr ) \rho , \end{aligned}$$

  where for the last line we used that \(\delta / \rho \le 1\). The desired lower bound follows taking \(c_0 = 3c_1+ c_2 \le 285\).

\(\square \)

B Some Geometric Properties under Reach Regularity Condition

1.1 B.1 Reach and Projection on the Submanifold

In this section we state intermediate results that connect the reach condition to orthogonal projections onto the tangent spaces. They are based on the following fundamental result.

Proposition 8.1

([22, Thm. 4.18]) For all x and y in M,

where \((y-x)_{\perp }\) denotes the projection of \(y-x\) onto \(T_x M^{\perp }\).

From Proposition 8.1 we may deduce the following property about trace of Euclidean balls on M.

Proposition 8.2

Let \(x \in \mathbb {R}^D\) be such that \({d}(x,M) = \Delta \le h \le {\rho }/{8}\), and let y denote \(\pi (x)\). Then,

where \(r_h^2 + \Delta ^2 = h^2\), \((r_h^-)^2 = \bigl (1-\frac{ \Delta }{\rho }\bigr )r_h^2\), and \((r_h^+)^2 = \bigl (1+\frac{ 2 \Delta }{\rho }\bigr )r_h^2\).

Proof

Let z be in \(M \cap \mathscr {B}(x,h)\), and denote by \(\delta \) the quantity \(\Vert z-y\Vert \). We may write

hence \(\delta ^2 \le h^2 - \Delta ^2 - 2 \langle z-y,y-x \rangle \). Denote, for u in \(\mathbb {R}^D\), by \(u_\perp \) its projection onto \(T_y M^{\perp }\). Since \(\langle z-y,y-x \rangle = \langle (z-y)_{\perp },y-x \rangle \), Proposition 8.1 ensures that

Since \(\Delta \le h \le \rho /8\), it comes \(\delta ^2 \le (1+2 {\Delta }/{\rho })r_h^2\). On the other hand, (2) and Proposition 8.1 also yield

Hence, if \(\delta ^2 \le \big (1- \frac{\Delta }{\rho } \big )r_h^2\), we have

\(\square \)

Also, the following consequence of Proposition 8.1 will be of particular use in the decluttering procedure.

Proposition 8.3

Let h and \(h_k\) be bandwidths satisfying \(h_k^2/\rho \le h \le h_k\). Let x be such that \(d(x,M) \le h/\sqrt{2}\) and \(\pi _{M} (x) = 0\), and let z be such that \(\Vert z-x\Vert \le h\) and \(d(z,M) \le h_k^2/\rho \). Then

where \(z_{\perp }\) denotes the projection of z onto \(T_0 M^{\perp }\).

Proof

Let y denote \(\pi _M (z)\). The triangle inequality yields \(\Vert y\Vert \le \Vert y-z \Vert + \Vert z-x\Vert + \Vert x\Vert \le h_k^{2}/\rho + (1 + 1/\sqrt{2}) h \le 3 h_k\). Proposition 8.1 ensures that \(\Vert y_{\perp } \Vert \le \Vert y \Vert ^2/(2\rho ) \le (9 h_k^2)/(2\rho )\). Since \(\Vert z_{\perp } \Vert \le \Vert y_{\perp }\Vert + h_k^2/\rho \), we have \(\Vert z_{\perp } \Vert \le 6 h_k^2/\rho \) . \(\square \)

At last, let us prove Lemma 5.4, which gives properties of intersections of ambient slabs with M.

Proof of Lemma 5.4

Set \(k_1=\frac{1}{16(K \vee 1)}\), \(k_2 = \frac{1}{16(K \vee \rho \vee 1)}\), and \(k_3 = k_1 \wedge \frac{\rho k_2}{1+2K} \wedge 1\). For all \(h> 0\), and \(z \in S(x,T,h)\), the triangle inequality yields \(\Vert z-x\Vert \le \Vert \pi _T(z-x)\Vert + \Vert \pi _{T^{\perp }}(z-x)\Vert \le (k_1 + k_2h)h\). Since \(h \le 1\) and \(k_1 + k_2 \le 1/2\), we get \(z \in \mathscr {B}(x,h/2)\).

Now, suppose that \( h/\sqrt{2} \ge {d}(x,M) \ge h^2 / \rho \) and \(\angle (T_{\pi (x)} M, T ) \le K h / \rho \). For short we write \(T_0 = T_{\pi (x)} M\). Let \(z \in S(x,T,h)\), since \(h \le 1\), it comes

with \(k'_1 = k_1 + k_2\). On the other hand

with \(k'_2 = k_1 K/\rho + k_2\). Hence \(S(x,T,h) \subset S'(x,T_0,h)\), for the constants \(k'_1\) and \(k'_2\) defined above. It remains to prove that \(S'(x,T_0,h) \cap M = \emptyset \). To see this, let \(z \in S'(x,T_0,h)\), and \(y = \pi (x)\). Since \(k'_1 + k'_2 \le 1/4\), we have \(\Vert y-z \Vert \le \Vert y-x \Vert + \Vert x-z \Vert \le h(1/\sqrt{2} + 1/4)\). For the normal part, we may write

Since \(k'_2 \le 1/(8\rho )\), we have \(\Vert \pi _{T_0^{\perp }}(z-y) \Vert > \Vert y-z\Vert ^2 /(2\rho )\), hence Proposition 8.1 ensures that \(z \notin M\).

At last, suppose that \(x \in M\) and \(y \in \mathscr {B}(x,k_3h)\cap M\). Since \(k_3 \le k_1\), we have \(\Vert \pi _{T}(y-x)\Vert \le k_1h\). Next, we may write

Since \(y \in M\), Proposition 8.1 entails \(\Vert \pi _{T_0^{\perp }}(y-x) \Vert \le \Vert y-x\Vert ^2/(2\rho ) \le k_3^2 h^2/(2\rho )\). It comes

Hence \(y \in S(x,T,h)\). \(\square \)

1.2 B.2 Reach and Exponential Map

In this section we state results that connect Euclidean and geodesic quantities under reach regularity condition. We start with a result linking reach and principal curvatures.

Proposition 8.4

([30, Prop. 6.1]) For all \(x\in M\), writing \(\textit{II}_x\) for the second fundamental form of M at x, for all unitary \(w\in T_x {M}\), we have \(\left\| \textit{II}_x(w,w)\right\| \le 1/\rho \).

For all \(x \in {M}\) and \(v\in T_x {M}\), let us denote by \(\exp _x(v)\) the exponential map at x of direction v. According to the following proposition, this exponential map turns out to be a diffeomorphism on balls of radius at most \(\pi \rho \).

Proposition 8.5

([1, Corr. 1.4]) The injectivity radius of M is at least \(\pi \rho \).

Denoting by \({d}_M(\cdot ,\cdot )\) the geodesic distance on M, we are in position to connect geodesic and Euclidean distance. In what follows, we fix the constant \(\alpha = 1 + \frac{1}{4 \sqrt{2}}\).

Proposition 8.6

For all \(x,y \in {M}\) such that \(\left\| x-y\right\| \le \rho /4\),

Moreover, writing \(y = \exp _x(r v)\) for \(v\in T_x {M}\) with \(\left\| v\right\| =1\) and \(r \le \rho /4\),

with \(\left\| R(r,v)\right\| \le {r^2}/({2\rho })\).

Proof

The first statement is a direct consequence of Proposition 6.3 in [30]. Let us define \(u(t) =\exp _x(tv) - \exp _x(0) -tv\) and \(w(t) = \exp _x(tv)\) for all \(0\le t \le r\). It is clear that \(u(0) = 0\) and \(u'(0) = 0\). Moreover, \(\Vert {u''(t)}\Vert = \Vert {\textit{II}_{w(t)}(w'(t),w'(t))}\Vert \le 1/\rho \). Therefore, a Taylor expansion at order two gives \(\left\| R(r,v)\right\| = u(r) \le r^2/(2\rho )\). Applying the first statement of the proposition gives \(r\le \alpha \left\| x-y\right\| \). \(\square \)

The next proposition gives bounds on the volume form expressed in polar coordinates in a neighborhood of points of M.

Proposition 8.7

Let \(x \in {M}\) be fixed. Denote by J(r, v) the Jacobian of the volume form expressed in polar coordinates around x, for \(r \le {\rho }/{4}\) and v a unit vector in \(T_x {M}\). In other words, if \(y = \exp _x(rv)\), \(d_yV =J(r,v)\,\, dr dv.\) Then

where \(c_d = 2^{-d}\) and \(C_d=2^d\). As a consequence, if \(\mathscr {B}_M(x,r)\) denotes the geodesic ball of radius r centered at x, then, if \(r \le {\rho }/{4}\),

with \(c'_d = c_d V_d\) and \(C'_d = C_d V_d\), where \(V_d\) denotes the volume of the unit d-dimensional Euclidean ball.

Proof

Denoting \(A_{r,v} = {d}_{rv} \exp _x\), the Area Formula [23, Sect. 3.2.5] asserts that \(J(r,v) = r^{d-1} \sqrt{\det ( A_{r,v}^t A_{r,v} )}\). Note that from Proposition 6.1 in [30] together with the Gauss equation [10, p. 130], the sectional curvatures in M are bounded by \(|\kappa | \le 2/\rho ^2\). Therefore, the Rauch theorem [21, Lemma 5] states that

for all \(w \in T_x {M}\). As a consequence,

Since \(\mathrm{Vol}(\mathscr {B}_M(x,r))= \int _{s=0}^{r} \int _{v \in {\mathscr {S}}_{d-1}} J(s,v)\, ds dv\), where \({\mathscr {S}}_{d-1}\) denotes the unit \((d-1)\)-dimensional sphere, the bounds on the volume easily follow. \(\square \)

C Some Technical Properties of the Statistical Model

1.1 C.1 Covering and Mass

Lemma 9.1

Let \(Q_0 \in \mathscr {U}_M(f_\mathrm{min},f_\mathrm{max})\). Then for all \(p \in {M}\) and \( r \le \rho /4\),

where \(a_d > 0\). As a consequence, for n large enough and for all \(Q \in \mathscr {G}_{D,d,f_\mathrm{min},f_\mathrm{max},\rho ,\sigma }\), with probability larger than \(1-({1}/{n})^{2/d}\),

Similarly, for n large enough and for all \(P \in \mathscr {O}_{D,d,f_\mathrm{min},f_\mathrm{max},\rho ,\beta }\), with probability larger than \(1-({1}/{n})^{2/d}\),

Proof

The first statement is a direct corollary of Proposition 8.7, since for all \(r \le \rho /4\),

where \(a_d\) can be taken to be equal to \(c'_d\) of Proposition 8.7. Let us now prove the second statement. By definition, sample \(X_i \in \mathbb {X}_n\), that has distribution \(Q \in \mathscr {G}_{D,d,f_\mathrm{min},f_\mathrm{max},\rho ,\sigma }\), can be written as \(X_i = Y_i + Z_i\), with \(Y_i\) having distribution \(Q_0 \in \mathscr {G}_{D,d,f_\mathrm{min},f_\mathrm{max},\rho }\), and \(\left\| Z_i\right\| \le \sigma \). From the previous point, letting \(a = a_d f_\mathrm{min}\), \(Q_0\) fulfils the so-called (a, d)-standard assumption of [12] for \(r\le \rho /4\). Looking carefully at the proof of Lemma 10 in [12] shows that its conclusion still holds for measures satisfying the (a, d)-standard assumption for small radii only. Therefore, writing \(\mathbb {Y}_n = \{Y_1,\ldots ,Y_n\}\), for \(r \le \rho /8\) we obtain

The claim follows using that \(d_H(\mathbb {X}_n,\mathbb {Y}_n) \le \sigma \), and setting \(r = C_{d,f_\mathrm{min}} ( {\log n}/{n})^{1/d}\) with \(C_{d,f_\mathrm{min}}^d \frac{a}{2^{d+1}} \ge 1+ 2/d\).

To prove the last point, notice that for all \(k=0,\ldots ,n\), conditionally on the event \(\lbrace |\mathbb {X}_n \cap {M}|=k\rbrace \), \(\mathbb {X}_n \cap {M}\) has the distribution of a k-sample of \(Q_0\). Therefore,

Hence,

whenever \(r\le \rho /8\) and \(a r^d \le 2^d\). Taking \(r = C_{d,f_\mathrm{min}}' \bigl ( \frac{\log n}{\beta n}\bigr )^{1/d}\) with \(C_{d,f_\mathrm{min}}'^d \frac{\beta a}{2^{d+1}} \ge 1+ 2/d\) yields the result. \(\square \)

We now focus on proving Lemma 2.2. For its proof, we need the following piece of notation. For all bounded subsets \(K \subset \mathbb {R}^D\) and \(\varepsilon >0\), we let \(\mathrm {cv}_K(\varepsilon )\) denote the Euclidean covering number of K. That is, \(\mathrm {cv}_K(\varepsilon )\) is the minimal number k of Euclidean open balls of radii \(\varepsilon \) and centered at elements of K that are needed to cover K.

Lemma 9.2

Let \(K \subset \mathbb {R}^D\) be a bounded subset. If K is path connected, then for all \(\varepsilon >0\), \(\mathrm {diam}(K) \le 2\varepsilon \mathrm {cv}_K(\varepsilon )\).

Proof

Let \(p,q \in K\) and \(\gamma :[0,1] \rightarrow K\) be a continuous path joining \(\gamma (0) = p\) and \(\gamma (1) = q\). Writing \(N = \mathrm {cv}_K(\varepsilon )\), let \(x_1,\ldots ,x_N \in \mathbb {R}^D\) be the centers of a covering of K by open balls of radii \(\varepsilon \). We let \(U_i\) denote \(\{ t , \left\| \gamma (t) - x_{i}\right\| < \varepsilon \} \subset [0,1]\). By construction of the covering, there exists \(x_{(1)} \in \{x_1,\ldots ,x_N\}\) such that \(\Vert {p - x_{(1)}}\Vert < \varepsilon \). Then \(U_{(1)} \ni \gamma (0) = p\) is a non-empty open subset of [0, 1], so that \(t_{(1)} = \sup U_{(1)}\) is positive. If \(t_{(1)} =1\), then \(\Vert {q-x_{(1)}}\Vert \le \varepsilon \), and in particular \(\left\| q-p\right\| \le 2 \varepsilon \). If \(t_{(1)} < 1\), since \(U_{(1)}\) is an open subset of [0, 1], we see that \(\gamma (t_{(1)}) \notin U_{(1)}\). But \(\bigcup _{i = 1}^N U_i\) is an open cover of [0, 1], which yields the existence of \(U_{(2)}\) such that \(\gamma (t_{(1)}) \in U_{(2)}\), and for all \(t < t_{(1)}\), \(\gamma (t) \notin U_{(2)}\). Then consider \(t_{(2)} = \sup U_{(2)}\), and so on. Doing so, we build by induction a sequence of numbers \(0< t_{(1)}< \cdots < t_{(k)} \le 1\) and distinct centers \(x_{(1)},\ldots ,x_{(k)} \in \{x_1,\ldots ,x_N\}\) (\(k \le N\)) such that \(\Vert {p - x_{(1)}}\Vert < \varepsilon \), \(\Vert {q - x_{(k)}}\Vert \le \varepsilon \), with \(\Vert {\gamma (t_{(i)}) - x_{(i)}}\Vert \le \varepsilon \) for \(1 \le i \le k\) and \(\Vert {\gamma (t_{(i)}) - x_{(i+1)}}\Vert < \varepsilon \) for \(1 \le i \le k-1\). In particular, \(\Vert {x_{(i)} - x_{(i+1)}}\Vert \le 2\varepsilon \) for all \(1\le i \le k-1\). To conclude, write

Since this bound holds for all \(p,q \in K\), we get the announced bound on the diameter of K. \(\square \)

We are now in position to prove Lemma 2.2.

Proof of Lemma 2.2

Let \(\varepsilon \le {\rho }/{4}\), and \(x_1,\ldots ,x_{\mathrm {cv}_M(\varepsilon )}\) be a minimal covering of M. According to Lemma 9.1, for all k,

for some \(a_d > 0\). A straightforward packing argument [12, Sect.  B.1] yields that the covering number of the support M of Q satisfies

for all \(\varepsilon \le {\rho }/{4}\), where \(c_d = 2^d/a_d\). Applying this bound with \(\varepsilon = \rho /4\), together with Lemma 9.2 yields

where \(C_d = 2^{3d-1}/a_d\). \(\square \)

Now we allow for some outliers. We consider a random variable X with distribution P, that can be written as \(X = V(Y+Z) + (1-V)X''\), with \(\Vert Z\Vert \le s h\), \(s \le 1/4\), such that \(\mathbb {P}(V=1) = \beta \) and V is independent from \((Y,Z,X'')\), Y has law Q in \(\mathscr {G}_{D,d,f_\mathrm{min},f_\mathrm{max},\rho }\), and \(X''\) has uniform distribution on \(\mathscr {B}(0,K_0)\) (recall that \(K_0\) is defined below Lemma 2.2). Note that \(s=0\) corresponds to the clutter noise case, whereas \(\beta =1\) corresponds to the additive noise case.

For a fixed point x, let p(x, h) denote \(P(\mathscr {B}(x,h))\). We have \(\mathbb {P}(VY \in \mathscr {B}(x,(1-s)h) ) \le \mathbb {P}(VX \in \mathscr {B}(x,h))\le \mathbb {P}(VY \in \mathscr {B}(x,2h))\). Hence we may write

where \(q(x,h) = Q(\mathscr {B}(x,h))\), and \(q'(x,h)\) = \((h/{K_0})^D\). Bounds on the quantities above are to be found in the following lemma.

Lemma 9.3

There exists \(h_+(\rho ,\beta ,f_\mathrm{min},f_\mathrm{max},d) \le \rho / \sqrt{12d}\) such that, if \(h \le h_+\), for every x such that \({d}(x,M) \le h\), we have

• \(\mathscr {B}(x,2h) \cap M \subset \mathscr {B}(\pi _{{M}}(x),4h) \cap M,\)

• \( q(x,2h) \le C_{d}{ f_\mathrm{max}} h^{d}\).

Moreover, if \({d}(x,M) \le h/\sqrt{2}\), we have

• \(\mathscr {B}(\pi _{{M}}(x),h/8) \cap M \subset \mathscr {B}(x,3h/4)\),

• \(c_{d}{ f_\mathrm{min}} h^d \le q(x,3h/4)\),

• \( p(x,h) \le 2 \beta q(x,2h)\).

Proof

Set \(h_1(\rho ) = \rho /(16 \alpha )\), and let x be such that \({d}(x,{M}) \le h\), and \(h \le h_1\). According to Proposition 8.2, \(\mathscr {B}(x,2h) \cap {M} \subset \mathscr {B}(\pi _{{M}}(x), r_{2h}^+) \cap M\), with \(r_{2h}^+ = \sqrt{(1 + 2 \Delta / \rho )} r_{2h} \le 2 r_{2h} \le 4h\). According to Proposition 8.6, if y \(\in \) \(\mathscr {B}(\pi _M(x),4h) \cap M\), then \(d_M(\pi _M(x),y) \le 4\alpha h \le \rho /4\). Proposition 8.7 then yields \(q(x,2h) \le C_d f_\mathrm{max}h^d\).

Now if \({d}(x,M) \le h/\sqrt{2}\), \(\mathscr {B}(\pi _{{M}}(x),r_{3h/4}^-) \cap M \subset \mathscr {B}(x,3h/4) \cap M\) from Proposition 8.2, with \(r_{3h/4}^- = \sqrt{(1 - \Delta / \rho )}r_{3h/4} \ge r_{3h/4}/2 \ge h/8\). Since we have \(\mathscr {B}_M(\pi _M(x),h/8) \subset \mathscr {B}(\pi _M(x),h/8)\cap M\), a direct application of Proposition 8.7 entails \(c_{d}{ f_\mathrm{min}} h^d \le q(x,3h/4)\).

Applying Proposition 8.7 again, there exists \(h_2(f_\mathrm{min},d,D,\beta ,\rho )\) such that if \(h \le h_1 \wedge h_2\), then for any x such that \({d}(x,{M}) \le h/\sqrt{2}\) we have \((1-\beta ) q'(x,h) \le \beta c_{d,f_\mathrm{min}} h^{d} \), along with \(q(x,2h) \ge q(x,3h/4) \ge c_{d,f_\mathrm{min}} h^{d}\). We deduce that \( p(x,h) \le 2 \beta q(x,2h)\). Taking \(h_+ = h_1 \wedge h_2\wedge \rho / \sqrt{12d}\) leads to the result. \(\square \)

1.2 C.2 Local Covariance Matrices

In this section we describe the shape of the local covariance matrices involved in tangent space estimation. Without loss of generality, the analysis will be conducted for \(\widehat{\Sigma }_1\) (at sample point \(X_1\)), abbreviated as \(\widehat{\Sigma }\). We further assume that \(d(X_1,M) \le h/\sqrt{2}\), \(\pi _{{M}}(X_1) = 0\), and that \(T_{0}{M}\) is spanned by the d first vectors of the canonical basis of \(\mathbb {R}^D\).

The two models (additive noise and clutter noise) will be treated jointly, by considering a random variable X of the form

where \(\mathbb {P}(V=1) = \beta \) and V is independent from \((Y,Z,X'')\), Y has distribution in \(\mathscr {G}_{D,d,f_\mathrm{min},f_\mathrm{max},\rho ,\sigma }\), \(\Vert Z\Vert \le \sigma \), and \(X''\) has uniform law on \(\mathscr {B}(0,K_0)\) (recall that \(K_0\) is defined above Definition 2.4). For short we denote by s the quantity \(\sigma /h\), and recall that we take \(s \le 1/4\), along with \(h \le h_+\) (defined in Lemma 9.3).

Let \(U(X_i,h)\), \(i=2, \ldots , n\), denote \( \mathbb {1}_{\mathscr {B} (X_1,h )}(X_i)\), let \(Y_i \in M\) and \(Z_i\) such that \(X_i = Y_i + Z_i\), with \(\Vert Z_i\Vert \le s h\), and let \(V_2, \ldots V_n\) denote random variables such that \(V_i= 1\) if \(X_i\) is drawn from the signal distribution (see Sect. 2.1). It is immediate that the \((U(X_i,h),V_i)\)’s are independent and identically distributed, with distribution (U(X, h), V).

With a slight abuse of notation, we will denote by \(\mathbb {P}\) and \(\mathbb {E}\) conditional probability and expectation with respect to \(X_1\). The following expectations will be of particular interest.

where for any x in \(\mathbb {R}^D\) \(x_{\top }\) and \(x_{\perp }\) denote respectively the projection of x onto \(T_0 M\) and \(T_0M^{\perp }\).

The following lemma gives useful results on both m(h) and \(\Sigma (h)\), provided that \(X_1\) is close enough to M.

Lemma 9.4

If \(d(X_1,M) \le h/\sqrt{2}\), for \(h \le h_+\), then

with

where \(\mu _{min}(A(h))\) denotes the smallest eigenvalue of A(h). Furthermore,

Proof

Let \(x=y+z\) be in \(B(X_1,h)\), with \(y \in M\) and \(\Vert z\Vert \le s h\). Since \(s \le 1/4\), \(\Vert y\Vert \le 2h\). According to Proposition 8.2 combined with Proposition 8.6, we may write, for \(h \le h_+\) and y in \(\mathscr {B}(X_1 ,2h) \cap {M}\),

in local polar coordinates. Moreover, if \(y \in \mathscr {B}(X_1,(1-s)h)\), then \(x \in \mathscr {B}(X_1,h)\). Then, according to Proposition 8.2, we have \(\mathscr {B}(\pi _{{M}}(X_1),r_{3h/4}^-) \cap M \subset \mathscr {B}(X_1,(1-s)h) \cap M\). Let u be a unit vector in \(T_0 {M}\). Then \(\langle u,x-m_{\top }(h) \rangle ^2\) \(=\) \(\langle u,rv + R(r,v)+z-m_{\top }(h) \rangle ^2\) \(\ge \) \(\langle u,rv -m_{\top }(h) \rangle ^2 /2 - 3 (R(r,v)+z)^2\) \(\ge \) \(\langle u,rv -m_{\top }(h) \rangle ^2 /2-6 r^4/(4\rho ^2) - 6 s^2 h^2\) according to Proposition 8.6. Hence we may write

according to Proposition 8.7 (bound on J(r, v)) and Proposition 8.2 (the geodesic ball \(\mathscr {B}_M(\pi _M(X_1),r_{3h/4}^-)\) is included in the Euclidean ball \(\mathscr {B}(\pi _M(X_1),r_{3h/4}^-)\) \(\subset \) \(\mathscr {B}(X_1,(1-s)h) \cap {M}\)). Then

where \(\sigma _{d-1}\) denotes the surface of the \((d-1)\)-dimensional unit sphere. On the other hand,

Since \(r_{3h/4}^- \le h \le h_+ \le \rho /\sqrt{12d}\), we conclude that

since, for \(d(X_1,M) \le h/\sqrt{2}\) and \(h \le h_+\), \(r_{3h/4}^- \ge r_{3h/4}/2 \ge h/8\), according to Proposition 8.2.

Now, since for any \(x=y+z \in \mathscr {B}(X_1,h)\), y \(\in \) \(M \cap \mathscr {B}(0,2h)\) and \(\Vert z\Vert \le s h\), we have \(\Vert y_{\perp }\Vert \le 2h^2/\rho \), according to Proposition 8.1. Jensen’s inequality yields that \(\Vert m(h)_{\perp }\Vert \le 2h^2/\rho + s h\) and \(\Vert m(h)_{\top }\Vert \le \Vert m(h)\Vert \le 2h\). \(\square \)

The following Lemma 9.5 is devoted to quantifying the deviations of empirical quantities such as local covariance matrices, means and number of points within balls from their deterministic counterparts. To this aim we define \(N_0(h)\) and \(N_1(h)\) as the number of points drawn from respectively noise and signal in \(\mathscr {B}(X_1,h) \cap M\), namely

Lemma 9.5

Recall that \(h_0 = \bigl ( \kappa \frac{\log n}{\beta (n-1)} \bigr )^{1/(d+1)}\) (as defined in Sect. 5.2), and \(h_{\infty } = h_0^{(d+1)/d}\), for \(\kappa \) to be fixed later.

If \(h_0 \le h_+\) and \(d(X_1, M) \le h_+ /\sqrt{2}\), then, with probability larger than \(1- 4 ({1}/{n})^{2/d +1}\), the following inequalities hold, for all \(h \le h_0\).

Moreover, for all \((h_{\infty } \vee \sqrt{2} {d}(X_1,M)) \le h \le h_0\), and n large enough,

Proof

The first two inequalities are straightforward applications of [6, Thm. 5.1]. The proofs of the two last results are detailed below. They are based on Talagrand–Bousquet’s inequality (see, e.g., [8, Thm. 2.3]) combined with the so-called peeling device.

Define \(h_-=(h_{\infty } \vee \sqrt{2} {d}(X_1,M))\), where we recall that in this analysis \(X_1\) is fixed, and let \(f_{T,h}\) denote the function

for \(h_- \le h \le h_0\), T a \(d \times d\) matrix such that \(\Vert T\Vert _{\mathscr {F}}=1\), x in \(\mathbb {R}^D\), v in \(\{0,1\}\), and \(\langle T, B \rangle = \mathrm {trace}(T^t A)\), for any square matrices T and A. Now we define the weighted empirical process

with \(r(h) = \beta q(2h) h^2\), along with the constrained empirical processes

for \(h_- \le u \le h_0\). Since \(\Vert f_{T,h} \Vert _{\infty } \le \sup _{x \in M} \Vert x-m(h)\Vert ^2 U(x,h) \le 4h^2\), and

for \(s \le 1/4\), a direct application of Theorem 2.3 in [8] yields, with probability larger than \(1-e^{-x}\),

To get a bound on \(\mathbb {E} Z(u)\), we introduce some independent Rademacher random variables \(\sigma _2, \ldots , \sigma _n\), i.e., \(\mathbb {P}(\sigma _j =1) = \mathbb {P}(\sigma _j=-1)=1/2\). With a slight abuse of notation, expectations with respect to the \((X_i,V_i)\)’s and \(\sigma _i\)’s, \(i=2, \ldots , n\), will be denoted by \(\mathbb {E}_{(X,V)}\) and \(\mathbb {E}_{\sigma }\) in what follows. According to the symmetrization principle (see, e.g., [7, Lem. 11.4]), we have

For a fixed sequence \((X_i,V_i)\), \(i=2, \ldots , n\), we may write

Jensen’s inequality ensures that

hence

For the term \(E_{11}\), note that, when \((X_i,V_i)_{i=2, \ldots ,n}\) is fixed, \(\sup _{h \le u} \bigl ( \bigl \Vert \sum _{i \ge 2} \sigma _i V_i U(X_i,h) X_i X_i^t \bigr \Vert _{\mathscr {F}} - \mathbb {E}_{\sigma } \bigl \Vert \sum _{i \ge 2} \sigma _i V_i U(X_i,h) X_i X_i^t \bigr \Vert _{\mathscr {F}} \bigr )\) is in fact a supremum of at most \(N_1(u)\) processes. According to the bounded difference inequality (see, e.g., [7, Thm. 6.2]), each of these processes is subGaussian with variance bounded by \(16h^4N_1(u)\) (see Theorem 2.1 of [7]). Hence a maximal inequality for sub-Gaussian random variables (see Sect. 2.5, p. 31, of [7]) ensures that

Hence \(\mathbb {E}_{(X,V)} E_{11} \le 4h^2\sqrt{2 \beta (n-1) q(2u) \log (n-1)}\). \(E_2\) may also be decomposed as

Jensen’s inequality yields that \(E_{22} \le 2u \sqrt{N_1(u)}\), and the same argument as for \(E_{11}\) (expectation of a supremum of \(n-1\) sub-Gaussian processes with variance bounded by \(4u^2N_1(u)\)) gives \(E_{22} \le 2u \sqrt{2 N_1(u) \log (n-1)}\). Hence

Similarly, we may write

At last, we may decompose \(E_4\) as

using the same argument. Combining all these terms leads to

hence we get

To derive a bound on the weighted process Z, we make use of the so-called peeling device (see, e.g., [7, Sect. 13.7, p. 387]). Set \(p = \lceil \log (h_0/h_\infty ) \rceil \le 1 + \log (h_0/h_\infty )\), so that \(e^{-{p}}h_0 \le h_-\). According to Lemma 9.3, if \(I_j\) denotes the slice \([e^{-j}h_0, e^{-(j-1)}h_0] \cap [h_-,h_0]\), then, for every h in \(I_j\), we have

where \(c_d\) depends only on the dimension, provided that \(h_0 \le h_+\). Now we may write

Since \(q(2h_{j-1}) \ge q(2h_-)\), we deduce that

Now, according to Lemma 9.3, \(\beta q(2h_-) \ge c_d \kappa \log n /(n-1)\). On the other hand, \(p \le 1 + \log (h_0/h_\infty ) \le \log (\beta (n-1)/\kappa )/d \le \log n /d\), for \(\kappa \ge 1\). For n large enough, taking \(x = ( 1 + 2/d ) \log n\) in the previous inequality, we get

The last concentration inequality of Lemma 9.5 may be derived the same way, considering the functions

where T is an element of \(\mathbb {R}^d\) satisfying \(\Vert T\Vert \le 1\). \(\square \)

1.3 C.3 Decluttering Rate

In this section we prove that, if the angle between tangent spaces is of order h, then we can distinguish between outliers and signal at order \(h^2\). We recall that the slab S(x, T, h) is the set of points y such that \( \Vert \pi _{T}(y-x) \Vert \le k_1 h\) and \(\Vert \pi _{T^{\perp }}(y-x)\Vert \le k_2h^2\), \(k_1\) and \(k_2\) defined in Lemma 5.4, and where \(\pi _{T}\) denotes the orthogonal projection onto T.

Lemma 9.6

Recall that \(h_0 = \bigl ( \kappa \frac{\log n}{\beta (n-1)} \bigr )^{1/(d+1)}\), and \(h_{\infty } = h_0^{(d+1)/d}\). Let K be fixed, and \(k_1\), \(k_2\) defined accordingly as in Lemma 5.4. If \(h_0 \le h_+\), for \(\kappa \) large enough (depending on d, \(\rho \) and \(f_\mathrm{min}\)) and n large enough, there exists a threshold t such that, for all \(h_{\infty } \le h \le h_0\), we have, with probability larger than \(1-3({1}/{n})^{2/d +1}\),

Proof

Suppose that \(d(X_1,M) \ge h/\sqrt{2} \). Then, according to Lemma 5.4, \(S(X_1,T,h) \subset \mathscr {B}(X_1,h/2)\), with \(\mathscr {B}(X_1, h/2) \cap M = \emptyset \), hence \(P_n(S(X_1,T,h)) \le P_n(\mathscr {B}(X_1,h/2))\). Theorem 5.1 in [6] yields that, for all \(h_{\infty } \le h \le h_0\), with probability larger than \(1-({1}/{n})^{2/d +1}\),

Since \(\log (n)/(n-1) \le \beta h^d/\kappa \), we may write

for n large enough so that \(h \le 1\).

If \(h/ \sqrt{2} \ge d(X_1,M) \ge h^2/\rho \) and \(\angle (T_{\pi (X_1)} M, T ) \le K h / \rho \), then Lemma 5.4 provides a big slab \(S'(x,T_{\pi (x)}M,h)\) so that \(S(x,T,h) \subset S'(x,T_{\pi (x)}M,h)\) and \(S'(x,T_{\pi (x)}M,h) \cap M = \emptyset \). Thus, \(P_n(S(x,T,h)) \le P_n(S'(x,T_{\pi (x)}M,h))\). Another application of Theorem 5.1 in [6] yields that, for all \(h_{\infty } \le h \le h_0\), with probability larger than \(1-({1}/{n})^{2/d +1}\),

hence, denoting by \(\omega _{r}\) the volume of the r-dimensional unit ball, we get

when n is large enough.

Now, if \(X_1 \in M\) and \(\angle (T_{\pi (X_1)} M, T ) \le K h / \rho \), Lemma 5.4 entails that \(\mathscr {B}(X_1,k_3h) \cap M \subset S(X_1,T,h)\), hence \(P_n(S(X_1,T,h)) \ge P_n(\mathscr {B}(X_1,k_3h) \cap M)\). The last application of Theorem 5.1 in [6] yields that, for all \(h_{\infty } \le h \le h_0\), with probability larger than \(1-({1}/{n})^{2/d +1}\),

Thus we deduce that

according to Lemma 9.3 (since \(k_3 \le 1\)). Choosing \(\kappa \) large enough (depending on d, \(\rho \) and \(f_\mathrm{min}\)) and then n large enough leads to the result. \(\square \)

D Matrix Decomposition and Principal Angles

In this section we expose a standard matrix perturbation result, adapted to our framework. For real symmetric matrices, we let \(\mu _i(\cdot )\) denote their i-th largest eigenvalue and \(\mu _\mathrm{min}(\cdot )\) the smallest one.

Theorem 10.1

(Sin \(\theta \) theorem [16], this version from Lemma 19 in [2]) Let \(O \in \mathbb {R}^{D\times D}\), \(B\in \mathbb {R}^{d\times d}\) be positive semi-definite symmetric matrices such that

Let \(T_0\) (resp. T) be the vector space spanned by the first d vectors of the canonical basis (resp. by the first d eigenvectors of O). Then

E Local PCA for Tangent Space Estimation and Decluttering

This section is dedicated to the proofs of Sect. 5. We begin with the case of additive noise (and no outliers), that is Proposition 5.1.

1.1 E.1 Proof of Proposition 5.1

Without loss of generality, the local PCA analysis will be conducted at base point \(X_1\), the results on the whole sample then follow from a standard union bound. For convenience, we assume that \(\pi _M(X_1) = 0\) and that \(T_{0}{M}\) is spanned by the d first vectors of the canonical basis of \(\mathbb {R}^D\). We recall that \(X_i = Y_i + Z_i\), with \(Y_i \in M\) and \(\Vert Z_i\Vert \le s h\), for \(s \le 1/4\). In particular, \(\Vert X_1\Vert \le \Vert Z_1\Vert \le sh \le h/4\).

We adopt the following notation for the local covariance matrix based on the whole sample \(\mathbb {X}_n\).

Note that the tangent space estimator \(\mathtt {TSE}(\mathbb {X}_n,h)_1\) is the space spanned by the first d eigenvectors of \(\widehat{\Sigma }(h)\). From now on we suppose that all the inequalities of Lemma 9.5 are satisfied, defining then a global event of probability larger than \(1-4 ( {1}/{n} )^{2/d + 1}\).

We consider \(h=h_0 \le h_+\), so that Lemmas 9.3 and 9.4 hold. We may then decompose the local covariance matrix as follows.

The first term may be written as

where

According to Lemma 9.4 (with \(\beta =1\)), \(\mu _\mathrm{min}(A(h)) \ge c_d f_\mathrm{min} h^{d+2}\). On the other hand, using Proposition 8.1 and Lemma 9.4 we may write

since \(h \le h_+\) and \(s \le 1/4\). In addition, we can write

with \(\Vert R_2\Vert _{\mathscr {F}} \le C_d \frac{f_\mathrm{max}}{f_\mathrm{min} \sqrt{\kappa }} q(2h) h^2\) according to Lemma 9.5 (with \(\beta =1\)). In turn, the term \(\widehat{\Sigma }_2\) may be decomposed as

with

according to Lemma 9.5. A similar bound on \(R_3\) may be derived,

according to Proposition 8.1 and Lemma 9.4. If we choose \(h = \bigl ( \kappa \frac{\log n}{n-1} \bigr )^{1/d}\), for \(\kappa \) large enough (depending on d, \(f_\mathrm{min}\) and \(f_\mathrm{max}\)), we have

Now, provided that \(\kappa \ge 1\), according to Lemma 9.5, we may write

which, for n large enough, leads to

according to Proposition 10.1.

1.2 E.2 Proof of Proposition 5.5

The proof of Proposition 5.5 follows the same path as the derivation of Proposition 5.1, with some technical difficulties due to the outliers (\(\beta < 1\)). We emphasize that in this framework, there is no additive noise (\(\sigma =0\)). As in the previous section, the analysis will be conducted for \(X_1\) \(\in \) \(\mathbb {X}^{(k)}\), for some fixed \(k \ge -1\), \(k=-1\) referring to the initialization step. Results on the whole sample then follow from a standard union bound. As before, we assume that \(\pi _{{M}}(X_1) = 0\) and that \(T_{0}{M}\) is spanned by the first d vectors of the canonical basis of \(\mathbb {R}^D\). In what follows, denote by \(\widehat{t}\) the map from \(\mathbb {R}^D\) to \(\{0,1\}\) such that \(\widehat{t}(X_i)=1\) if and only if \(X_i\) is in \(\mathbb {X}^{(k)}\).

We adopt the following notation for the local covariance matrix based on \(\mathbb {X}^{(k)}\) (after \(k+1\) iterations of the outlier filtering procedure).

Also recall that we define \(N_0(h)\) and \(N_1(h)\) as the number of points drawn from respectively clutter and signal in \(\mathscr {B}(X_1,h) \cap M\) (based on the whole sample \(\mathbb {X}_n\)). At last, we suppose that all the inequalities of Lemmas 9.5 and 9.6 are satisfied, defining then a global event of probability larger than \(1-7 ( {1}/{n} )^{2/d + 1}\).

We recall that we consider \(h_\infty \le h \le h_{k}\), \(k \ge -1\) (with \(h_{-1} = h_0\)), and \(X_1\) in \(\mathbb {X}^{(k)}\) such that \({d}(X_1,M) \le h/\sqrt{2}\). We may then decompose the local covariance matrix as

The proof of Proposition 5.5 will follow by induction.

Initialization step (\(k=-1\)): In this case \(\mathbb {X}^{(k)} = \mathbb {X}_n\), \(h=h_0\), \({d}(X_1,M) \le h_0/\sqrt{2}\), and \(\widehat{t}\) is always equal to 1. Then the first term \(\widehat{\Sigma }_1^{(k)}\) of (4) may be written as

where

According to Lemma 9.4, \(\mu _\mathrm{min}(A(h)) \ge c_d f_\mathrm{min} \beta h^{d+2}\), and \(\Vert R_1\Vert _{\mathscr {F}} \le 34 \frac{N_1(h) h^3 }{\rho (n-1)}\) according to Proposition 8.1. Moreover, we can write

with \(\Vert R_2\Vert _{\mathscr {F}} \le C_d \frac{f_\mathrm{max}}{f_\mathrm{min} \sqrt{\kappa }} \beta q(2h) h^2\) according to Lemma 9.5. Term \(\widehat{\Sigma }^{(k)}_2\) in inequality (4) may be bounded by

In turn, term \(\widehat{\Sigma }^{(k)}_3\) may be decomposed as

with

according to Lemma 9.5. We may also write

according to Proposition 8.1 and Lemma 9.4. As in the additive noise case (see proof of Proposition 5.1), provided that \(\kappa \) is large enough (depending on d, \(f_\mathrm{min}\), and \(f_\mathrm{max}\)), we have

Since \((n-1)h_0^{d} =\frac{\kappa \log n}{\beta h}\), if we ask \(\kappa \ge \rho \), then for n large enough we eventually get

according to Lemma 9.5. Then, Proposition 10.1 can be applied to obtain

According to Lemma 9.6, we may choose \(\kappa \) large enough (with respect to \(K=\sqrt{2} K^{(0)}\), d, \(f_\mathrm{min}\) and \(\rho \)) and then a threshold t so that, if \(X_1 \in M\), then \(X_1 \in \mathbb {X}^{(0)}\), and if \(d(X_1,M) \ge h_0^2/ \rho \), then \(X_1 \notin \mathbb {X}^{(0)}\).

Iteration step: Now we assume that \(k \ge 0\), and that \({d}(X_i,M) \ge h_k^2/\rho \) implies \(\widehat{t}(X_i)=0\), with \(h_k = \bigl ( \kappa \frac{\log n}{\beta (n-1)} \bigr )^{\gamma _k}\), \(\gamma _k\) being between \(1/(d+1)\) and 1 / d. Let \(h_{\infty } \le h \le h_k\), and suppose that \({d}(X_1,M) \le h_k/\sqrt{2}\). As in the initialization step, \(\widehat{\Sigma }_1^{(k)}\) may be written as

with \(\mu _\mathrm{min}(A(h)) \ge c_d f_\mathrm{min} \beta h^{d+2}\), \(\Vert R_1\Vert _{\mathscr {F}} \le 34 \frac{N_1(h) h^3 }{\rho (n-1)}\), and \(\Vert R_2\Vert _{\mathscr {F}} \le C_d \frac{f_\mathrm{max}}{f_\mathrm{min} \sqrt{\kappa }} \times \beta q(2h) h^2\).

We can decompose \(\widehat{\Sigma }_2^{(k)}\) as

with \(\Vert R_4\Vert _{\mathscr {F}} \le \frac{16N_0(h) h^2}{n-1}\) and \(\Vert R_3\Vert \le \frac{128 N_0(h) h h_k^2}{(n-1)\rho }\), according to Proposition 8.3, for n large enough so that \(h_0^2/\rho \le h_{\infty }\). Term \(\widehat{\Sigma }^{(k)}_3\) may also be written as

with

according to Lemma 9.5. We may also write

according to Propositions 8.1, 8.3 and Lemma 9.4. As done before, we may choose \(\kappa \) large enough (depending on d, \(f_\mathrm{min}\) and \(f_\mathrm{max}\), but not on k) such that

Now choose \(h = h_{k+1} = \bigl ( \kappa \frac{\log n}{\beta (n-1)} \bigr )^{(2\gamma _k +1)/(d+2)}\), with \(\kappa \ge 1\). This choice is made to optimize residual terms of the form \(h/\rho + h_k^2 N_0(h)/h\) coming from \({\Vert R_1 + R_3 + R_5 \Vert _{\mathscr {F}}}/{\mu _\mathrm{min}(A(h_{k+1}))}\). Then we get, according to Lemma 9.5,

where again, \(K_{d,f_\mathrm{min},f_\mathrm{max},\beta }\) does not depend on k. At last, we may apply Proposition 10.1 to get

Then, according to Lemma 9.6, we may choose \(\kappa \) large enough (not depending on k) and t (not depending on k either) so that if \(X_1 \in M\), then \(X_1 \in \mathbb {X}^{(k+1)}\), and if \(d(X_1,M) \ge h_{k}^2/\rho \), then \(X_1 \notin \mathbb {X}^{(k+1)}\). Proposition 5.5 then follows from a straightforward union bound on the sample \(\{X_1, \ldots , X_n\}\).

1.3 E.3 Proof of Proposition 5.8

In this case, we have \({d}(X_j,M) \le h_\infty ^2/\rho \), for every \(X_j\) in \(\mathbb {X}^{(\widehat{k})}\). The proof of Proposition 5.8 follows from the same calculation as in the proof of Proposition 5.5, replacing \(h_k^2/\rho \) by its upper bound \(h_{\infty }^2/\rho \) and taking \(h_{k+1} = h_{\infty }\) in the iteration step.

F Proof of the Main Reconstruction Results

We now prove main results Theorem 2.7 (additive noise model), and Theorems 2.8 and 2.9 (clutter noise model).

1.1 F.1 Additive Noise Model

Proof of Corollary 5.2

Let \( Q \in \mathscr {G}_{D,d,f_\mathrm{min},f_\mathrm{max},\rho ,\sigma }\). Write \(\varepsilon = c_{d,f_\mathrm{min},f_\mathrm{max}} (h \vee \rho \sigma /h)\) for \(c_{d,f_\mathrm{min},f_\mathrm{max}}\) large enough, an consider the event A defined by

Then from Proposition 5.1 and Lemma 9.1, \(\mathbb {P}_Q(A) \ge 1 - 5 \bigl ( \frac{1}{n} \bigr )^{2/d}\), and from the definition of \(\varepsilon \) and the construction of \(\mathbb {Y}_n\), for n large enough,

which yields the result. \(\square \)

Proof of Theorem 2.7

Following the above notation, we observe that on the event A, Theorem 4.4 holds for \(\varepsilon = c_{d,f_\mathrm{min},f_\mathrm{max}} (h \vee \rho \sigma /h)\), \(\theta = \varepsilon /(1140 \rho )\) (where we used the fact that \(\theta \le 2 \sin \theta \)) and \(\eta = \varepsilon ^2/(1140 \rho )\) with high probability, so that the first part of Theorem 2.7 is proven. Furthermore, for n large enough,

where for the last line we used the diameter bound of Lemma 2.2. \(\square \)

1.2 F.2 Clutter Noise Model

Proof of Corollary 5.6

Let \( P \in \mathscr {O}_{D,d,f_\mathrm{min},f_\mathrm{max},\rho ,\beta }\). For n large enough, write \(\varepsilon = c_{d,f_\mathrm{min}f_\mathrm{max}} h_{k_\delta }\) for \(c_{d,f_\mathrm{min}f_\mathrm{max}}\) large enough, and consider the event

From Proposition 5.5 and Lemma 9.1, \(\mathbb {P}_P\bigl (A^\delta \bigr ) \ge 1- 8 ( {1}/{n} )^{2/d}\)and from the definition of \(\varepsilon \) and the construction of \(\mathbb {Y}_n^\delta \), for n large enough,

which yields the result. \(\square \)

Proof of Theorem 2.8

Following the above notation, we observe that on the event \(A^\delta \), Theorem 4.4 holds for \(\varepsilon = c_{d,f_\mathrm{min}f_\mathrm{max}} h_{k_\delta }\), \(\theta = \varepsilon /(1140 \rho )\) and \(\eta = \varepsilon ^2/(1140 \rho )\), so that the first part of Theorem 2.8 is proven. As a consequence, for n large enough,

where for the second line we used the fact that \(M \cup \widehat{M}_\mathtt {TDC \delta } \subset \mathscr {B}_0\), a ball of radius \(K_0 = K_0(d,f_\mathrm{min},\rho )\). \(\square \)

Finally, Theorem 2.9 is obtained similarly using Proposition 5.8.

Reprints and permissions