Adaptive density estimation for directional data using needlets

Introduction

There is an abundant literature about this type of problems. In particular, minimax $L^{2}$ results have been obtained (see [Kle99],[Kle03]). These procedures are generally obtained using either kernel methods (but in this case the manifold structure of the sphere is not well taken into account), or using orthogonal series methods associated with spherical harmonics (and in this case the ’local performances of the estimator are quite poor, since spherical harmonics are spread all over the sphere).

In our approach we focus on two important points. We aim at a procedure of estimation which is efficient from a $L^{2}$ point of view (as it is a tradition in statistics to evaluate the procedure with the mean square error). On the other hand, we would like it to perform satisfactorily also from a local point of view (in infinity norm, for instance). To have these two requirements together seems to us a warrant to have good results in practice. In effect, it is very difficult to produce a loss function which reflects at the same time the requirement of clearly seeing the bumps of the density, of being able to well estimate different level sets, of testing whether there is a difference between the northern and southern hemispheres and so on.

In addition, we require this procedure to be simple to implement, as well as adaptive to inhomogeneous smoothness.

This type of requirements is generally well handled using thresholding estimates associated to wavelets. The problem requires a special construction adapted to the sphere, since usual tensorized wavelets will never reflect the manifold structure of the sphere and will necessarily create unwanted artifacts. Recently in ([NPW06b],[NPW06a]) a tight frame (i.e. a redundant family) was produced which enjoys enough properties to be successfully used for density estimation.

The fundamental properties of wavelets are their concentration in the Fourier domain as well as in the space domain. Here, obviously the ’space’ domain is the sphere itself whereas the Fourier domain is now obtained by replacing the ’Fourier’ basis by the basis of Spherical Harmonics which plays an analogous role on the sphere.

The construction [NPW06b],[NPW06a] produces a family of functions which very much resemble to wavelets, the needlets, and in particular have very good concentration properties.

We use these needlets to construct an estimation procedure, and prove that this procedure attains optimal rates over various spaces of regularity.

Again, the problem of choosing appropriated spaces of regularity on the sphere in a serious question, and we decided to consider the spaces which may be the closest to our natural intuition: those which generalize to the sphere case the classical Hölder spaces.

In the first section we present ([NPW06b]) needlets, and describe spaces of regularity on the sphere. In the second one we define our estimation procedure, and describe its properties.

The novelties of this paper lie in the application of thresholding to the needlet coefficients, which gives a very simple and adaptive procedure which works on the sphere. We also focus here on giving the results in $L_{\infty}$ norm, and obtain the rates of convergence for many other loss functions as a consequence of the previous ones.

Our results are motivated by many recent developments in the area of observational astrophysics. As an example, we refer to experiments measuring incoming directions of Ultra High Energy Cosmic Rays, such as the AUGER Observatory (http://www.auger.org). Here, efficient estimation of the density function of these directional data may yield crucial insights into the physical mechanisms generating the observations. More precisely, a uniform density would suggest the High Energy Cosmic Rays are generated by cosmological effects, such as the decay of massive particles generated during the Big Bang; on the other hand, if these Cosmic Rays are generated by astrophysical phenomena (such as acceleration into Active Galactic Nuclei), then we should observe a density function which is highly non-uniform and tightly correlated with the local distribution of nearby Galaxies. Massive amount of data in this area are expected to be available in the next few years. The Auger observatory will be based on two arrays of detectors; the first one covers an area larger than 3000 Km2 in Pampa Amarilla (Argentina), and has already started to collect observations: some preliminary evidence was provided in [Col08], and a non-uniform distribution seems to be favored. The whole celestial sphere will actually be covered only when the construction of the northern hemisphere array, due to be built in eastern Colorado, will be completed, a few years from now. Hence, in the immediate future efficient statistical techniques will be eagerly requested for the analysis of the forthcoming datasets.

A survey of statistical methodologies dealing with directional data on the sphere may be found in [Mar72], [Jup95], [MJ00]. The generalization of estimation using orthogonal series methods to the case of compact Riemannian manifold can be found in [Hen03]. See related works in [HK96], [Ruy89], [HJR93], [Pel05], [Jup08]. Kernel methods on the sphere have been investigated in [HWC87]. Minimax rates for the equivalent of Sobolev spaces on the sphere associated can be found in [Kle99], [Kle00], [Kle03].

The plan of the paper is as follows. In §2 and §3 we review some background material on needlets and Besov spaces. §4 introduces our thresholding estimator, whose minimax performances are stated in §5. §6 shows the performance of the estimators on some simulated data. §7–§9 contain the proofs.

Needlets

This construction is due to Narcowich, Petrushev and Ward [NPW06b]. Its aim is essentially to build a very well localized tight frame constructed using spherical harmonics, as discussed below. It was recently extended with fruitful statistical applications to more general Euclidean settings (see [KPPW07]) and already exploited for estimation and testing problems in [BKMP06], [BKMP07].

For the main situation of interest, $d=2$, the right hand side above is equal to $\frac{2l+1}{8\pi^{2}}$. Recall that if $d=2$, the usual normalization of the Legendre polynomial ($L_{l}(1)=1$) gives the square of their $L^{2}$ norm equal to $\frac{2}{2l+1}$. Therefore these must be multiplied by $(2l+1)/(4\pi)$, in order to satisfy (3).

Let us point out the following reproducing property of the projection operators:

The construction of needlets is based on the classical Littlewood-Paley decomposition and a subsequent discretization.

Remark that $b(\xi)\not=0$ only if $\tfrac{1}{2}\leq|\xi|\leq 2$. Let us now define the operator $\Lambda_{j}=\sum_{l\geq 0}b^{2}(\tfrac{l}{2^{j}})L_{l}$ and the associated kernel

Moreover, if $M_{j}(x,y)=\sum_{l\geq 0}b(\frac{l}{2^{j}})L_{l}(\langle x,y\rangle)$, then

Then the operator $M_{j}$ defined in the subsection above is such that: $z\mapsto M_{j}(x,z)\in\mathscr{P}_{[2^{j+1}]}$, so that

The choice of the sets ${\mathscr{Z}}_{j}$ of cubature points is not unique, but one can impose the conditions

for some $c>0$. Actually in the simulations of §6 we make use of some sets of cubature points for $d=2$ such that $\#\mathscr{Z}_{j}=2^{2j+4}$ exactly (the corresponding weights being however not identical). We have, using (6)

where $d$ is the natural geodesic distance on the sphere (for $d=2$, $d(\xi,\eta)=\arccos\langle\eta,\xi\rangle$ ). In other words needlets are almost exponentially localized around any cubature point, which motivates their name. From this localization property it follows (see [NPW06b]) that for $1\leq p\leq+\infty$ there exists positive constants $c_{p},C_{p}$ such that

Let us prove (13) for $p=+\infty$. Using (11) and Lemma 6 of [BKMP06]

If $1\leq p<+\infty$, by Hölder inequality, if $\frac{1}{p}+\frac{1}{p^{\prime}}=1$ so that $\frac{p}{p^{\prime}}=p-1$,

where the last inequality comes again from (11) and Lemma 6 of [BKMP06]. Now integrating and using (12) for $p=1$,

from which (13) follows. The remaining case $0<p\leq 1$ follows immediately by subadditivity, as

But, by Holder inequality, for $p^{\prime}$ such that $\frac{1}{p}+\frac{1}{p}^{\prime}=1,then\frac{p}{p^{\prime}}=p-1$ and

Relation (12) for $p=2$ states that the $L^{2}$ norm of $\psi_{j\xi}$ is bounded with respect to $j$ and also bounded away from from below. Assume $d=2$. Then using (4) it is actually easy to see that, keeping in mind that $L_{l}(1)=\frac{2l+1}{4\pi}$,

Assuming that the cubature points are of cardinality $2^{2j+4}$ and that they sum up to $4\pi$, $\lambda_{\eta}\sim 4\pi\cdot 2^{-2j-4}$ as $j\to\infty$. If the previous relation were an equality we could recognize in the right hand term the Riemann sum

that converges, as $j\to\infty$, to the integral

which depends on the choice of the function $b$. This $L^{2}$ norm shall appear frequently in the sequel. For instance, if we write down the development (10) or the function $f=\psi_{j_{0}\xi_{0}}$, then the coefficient $\beta_{j_{0}\xi_{0}}=\langle f,\psi_{j,\eta}\rangle$ would be exactly equal to $\|\psi_{j\xi}\|^{2}_{2}$. As it is clear that it would be desirable for this coefficient to be as large as possible, the value of the integral above can be seen as a measure of the localization properties of the system of needlets and can be used as a criterion of goodness of the choice of the function $b$. With the choice we made (see §6) the quantity $I$ above is $\simeq 0.107$.

Besov spaces on the sphere and needlets

In this section we summarize the main properties of Besov spaces and needlets, as established in [NPW06b].

the infimum of the distances in $L^{r}$ of $f$ from the polynomials of degree $k$. Then the Besov space $B^{s}_{r,q}$ is defined as the space of functions such that

Remarking that $k\to E_{k}(f,r))$ is decreasing, by a standard condensation argument this is equivalent to

Let $1\leq r\leq+\infty$, $s>0$, $0\leq q\leq+\infty$. Let $f$ a measurable function and define

provided the integrals exists. Then $f\in B^{s}_{r,q}$ if and only if, for every $j=1,2,\dots$,

for some positive constants $c,C$, the Besov space $B^{s}_{r,q}$ turns out to be a Banach space associate to the norm

In the sequel we shall denote by $B^{s}_{r,q}(M)$ the ball of radius $M$ of the Besov space $B^{s}_{r,q}$.

(The Besov embedding) If $p\leq r\leq\infty$ then $B^{s}_{r,q}\subseteq B^{s}_{p,q}$. If $s>d(\frac{1}{r}-\frac{1}{p})$,

On the other hand, if $r\leq p\leq\infty$,

Needlet estimation of a density on the sphere

Let us suppose that we observe $X_{1},\ldots,X_{n}$, i.i.d. random variables taking values on the sphere having common density $f$ with respect to $dx$. $f$ can be decomposed using the frame of needlets described above.

The needlet estimator is based on hard thresholding of a needlet expansion as follows. We start by letting:

The tuning parameters of the needlet estimator are:

$\bullet$ The range $J=J(n)$ of resolution levels (frequencies) where the approximation (17) is used:

We shall see that the choice 2^{J}=\big{(}\frac{n}{\log n}\big{)}^{\frac{1}{d}} is appropriate.

$\bullet$ The threshold constant $\kappa$. Evaluations of $\kappa$ are given in the following Section and also discussed in §6.

$\bullet$ $c_{n}$: is a sample size-dependent scaling factor. We shall see that an appropriate choice is

which is a quantity already discussed in Example 3. As for the correlation between coefficients, it is given by the function $\theta\to\lambda_{\eta}\sum_{l\geq 0}b^{2}(\tfrac{l}{2^{j}})L_{l}(\cos\theta)$, whose graph, for some values of $j$ is plotted in Figure 2.

Whereas coefficients associated to cubature points that are not too close are only slightly correlated, the random needlet coefficients $\widehat{\beta}_{j,\eta}$, $\eta\in{\mathscr{Z}}_{j}$ are not independent and they even satisfy the linear relation

This comes from the fact that, as $y\to L_{l}(\langle y,x\rangle)$ for $l\leq 2^{j}$ is a polynomial of degree $\leq 2^{2j}$, one has

For $0<r\leq\infty$, $p\geq 1$, $s>\frac{d}{r}$ we have

a) For any $z>1$, there exist some constants $c_{\infty}=c_{\infty}(s,p,r,A,M)$ such that if $\kappa>\frac{z+1}{6}$,

b) For $1\leq p<\infty$ there exist some constant $c_{p}=c_{p}(s,r,p,A,M)$ such that if $\kappa>\frac{p}{12}$,

where $\alpha_{p}=p-1+1_{\{r=\frac{dp}{2s+d}\}}$, if $r\leq\frac{dp}{2s+d}$, whereas

which, as remarked above gives an indication about the square of the value of the $L^{2}$ norm of a needlet $\psi_{j\xi}$. In both the examples below we considered samples of cardinality $n=2000$ and $n=8000$. The hint for the value of $J$ of Theorem 8 is J=\frac{1}{2}\,\log_{2}\big{(}\frac{n}{\log n}\big{)}, which gives the values $J\sim 4.02$ and $J\sim 4.9$ respectively. One should keep in mind that at a given level $j$ it is necessary to have enough cubature points in order to integrate exactly all polynomials up to the degree $2(2^{j+1}-1)=2^{j+2}-2$, which means $\sim 2^{2j+4}$ cubature points with Womersley’s set (recall that on the sphere the polynomials of degree $d$ form a vector space of dimension $(2d+1)^{2}$). This gives $2^{10}=1024$ cubature points for $j=3$, $2^{12}=4096$ for $j=4$ and $2^{14}=16384$ for $j=5$. To avoid to have more coefficients than observations, we decided to set $J=3$ for $n=2000$ and $J=4$ for $n=8000$.

As for the value of $\kappa$, we shall give the result with $\kappa=k_{0}\sqrt{0.107}\,M$, where $M$ is an a bound for $\|f\|_{\infty}$, trying different values of $k_{0}$. Recall that this means that the threshold kills all coefficients $\beta_{j\xi}$ such that $|\beta_{j\xi}|<\kappa\sqrt{\frac{\log n}{n}}$

$f=\frac{1}{4\pi}$, the uniform density. In this case in the development (10) it holds $\beta_{j\xi}=\langle f,\psi_{j\xi}\rangle_{L^{2}}=0$ for every $j$ and $\xi$. Therefore a first simple way of assessing the performance of the procedure is to count the number of coefficients that survive thresholding. Of course in this case a good estimate is such that the coefficients $\beta_{j,\xi}$ fall below the threshold. Taking into account Lemma 2 the square root of the sum of the squares of the coefficients surviving thresholding gives an estimate of $\|\hat{f}-f\|_{2}$. Therefore a measure of the goodness of the fit is obtained by taking the sum of their squares. Tables 1 and 2 give the number of surviving coefficients for different values of the constant $k_{0}$.

In order to kill all the coefficients one should choose $k_{0}=5.4$ for $n=2000$ and $k_{0}=2.8$ for $n=8000$. The estimate of the $L^{2}$ norm of the difference between $\hat{f}$ and $f$ by taking the square root of the sum of the squares of the coefficients is

Let us consider a mixture $f$ of two densities of the form $f_{i}(x)=c_{i}\exp(-k_{i}|x-x_{i}|^{2})$, $i=1,2$, for $k_{1}=.7$ and $k_{2}=2$ and with weights $0.65$ and $0.35$ respectively. Here the centers $x_{i}$ of the two bell-shaped densities were taken to be $x_{1}=(0,1,0)$, $x_{2}=(0,-.8,.6)$. With these choices it turns out that $\|f\|_{\infty}=0.26$. The graph of $f$ in the coordinates $(\varphi,\theta)$ ($\varphi=$longitude, $\theta=$colatitude) is given in Figure 4.

The estimator $\hat{f}$ obtained with the choice $k_{0}=1.1$ has the graph of Figure 5.

If one chooses $k_{0}=1.5$ the graph becomes the one of Figure 6. At a closer inspection it turns out that with this value of $k$ all coefficients at level $j=3$ do not pass the thresholding. It looks very much like the graph of $f$, even though some differences in shape are apparent. An estimate of the norm $\|\hat{f}-f\|_{\infty}$ computed on a grid gives $\|\hat{f}-f\|_{\infty}\sim 0.054$.

We repeated the simulation with $n=8000$ observations. The results are reported in Figures 7 and 8 and are to be considered rather satisfactory. It should be stressed that a very limited number of coefficients passes thresholding at a frequency $j>2$. This behaviour is expected: $f$ being very regular, it belongs to a space $B^{\infty}_{\infty,\infty}$ and thus its needlet coefficients decay very rapidly.

In the sequel we note $t(\hat{\beta}_{j,\xi})=\hat{\beta}_{j\eta}\,{1}_{\{|\hat{\beta}_{j\eta}|\geq\,\kappa\,c_{n}\}}$, so that the needlet estimator (17) is

The following proposition collects the main estimates needed in the proof.

Let $J_{1}\leq J$ be such that, for all $J_{1}\leq j\leq J$, $|\beta_{j\eta}|\leq\tfrac{\kappa}{2}t_{n}$ (possibly $J_{1}=J$; obviously, when $f$ belongs to a Besov class, $J_{1}$ depends on the “regularity” $s$). Then for any $\gamma>0,s>0,z\geq 1$, we have

1) if $\kappa>\frac{1}{3}(\frac{\gamma}{d}+\frac{1}{2})$

We delay the proof of Proposition 14 to §8 and derive from it the proof of Theorem 8. In this proof $C$ will denote an absolute constant which may change from line to line. Let us now prove that Proposition 14 yields to the statements of Theorem 8:

Let us prove the $L^{\infty}$ upper bound (19), first under the condition $q=r=\infty$

The term $II$ is easy to analyze: as $f$ belongs to $B^{s}_{\infty,\infty}(M)$, we have using (12) and 13,

Then we only need to remark that $\frac{s}{d}\geq\frac{s}{d+2s}$ for $s>0$.

As for $I$, using the triangular inequality together with Hölder inequality, then (12), and (22) with $\gamma=\frac{dz}{2},z>1$, we get

As $f$ belongs to $B^{s}_{\infty,\infty}(M)$, $|\beta_{j\eta}|\leq M2^{-j(s+\frac{d}{2})}$ and we can see that

For arbitrary $q,r$ (19) is now easy to deduce from the previous computation by the Besov embedding (Theorem 5) $B^{s}_{r,q}(M)\subset B^{s-\frac{d}{r}}_{\infty,\infty}(M).$ Let us prove (21), that is the regular case. We observe first that since $B^{s}_{r,q}(M)\subset B^{s}_{p,q}(M)$ for $r\geq p$, this case will be assimilated to the case $p=r$, and from now on, we only consider $r\leq p$. We follow the same arguments as above. (25) can be replaced by

For $II$ using the embedding $B^{s}_{r,q}(M)\subset B^{s-\frac{d}{p}+\frac{d}{p}}_{p,q}(M)$, for $r\leq p$, we have

And it is easy to verify that $\frac{s}{d}-\frac{1}{r}+\frac{1}{p}\geq\frac{s}{2s+d}$ on the zone that we are considering in this part. In effect as $s\geq\frac{p}{2}(\frac{d}{r}-\frac{d}{p})$, $\frac{s}{2s+d}\leq\frac{sr}{dp}$ we have $\frac{s}{d}-\frac{1}{r}+\frac{1}{p}-\frac{sr}{dp}=(\frac{1}{r}-\frac{1}{p})(\frac{s}{d}r-1)\geq 0$.

For $I$, we have using the triangular inequality together with Hölder inequality,

Then we need only to use (24), with $\gamma=\frac{dp}{2},z=p$, to obtain

is adequate, and to observe that the first term in the sum has the right order. For the second term, it can be bounded (as $p\geq r$) by

as, $sr-\frac{d}{2}(p-r)\geq 0.$ Now, this term obviously is of the right order.

Again we proceed as above and observe first that in order to have $s>0$ as well as $s\leq\frac{pd}{2}(\frac{1}{r}-\frac{1}{p})$, it is necessary that $p\geq r$:

For $II$ using the embedding, $B^{s}_{r,q}(M)\subset B^{s-\frac{d}{r}+\frac{d}{p}}_{p,q}(M)$, for $r\leq p$, we have:

And it is easy to verify that $\frac{s}{d}-\frac{1}{r}+\frac{1}{p}\geq\frac{(s-d(\frac{1}{r}-\frac{1}{p}))}{2(s-d(\frac{1}{r}-\frac{1}{2}))}$, since $2(s-d(\frac{1}{r}-\frac{1}{2}))\geq d$, when $s>\frac{d}{r}$.

For $I$, again, we have using the triangular inequality together with Hölder inequality,

Then we need to use (23), with $\gamma=d\frac{p}{2},z=p$, to obtain:

as we are in the sparse region. It is easy to realize that now, again because we are in the sparse region

is adequate, and to observe then that the first term in the sum has the right order. For the second term, let us introduce

We easily observe that $p-m=\frac{p(s+\frac{d}{p}-\frac{d}{r})}{s+\frac{d}{2}-\frac{d}{r}}>0$, and that $m-r=\frac{-sr+(p-r)\frac{d}{2}}{s+\frac{d}{2}-\frac{d}{r}}\geq 0.$ Then, as $B^{s}_{r,q}(M)\subset B^{s-\frac{d}{r}+\frac{d}{m}}_{m,q}(M)$

which gives the right order. Observe that the term $J$ (which is of logarithmic order), can be avoided by choosing $\widetilde{m}$ instead of $m$ in such a way that $\widetilde{m}>m$, but $r<\widetilde{m}$. This can be done except for the case where $r=\frac{dp}{2s+d}$ where this logarithmic term is unavoidable.

The proof of Proposition 14 relies on the following lemma:

There exist constants $\sigma^{2}>0,\;C,\;c$, such that, as soon as $2^{j}\leq[\frac{n}{\log n}]^{\frac{1}{d}}$,

Proof of the lemma (28) is simply Bernstein inequality, noticing that

and $\|\psi_{j\eta}(X_{i})\|_{\infty}\leq c2^{\frac{jd}{2}}$. The following inequality directly follows from (28), when $2^{jd}\leq n$.

using the change of variables $u=\sqrt{n}v$.

(30) also follows from (32): take $a=\max\{\frac{8cd}{3},{2\sqrt{2}d\sigma}\}$

Now, if $v\geq\frac{aj}{\sqrt{n}}$, $2^{jd}e^{-\frac{nv^{2}}{4\sigma^{2}}}\leq e^{-\frac{nv^{4}}{8\sigma^{2}}-\frac{nv^{4}}{8\sigma^{2}}+jd}\leq e^{-\frac{nv^{4}}{8\sigma^{2}}}$. Similarly $2^{jd}e^{-\frac{3\sqrt{n}v}{4c}}\leq e^{-\frac{3\sqrt{n}v}{8c}}$, so that

Let us now turn to the proof of the Proposition. We partition our sum in four regions:

We use extensively Lemma 15 in order to bound separately each of the four terms $Bb,Ss,Sb,Bs$.

where $J_{1}$ is chosen such that for $j\geq J_{1}$, $|\beta_{j\eta}|\leq\frac{\kappa}{2}t_{n}$. Also

which gives the proper rate of convergence. Moreover, using (30) and (31),

where $\kappa>\frac{1}{3}(\frac{\gamma}{d}+\frac{1}{2})$. Finally, using (31), and the fact that for $f$ bounded, $|\beta_{j\eta}|\leq C2^{-\frac{jd}{2}}$

for $\kappa>\frac{1}{6}(\frac{\gamma}{d}+1)$.

This proof follows along the lines of the previous one. (24) is a consequence of (23), and the two inequalities will be proved together. We again separate the four cases.

Let us now bound separately each of the four terms $Bb,\;Ss,\;Sb,\;Bs$. Using (29)

where $J_{1}$ again is chosen such that for $j\geq J_{1}$, $|\beta_{j\eta}|\leq\frac{\kappa}{2}t_{n}$. To prove (23), we stop in (*), the next bound yields (24).

which gives the proper rate of convergence. Again, to prove (23), we stop in (*), the next bound yields (24). Moreover, using (30) and (31),

for $\kappa>\frac{\gamma}{6d}$. Finally, using (31), and the fact that for $f$ bounded, $|\beta_{j\eta}|\leq C2^{-\frac{jd}{2}}$

Let us recall that given two probabilities $P$, $Q$ on some measure space their Kullback-Leibler distance is

We make use of Fano’s lemma below, see [Tsy04] and the references therein. We use the point of view introduced in [Bir01].

(Fano’s Lemma) Let $\mathscr{F}$ be a sigma algebra on the space $\Omega.$ Let $F_{i}\in\mathscr{F},~{}~{}i\in\{0,1,\ldots,m\}$ such that $\forall i\neq j,F_{i}\cap F_{j}=\emptyset.$ Let $P_{i}$, $i=0,\ldots,m$ be probability measures on $(\Omega,\mathscr{A}).$ If

$\bullet$ We prove first that the minimax $L^{p}$-loss is $\gtrsim n^{-\alpha p}$ with $\alpha=\frac{s}{2s+d}$. For every $j$ let us consider the family ${\mathscr{A}}_{j}$ of densities

where $A_{j}$ is a subset of ${\mathscr{Z}}_{j}$ to be made precise later, $\varepsilon_{\xi}\in\{0,1\}$ and $\gamma$ is chosen so that all these functions are positive. We are going to show that for every estimator $\hat{f}$,

Throughout this section we shall note $x\lesssim y$, $x\gtrsim y$ whenever it holds $x\leq cy$ or $x\geq cy$ respectively, $c$ being a strictly positive constant independent of $j,\xi$. We shall note $x\simeq y$ whenever both $x\lesssim y$ and $x\gtrsim y$ hold. Thanks to (12) for these functions to be positive it is enough that $|\gamma|\lesssim 2^{-jd/2}$. Such a $\gamma$ can even be chosen in such a way that all the densities (37) are bounded from below by a strictly positive constant. If the functions $(\psi_{j\xi})_{\xi\in{\mathscr{Z}}_{j}}$ were orthonormal we would have immediately that

Needlets are not a basis, but their scalar product is close enough to if the respective cubature points are far enough. Hence one can get the following lemma that states that a subset $A_{j}\subset{\mathscr{Z}}_{j}$ can be chosen so that it is quite large and inequalities (14) and (13), in a sense, can be reversed.

There exists a subset $A_{j}\subset{\mathscr{Z}}_{j}$ such that ${\rm card}\,A_{j}\gtrsim 2^{jd}$ and

Let us now impose conditions that ensure that $f_{\varepsilon}$ belongs to the ball $B^{s}_{r,q}(M)$. Now, recalling (15),

where we use the fact that $|\varepsilon_{\xi}|=1$. Therefore the condition $\|f_{\varepsilon}\|_{B^{s}_{r,q}}\leq M$ follows from

In order to apply Fano’s Lemma and get a lower bound of the left hand side let us first get an upper bound for the Kullback-Leibler distances $K(f_{\varepsilon};f_{\varepsilon})$, which comes from (33) and (12) for $p=2$,

Thanks to Lemma 17, the set of functions ${\mathscr{A}}_{j}$ has a cardinality that is $\geq 2^{c2^{jd}}$. By the Varshanov-Gilbert Lemma ([Tsy04] e.g.) there exists a subset ${\mathscr{A}}^{\prime}_{j}\subset{\mathscr{A}}_{j}$ such that ${\rm card}\,{\mathscr{A}}^{\prime}_{j}\geq 2^{c^{\prime}2^{jd}}$ and such that if $f_{\varepsilon},f_{\varepsilon}^{\prime}\in{\mathscr{A}}^{\prime}_{j}$, then $\sum_{\xi\in A^{\prime}_{j}}|\varepsilon_{\xi}-\varepsilon^{\prime}_{\xi}|>\frac{1}{4}\,2^{jd}$. Therefore, as $|\varepsilon_{\xi}-\varepsilon^{\prime}_{\xi}|$ can be $=0$ or $=1$ only and by (12),

which implies that the events $\{\|\widehat{f}-f_{\varepsilon^{\prime}}\|_{p}\geq\tfrac{1}{2}\,2^{-js}\}$ are disjoint. The family of densities $f_{\varepsilon}\in{\mathscr{A}}^{\prime}_{j}$ given by the Varshanov-Gilbert Lemma has cardinality $m\simeq 2^{c^{\prime}2^{jd}}$ and by (39) and (38)

We apply now Fano’s lemma to the probabilities ${\rm P}_{\varepsilon}$ that are the $n$ times product of $f_{\varepsilon}\,dx$ and to the events $A_{\varepsilon}=\{\|\widehat{f}-f_{\varepsilon^{\prime}}\|_{p}\geq\tfrac{1}{2}\,2^{-js}\}$. It is well known that

Now let $j$ be so that $n2^{-2js}\simeq 2^{jd}$, that is $2^{j}\simeq n^{\frac{1}{2s+d}}$. With this choice one has

$\bullet$ We prove now that the minimax $L^{p}$-loss is $\gtrsim n^{-\frac{p(s+d(\frac{1}{p}-\frac{1}{r}))}{2(s+d(\frac{1}{2}-\frac{1}{r}))}}$. Let us consider the two densities

with $\gamma$ such that the above are positive ($|\gamma|\lesssim 2^{-jd/2}$ is enough). If $|\gamma|\leq 2^{-js}2^{-jd(\frac{1}{2}-\frac{1}{r})}M$, then thanks to (15) both $f_{0}$ and $f_{1}$ belong to the ball $B^{s}_{r,q}(M)$. Remark that this condition implies $|\gamma|\lesssim 2^{-jd/2}$, as we assume $s\geq\frac{d}{r}$. Also

so that,if we denote by ${\rm P}_{0},P_{1}$ the $n$-times product of $f_{0}\,dx$ and $f_{1}\,dx$ by itself respectively, $K({\rm P}_{0},{\rm P}_{1})\approx n\gamma^{2}$. By (13) and Lemma 17 we have

We choose $\gamma=\frac{1}{\sqrt{n}}=2^{-j(s+d(\frac{1}{2}-\frac{1}{r}))}$, so that $K({\rm P}_{0},{\rm P}_{1})\approx n$. Moreover with this choice of $n$, $j\approx\log n((2(s+d(\frac{1}{2}-\frac{1}{r})))^{-1}$, so that again by Fano’s lemma,

Thanks to (39) the events $\{\|\hat{f}-f_{i}\|_{p}\geq\delta\}$ are disjoint if $\delta\lesssim 2^{-j(s+d(\frac{1}{p}-\frac{1}{r}))}$. Therefore by Fano’s lemma

Putting things together and checking for which values of the parameters one rate is larger than the other one concludes the proof of Theorem 10. Note that, as $s>\frac{d}{r}$, if $1\leq p\leq 2$