Olivier Collier

Laëtitia Comminges

Alexandre B Tsybakov

Minimax estimation of linear and quadratic functionals on sparsity classes

Keywords: nonasymptotic minimax estimation, linear functional, quadratic functional, sparsity, unknown noise variance, thresholding

Introduction

In this paper, we consider the model [START_REF] Abramovich | MAP model selection in Gaussian regression[END_REF] y j = θ j + σξ j , j = 1, . . . , d, where θ = (θ 1 , . . . , θ d ) ∈ R d is an unknown vector of parameters, ξ j are i.i.d. standard normal random variables, and σ > 0 is the noise level. We study the problem of estimation of linear and quadratic functionals

L(θ) = d i=1 θ i , and
Q(θ) = d i=1 θ 2 i ,
and of the ℓ 2 -norm

θ 2 = Q(θ)
based on the observations y 1 , . . . , y d .

In this paper, we assume that θ belongs to a given subset Θ of R d . We will be considering classes Θ with elements satisfying the sparsity constraints θ 0 ≤ s where θ 0 denotes the number of non-zero components of θ, or θ q ≤ r where

θ q = d i=1 |θ i | q 1/q .
Here, r, q > 0 and the integer s ∈ [1, d] are given constants.

Let T (θ) be one of the functionals L(θ), Q(θ) or Q(θ). As a measure of quality of an estimator T of the functional T (θ), we consider the maximum squared risk 2 , where E θ denotes the expectation with respect to the probability measure P θ of the vector of observations (y 1 , . . . , y d ) satisfying [START_REF] Abramovich | MAP model selection in Gaussian regression[END_REF]. The best possible quality is characterized by the minimax risk

sup θ∈Θ E θ ( T -T (θ))
R * T (Θ) = inf T sup θ∈Θ E θ ( T -T (θ)) 2 ,
where inf T denotes the infimum over all estimators. In this paper, we find minimax optimal estimators of T (θ), i.e., estimators T such that

(2)

sup θ∈Θ E θ ( T -T (θ)) 2 ≍ R * T (Θ).
Here and below, we write a ≍ b if c ≤ a/b ≤ C for some absolute positive constants c and C. Note that the minimax optimality is considered here in the non-asymptotic sense, i.e., [START_REF] Aldous | Exchangeability and Related Topics, École d'été de Saint-Flour XIII -1983[END_REF] should hold for all d and σ.

The literature on minimax estimation of linear and quadratic functionals is rather extensive. The analysis of estimators of linear functionals from the minimax point of view was initiated in [START_REF] Ibragimov | Nonparametric estimation of the value of a linear functional in Gaussian white noise[END_REF] while for the quadratic functionals we refer to [START_REF] Donoho | Minimax quadratic estimation of a quadratic functional[END_REF]. These papers, as well as the subsequent publications [START_REF] Cai | On adaptive estimation of linear functionals[END_REF][START_REF] Cai | Nonquadratic estimators of a quadratic functional[END_REF][START_REF] Donoho | Geometrizing rates of convergence[END_REF][START_REF] Efromovich | On optimal adaptive estimation of a quadratic functional[END_REF][START_REF] Golubev | The method of risk envelopes in the estimation of linear functionals[END_REF][START_REF] Golubev | An oracle approach to adaptive estimation of linear functionals in a Gaussian model[END_REF][START_REF] Johnstone | Chi-square oracle inequalities[END_REF][START_REF] Johnstone | Thresholding for weighted χ 2[END_REF][START_REF] Juditsky | Nonparametric estimation via convex programming[END_REF][START_REF] Klemelä | Sharp adaptive estimation of quadratic functionals[END_REF][START_REF] Klemelä | Sharp adaptive estimation of linear functionals[END_REF][START_REF] Laurent | Adaptive estimation of linear functionals by model selection[END_REF][START_REF] Laurent | Adaptive estimation of a quadratic functional by model selection[END_REF][START_REF] Lepski | On estimation of the Lr norm of a regression function[END_REF][START_REF] Nemirovski | Topics in Nonparametric Statistics[END_REF], focus on minimax estimation of functionals on the classes Θ describing the smoothness properties of functions in terms of their Fourier or wavelet coefficients. Typical examples are Sobolev ellipsoids, hyperrectangles or Besov bodies while a typical example of linear functional is the value of a smooth function at a point. In this framework, a deep analysis of estimation of functionals is now available including the minimax rates (and in some cases the minimax constants), oracle inequalities and adaptation. Extensions to linear inverse problems have been considered in detail by [START_REF] Butucea | Goodness-of-fit testing and quadratic functional estimation from indirect observations[END_REF][START_REF] Butucea | Adaptive estimation of linear functionals in the convolution model and applications[END_REF][START_REF] Goldenshluger | On adaptive inverse estimation of linear functionals[END_REF]. Note that classes Θ studied in this literature are convex classes. Estimation of functionals on the non-convex sparsity classes B 0 (s) = {θ ∈ R d : θ 0 ≤ s} or B q (r) = {θ ∈ R d : θ q ≤ r} with 0 < q < 1 has received much less attention. We are only aware of the paper [START_REF] Cai | Minimax Estimation of Linear Functionals Over Nonconvex Parameter Spaces[END_REF], which establishes upper and lower bounds on the minimax risk for estimators of the linear functional L(θ) on the class B 0 (s). However, that paper considers the special case when s < d a for some a < 1/2, and σ = 1/ √ d and there is a logarithmic gap between the upper and lower bounds. Minimax rates for the estimation of Q(θ) and of the ℓ 2 -norm on the classes B 0 (s) and B q (r), 0 < q < 2, were not studied. Note, that estimation the ℓ 2 -norm is closely related to minimax optimal testing of hypotheses under the ℓ 2 separation distance in the spirit of [START_REF] Ingster | Nonparametric Goodness-of-Fit Testing Under Gaussian Models[END_REF]. Indeed, the optimal tests for this problem are based on estimators of the ℓ 2 -norm. A non-asymptotic study of minimax rates of testing for the classes B 0 (s) and B q (r), 0 < q < 2, is given in [START_REF] Baraud | Non asymptotic minimax rates of testing in signal detection[END_REF] and [START_REF] Verzélen | Minimax risks for sparse regressions: Ultra-high dimensional phenomenons[END_REF]. But for the testing problem, the risk function is different and these papers do not provide results on the estimation of the ℓ 2 -norm. Note also that the upper bounds on the minimax rates of testing in [START_REF] Baraud | Non asymptotic minimax rates of testing in signal detection[END_REF] and [START_REF] Verzélen | Minimax risks for sparse regressions: Ultra-high dimensional phenomenons[END_REF] depart from the lower bounds by a logarithmic factor.

In this paper, we find non-asymptotic minimax rates of estimation of the above three functionals on the sparsity classes B 0 (s), B q (r) and construct optimal estimators that attain these rates. We deal with non-convex classes B q (0 < q < 1) for the linear functional and with the classes that are not quadratically convex (0 < q < 2) for Q(θ) and of the ℓ 2 -norm. Our main object of interest is the class B 0 (s), for which we also provide completely adaptive estimators (independent of σ and s) having logarithmically slower rates than the minimax ones. Some interesting effects should be noted. First, we show that, for the linear functional and the ℓ 2 -norm there are, in general, three zones in the rates of convergence that we call the sparse zone, the dense zone and the degenerate zone, while for the quadratic functional an additional fourth zone appears. Next, as opposed to estimation of the vector θ in the ℓ 2 -norm, cf. [START_REF] Donoho | Minimax risk over ℓp-balls for ℓq-error[END_REF][START_REF] Birgé | Gaussian model selection[END_REF][START_REF] Abramovich | MAP model selection in Gaussian regression[END_REF][START_REF] Johnstone | Gaussian Estimation: Sequence and Wavelet Models[END_REF][START_REF] Rigollet | Exponential Screening and optimal rates of sparse estimation[END_REF][START_REF] Verzélen | Minimax risks for sparse regressions: Ultra-high dimensional phenomenons[END_REF], the correct logarithmic terms in the optimal rates for the sparse zone scale as log(d/s 2 ) and not as log(d/s). Noteworthy, for the class B 0 (s), the rates of estimation of the linear functional and of the ℓ 2 -norm have a simple elbow at s = √ d (boundary between the sparse and the dense zones) and exhibit similar performances, whereas the estimation of the quadratic functional Q(θ) reveals more complex effects and is not possible only on the basis of sparsity described by the condition θ ∈ B 0 (s). Finally, we apply our results on estimation of the ℓ 2 -norm to the problem of testing against sparse alternatives. In particular, we obtain a non-asymptotic analog of Ingster-Donoho-Jin theory revealing some effects that were not captured by the previous asymptotic analysis.

Minimax estimation of the linear functional

In this section, we study the minimax rates of estimation of the linear functional L(θ) and we construct minimax optimal estimators.

Assume first that Θ is the class of s-sparse vectors B 0 (s) = {θ ∈ R d : θ 0 ≤ s} where s is a given integer, 1 ≤ s ≤ d. Consider the estimator

L = d j=1 y j 1 {|y j |>σ √ 2 log(1+d/s 2 )} if s < √ d, d j=1 y j if s ≥ √ d,
where 1 {•} denotes the indicator function.

The following theorem shows that

ψ L σ (s, d) = σ 2 s 2 log(1 + d/s 2 )
is the minimax rate of estimation of the linear functional on the class B 0 (s) and that L is a minimax optimal estimator. Theorem 1. There exist absolute constants c > 0, C > 0 such that, for any integers s, d satisfying 1 ≤ s ≤ d, and any σ > 0,

(3)

sup θ∈B 0 (s) E θ ( L -L(θ)) 2 ≤ Cψ L σ (s, d),
and

(4) R * L (B 0 (s)) ≥ cψ L σ (s, d).
Proofs of (3) and of (4) are given in Sections 8 and 7 respectively. Note that since log(1 + u) ≥ u/2 for 0 < u ≤ 1, and log(1 + u) ≤ u we have

(5) σ 2 s 2 log(1 + d/s 2 ) ≍ min(σ 2 s 2 log(1 + d/s 2 ), σ 2 d)
for all 1 ≤ s ≤ d. This writing clarifies the fact that the rate exhibits a "hidden" elbow at s = √ d. Thus,

(6) R * L (B 0 (s)) ≍ min(σ 2 s 2 log(1 + d/s 2 ), σ 2 d).
We consider now the classes B q (r) = {θ ∈ R d : θ q ≤ r}, where 0 < q ≤ 1, and r is a positive number. For any r, σ, q > 0 any integer d ≥ 1, we define the intege [START_REF] Butucea | Goodness-of-fit testing and quadratic functional estimation from indirect observations[END_REF] m = max{s ∈ {1, . . . , d} :

σ 2 log(1 + d/s 2 ) ≤ r 2 s -2/q } if the set {s ∈ {1, . . . , d} : σ 2 log(1 + d/s 2 ) ≤ r 2 s -2/q
} is non-empty, and we put m = 0 if this set is empty. The next two theorems show that the optimal rate of convergence of estimators of the linear functional on the class B q (r) is of the form:

ψ L σ,q (r, d) = σ 2 m 2 log(1 + d/m 2 ) if m ≥ 1, r 2 if m = 0.
The following theorem shows that ψ L σ,q (r, d) is a lower bound on the convergence rate of the minimax risk of the linear functional on the class B q (r).

Theorem 2. If 0 < q ≤ 1, then there exists a constant c > 0 such that, for any integer d ≥ 1 and any r, σ > 0, we have

(8) R * L (B q (r)) ≥ cψ L σ,q (r, d).
The proof of Theorem 2 is given in Section 7.

We now turn to the construction of minimax optimal estimators on B q (r). For 0 < q ≤ 1, define the following statistic

Lq =      d j=1 y j if m > √ d, d j=1 y j 1 {|y j |>2σ √ 2 log(1+d/m 2 )} if 1 ≤ m ≤ √ d, 0 if m = 0.
Theorem 3. Let 0 < q ≤ 1. There exists a constant C > 0 such that, for any integer d ≥ 1 and any r, σ > 0, we have

(9) sup θ∈Bq(r) E θ ( Lq -L(θ)) 2 ≤ Cψ L σ,q (r, d).
The proof of Theorem 3 is given in Section 8. Theorems 2 and 3 imply that ψ L σ,q (r, d) is the minimax rate of estimation of the linear functional on the ball B q (r) and that Lq is a minimax optimal estimator. Some remarks are in order here. Apart from the degenerate case m = 0 when the zero estimator is optimal, we obtain on B q (r) the same expression for the optimal rate as on the class B 0 (s), with the difference that the sparsity s is now replaced by the "effective sparsity" m. Heuristically, m is obtained as a solution of

σ 2 m 2 log(1 + d/m 2 ) ≍ r 2 m 2-2/q
where the left hand side represents the estimation error for m-sparse signals established in Theorem 1 and the right hand side gives the error of approximating a vector from B q (r) by an m-sparse vector in squared ℓ 1 -norm. Note also that, in view of (5), we can equivalently write the optimal rate in the form

ψ L σ,q (r, d) ≍    σ 2 d if m > √ d, σ 2 m 2 log(1 + d/m 2 ) if 1 ≤ m ≤ √ d, r 2 if m = 0.
Thus, the optimal rate on B q (r) has in fact three regimes that we will call the dense zone

(m > √ d), the sparse zone (1 ≤ m ≤ √ d)
, and the degenerate zone (m = 0). Furthermore, it follows from the definition of m that the rate ψ L σ,q (r, d) in the sparse zone is of the order σ 2 (r/σ) 2q log 1-q (1 + d(σ/r) 2q ), which leads to

ψ L σ,q (r, d) ≍    σ 2 d if m > √ d, σ 2 (r/σ) 2q log 1-q (1 + d(σ/r) 2q ) if 1 ≤ m ≤ √ d, r 2 if m = 0.
In particular, for q = 1, the logarithmic factor disappears from the rate, and the optimal rates in the sparse and degenerate zones are both equal to r 2 . Therefore, for q = 1, there is no need to introduce thresholding in the definition of Lq , and it is enough to use only the zero estimator for m ≤ √ d and the estimator d j=1 y j for m > √ d to achieve the optimal rate.

Remark 1. In this section and throughout the paper, theorems on the minimax lower bounds are stated for the squared loss function only. However, the proofs in Section 7 are given for the indicator loss function, which is more general. For each of the considered classes Θ, they have the form

(10) inf T sup θ∈Θ P θ | T -T (θ)| ≥ ψ ≥ c,
where inf T denotes the infimum over all estimators, ψ is the corresponding minimax optimal rate and c > 0 is an absolute constant. Clearly, [START_REF] Cai | On adaptive estimation of linear functionals[END_REF] implies lower bounds for the minimax risk with any monotone non-decreasing loss function on R + taking value 0 at 0.

Minimax estimation of the quadratic functional

Consider now the problem of estimation of the quadratic functional Q(θ) = d i=1 θ 2 i . For any integers s, d satisfying 1 ≤ s ≤ d, and any σ > 0, we introduce the notation

ψσ (s, d) = σ 4 s 2 log 2 (1 + d/s 2 ) if s < √ d, σ 4 d if s ≥ √ d.
The following theorem shows that

ψ Q σ (s, d, κ) = min{κ 4 , max{σ 2 κ 2 , ψσ (s, d)}}
is a lower bound on the convergence rate of the minimax risk of the quadratic functional on the class B 2 (κ) ∩ B 0 (s), where B 2 (κ) = {θ ∈ R d : θ 2 ≤ κ}.

Theorem 4. There exists an absolute constant c > 0 such that, for any integers s, d satisfying 1 ≤ s ≤ d, and any κ, σ > 0, we have

(11) R * Q (B 2 (κ) ∩ B 0 (s)) ≥ c ψ Q σ (s, d, κ).
The proof of Theorem 4 is given in Section 7.

Remark 2. Note that the minimax risk R * Q (B 2 (κ) ∩ B 0 (s)) is monotone non-decreasing in s while the right hand side of ( 11) is not monotone in s. Nevertheless, there is no problem since ψσ (s, d) is equivalent, up to absolute constants, to a monotone function of s, for which [START_REF] Cai | Nonquadratic estimators of a quadratic functional[END_REF] remains valid with another constant c. For example, we have [START_REF] Donoho | Higher criticism for detecting sparse heterogeneous mixtures[END_REF] ψσ (s, d)

≍ d f 2 min{1, s/ √ d} ,
where f (t) = t log(1 + 4/t 2 ). It is easy to check that the right hand side of ( 12) is monotone in s.

One of the consequences of Theorem 4 is that [START_REF] Cai | Nonquadratic estimators of a quadratic functional[END_REF]). Thus, only smaller classes than B 0 (s) are of interest when estimating the quadratic functional. The class B 2 (κ) ∩ B 0 (s) naturally arises in this context but other classes can be considered as well.

R * Q (B 0 (s)) = ∞ (set κ = ∞ in
We now turn to the construction of minimax optimal estimator on B 2 (κ) ∩ B 0 (s). Set

α s = E X 2 | X 2 > 2 log(1 + d/s 2 ) = E X 2 1 {|X|> √ 2 log(1+d/s 2 )} P |X| > 2 log(1 + d/s 2 ) ,
where X ∼ N (0, 1) denotes the standard normal random variable. Introduce the notation

ψ σ (s, d, κ) = max{σ 2 κ 2 , ψσ (s, d)}. Thus, ( 13
) ψ Q σ (s, d, κ) = min{κ 4 , ψ σ (s, d, κ)}.
Define the following statistic

Q =      d j=1 (y 2 j -α s σ 2 ) 1 {|y j |>σ √ 2 log(1+d/s 2 )} if s < √ d and κ 4 ≥ ψ σ (s, d, κ), d j=1 y 2 j -dσ 2 if s ≥ √ d and κ 4 ≥ ψ σ (s, d, κ), 0 if κ 4 < ψ σ (s, d, κ).
Theorem 5. There exists an absolute constant C > 0 such that, for any integers s, d satisfying 1 ≤ s ≤ d, and any κ, σ > 0, we have

(14) sup θ∈B 2 (κ)∩B 0 (s) E θ ( Q -Q(θ)) 2 ≤ C ψ Q σ (s, d, κ).
The proof of Theorem 5 is given in Section 8. Theorems 4 and 5 imply that ψ Q σ (s, d, κ) is the minimax rate of estimation of the quadratic functional on the class B 2 (κ) ∩ B 0 (s) and that Q is a minimax optimal estimator.

As a corollary, we obtain the minimax rate of convergence on the class B 2 (κ) (set s = d in Theorems 4 and 5). In this case, the estimator Q takes the form

Q * = d j=1 y 2 j -dσ 2 if κ 4 ≥ max{σ 2 κ 2 , σ 4 d}, 0 if κ 4 < max{σ 2 κ 2 , σ 4 d}.
Corollary 1. There exist absolute constants c, C > 0 such that, for any κ, σ > 0, we have

(15) sup θ∈B 2 (κ) E θ ( Q * -Q(θ)) 2 ≤ C min{κ 4 , max(σ 2 κ 2 , σ 4 d)}, and
(16) R * Q (B 2 (κ)) ≥ c min{κ 4 , max(σ 2 κ 2 , σ 4 d)}.
Note that the upper bounds of Theorem 5 and Corollary 1 obviously remain valid for the positive part estimators Q+ = max{ Q, 0}, and Q * ,+ = max{ Q * , 0}. The upper rate as in [START_REF] Donoho | Minimax quadratic estimation of a quadratic functional[END_REF] on the class B 2 (κ) with an extra logarithmic factor is obtained for different estimators in [START_REF] Johnstone | Chi-square oracle inequalities[END_REF][START_REF] Johnstone | Thresholding for weighted χ 2[END_REF].

Alternatively, we consider the classes B q (r), where r is a positive number and 0 < q < 2. As opposed to the case of B 0 (s), we do not need to consider intersection with B 2 (κ). Indeed, it is granted that the ℓ 2 -norm of θ is uniformly bounded thanks to the inclusion B q (r) ⊆ B 2 (r). For any r, σ > 0, 0 < q < 2, and any integer d ≥ 1 we set

ψ Q σ,q (r, d) =    max{σ 2 r 2 , σ 4 d} if m > √ d, max{σ 2 r 2 , σ 4 m 2 log 2 (1 + d/m 2 )} if 1 ≤ m ≤ √ d, r 4 if m = 0,
where m is the integer defined above (cf. [START_REF] Butucea | Goodness-of-fit testing and quadratic functional estimation from indirect observations[END_REF]) and depending only on d, r, σ, q. The following theorem shows that ψ Q σ,q (r, d) is a lower bound on the convergence rate of the minimax risk of the quadratic functional on the class B q (r). Theorem 6. Let 0 < q < 2. There exists a constant c > 0 such that, for any integer d ≥ 1, and any r, σ > 0, we have

(17) R * Q (B q (r)) ≥ c ψ Q σ,q (r, d).
We now turn to the construction of minimax optimal estimators on B q (r). Consider the following statistic

Qq =      d j=1 y 2 j -dσ 2 if m > √ d, d j=1 (y 2 j -αm σ 2 ) 1 {|y j |>2σ √ 2 log(1+d/m 2 )} if 1 ≤ m ≤ √ d, 0 if m = 0, where αm = E X 2 | X 2 > 8 log(1 + d/m 2 ) , X ∼ N (0, 1).
Theorem 7. Let 0 < q < 2. There exists a constant C > 0 such that, for any integer d ≥ 1 , and any r, σ > 0, we have

(18) sup θ∈Bq(r) E θ ( Qq -Q(θ)) 2 ≤ Cψ Q σ,q (r, d).
The proof of Theorem 7 is given in Section 8. Theorems 6 and 7 imply that ψ Q σ,q (r, d) is the minimax rate of estimation of the quadratic functional on the class B q (r) and that Qq is a minimax optimal estimator.

Notice that, in view of the definition of m, in the sparse zone we have

σ 4 m 2 log 2 (1 + d/m 2 ) ≍ σ 4 (r/σ) 2q log 2-q (1 + d(σ/r) 2q ),
which leads to

ψ Q σ,q (r, d) ≍    max{σ 2 r 2 , σ 4 d} if m > √ d, max{σ 2 r 2 , σ 4 (r/σ) 2q log 2-q (1 + d(σ/r) 2q )} if 1 ≤ m ≤ √ d, r 4 if m = 0.
One can check that for q = 2 this rate is of the same order as the rate obtained in Corollary 1.

Minimax estimation of the ℓ 2 -norm

Interestingly, the minimax rates of estimation of the ℓ 2 -norm θ 2 = Q(θ) do not degenerate as the radius κ grows to infinity, as opposed to the rates for Q(θ) established above. It turns out that the restriction to B 2 (κ) is not needed to get meaningful results for estimation of Q(θ) on the sparsity classes. We drop this restriction and assume that Θ = B 0 (s). Consider the estimator

N = max{ Q• , 0}
where

Q• = d j=1 (y 2 j -α s σ 2 ) 1 {|y j |>σ √ 2 log(1+d/s 2 )} if s < √ d, d j=1 y 2 j -dσ 2 if s ≥ √ d.
The following theorem shows that N is a minimax optimal estimator of the ℓ 2 -norm θ 2 = Q(θ) on the class B 0 (s) and that the corresponding minimax rate of convergence is

ψ √ Q σ (s, d) = σ 2 s log(1 + d/s 2 ) if s < √ d, σ 2 √ d if s ≥ √ d.
Theorem 8. There exist absolute constants c > 0, C > 0 such that, for any integers s, d satisfying 1 ≤ s ≤ d, and any σ > 0,

sup θ∈B 0 (s) E θ ( N -θ 2 ) 2 ≤ Cψ √ Q σ (s, d), (19)
and

(20) R * √ Q (B 0 (s)) ≥ cψ √ Q σ (s, d).
Proofs of ( 19) and of ( 20) are given in Sections 8 and 7 respectively. Our next step is to analyze the classes B q (r). For any r, σ > 0, 0 < q < 2, and any integer d ≥ 1 we set

ψ √ Q σ,q (r, d) =    σ 2 √ d if m > √ d, σ 2 m log(1 + d/m 2 ) if 1 ≤ m ≤ √ d, r 2 if m = 0,
where m is the integer defined above (cf. ( 7)) and depending only on d, r, σ, q. The estimator that we consider when θ belongs to the class B q (r) is Nq = max{ Qq , 0}.

Theorem 9. Let 0 < q < 2. There exist constants C, c > 0 such that, for any integer d ≥ 1, and any r, σ > 0, we have

(21) sup θ∈Bq(r) E θ ( Nq -θ 2 ) 2 ≤ Cψ √ Q σ,q (r, d), and (22)
R * √ Q (B q (r)) ≥ cψ √ Q σ,q (r, d).
Proofs of ( 21) and of ( 22) are given in Sections 8 and 7 respectively. As in the case of linear and quadratic functionals, we have an equivalent expression for the optimal rate:

ψ √ Q σ,q (r, d) ≍    σ 2 √ d if m > √ d, σ 2 (r/σ) q log 1-q/2 (1 + d(σ/r) 2q ) if 1 ≤ m ≤ √ d, r 2 if m = 0.
Though we formally did not consider the case q = 2, note that the logarithmic factor disappears from the above expression when q = 2, and the optimal rates in the sparse and degenerate zones are both equal to r 2 . This suggests that, for q = 2, there is no need to introduce thresholding in the definition of Nq , and it is enough to use only the zero estimator for m ≤ √ d and the estimator max

d j=1 y 2 j -dσ 2 , 0 1/2 for m > √ d
to achieve the optimal rate.

Estimation with unknown noise level

In this section, we discuss modifications of the above estimators when the noise level σ is unknown. A general idea leading to our construction is that the smallest y 2 j are likely to correspond to zero components of θ, and thus to contain information on σ not corrupted by θ. Here, we will demonstrate this idea only for estimation of s-sparse vectors in the case s ≤ √ d. Then, not more than d -√ d smallest y 2 j can be used for estimation of the variance. Throughout this section, we assume that d ≥ 3.

We start by considering estimation of the linear functional. Then it is enough to replace σ in the definition of L by the following statistic

σ = 3 1 d j≤d- √ d y 2 (j) 1/2
where y 2 (j) ≤ • • • ≤ y 2 (d) are the order statistics associated to y 2 1 , . . . , y 2 d . Note that σ is not a good estimator of σ but rather an over-estimator. The resulting estimator of L(θ) is

L = d j=1 y j 1 {|y j |>σ √ 2 log(1+d/s 2 )} .
Theorem 10. There exists an absolute constant C such that, for any integers s and d satisfying s ≤ √ d, and any σ > 0, sup

θ∈B 0 (s) E θ ( L -L(θ)) 2 ≤ Cψ L σ (s, d).
The proof of Theorem 10 is given in Section 8.

Note that the estimator L depends on s. To turn it into a completely data-driven one, we may consider

L′ = d j=1 y j 1 {|y j |>σ √ 2 log d} .
Inspection of the proof of Theorem 10 leads to the conclusion that [START_REF] Ingster | Classification of sparse high-dimensional vectors[END_REF] sup

θ∈B 0 (s) E θ ( L′ -L(θ)) 2 ≤ Cσ 2 s 2 log d.
Thus, the rate for the data-driven estimator L′ is not optimal but the deterioration is only in the expression under the logarithm. A data-driven estimator of the quadratic functional can be taken in the form:

Q = d j=1 y 2 j 1 {|y j |>σ √ 2 log d} .
The following theorem shows that the estimator

Q is nearly minimax on B 2 (κ) ∩ B 0 (s) for s ≤ √ d.
Theorem 11. There exists an absolute constant C such that, for any integers s and d satisfying s ≤ √ d, and any σ > 0, sup

θ∈B 2 (κ)∩B 0 (s) E θ ( Q -Q(θ)) 2 ≤ C max σ 2 κ 2 , σ 4 s 2 log 2 d .
The proof of Theorem 11 is given in Section 8.

Consequences for the problem of testing

The results on estimation of the ℓ 2 -norm stated above allow us to obtain the solution of the problem of non-asymptotic minimax testing on the classes B 0 (s) and B q (r) under the ℓ 2 separation distance. For q ≥ 0, u > 0, and δ > 0, consider the set

Θ q,u (δ) = {θ ∈ B q (u) : θ 2 ≥ δ}.
Assume that we wish to test the hypothesis H 0 : θ = 0 against the alternative

H 1 : θ ∈ Θ q,u (δ).
Let ∆ be a test statistic with values in {0, 1}. We define the risk of test ∆ as the sum of the first type error and the maximum second type error:

P 0 (∆ = 1) + sup θ∈Θq,u(δ) P θ (∆ = 0).
A benchmark value is the minimax risk of testing

R q,u (δ) = inf ∆ P 0 (∆ = 1) + sup θ∈Θq,u(δ) P θ (∆ = 0)
where inf ∆ is the infimum over all {0, 1}-valued statistics. The minimax rate of testing on Θ q,u is defined as λ > 0, for which the following two facts hold:

(i) for any ε ∈ (0, 1) there exists A ε > 0 such that, for all A > A ε , (24) R q,u (Aλ) ≤ ε, (ii) for any ε ∈ (0, 1) there exists a ε > 0 such that, for all 0 < A < a ε ,

(25) R q,u (Aλ) ≥ 1 -ε.
Note that this defines a non-asymptotic minimax rate of testing as opposed to the classical asymptotic definition that can be found, for example, in [START_REF] Ingster | Nonparametric Goodness-of-Fit Testing Under Gaussian Models[END_REF]. A non-asymptotic minimax study of testing for the classes B 0 (s) and B q (r) is given by [START_REF] Baraud | Non asymptotic minimax rates of testing in signal detection[END_REF] and [START_REF] Verzélen | Minimax risks for sparse regressions: Ultra-high dimensional phenomenons[END_REF]. However, those papers derive the minimax rates of testing on Θ q,u only up to a logarithmic factor. The next theorem provides the exact expression for the minimax rates in the considered testing setup.

Theorem 12. For any integers s and d satisfying 1 ≤ s ≤ d, and any σ > 0, the minimax rate of testing on Θ 0,s is equal to λ = (ψ

√ Q σ (s, d)) 1/2
. For any 0 < q < 2, and any r, σ > 0, the minimax rate of testing on Θ q,r is equal to λ = (ψ

√ Q σ,q (r, d)) 1/2
. The proof of this theorem consists in establishing the upper bounds [START_REF] Ingster | Nonparametric Goodness-of-Fit Testing Under Gaussian Models[END_REF] and the lower bounds [START_REF] Ingster | Detection boundary in sparse regression[END_REF]. We note first that the lower bounds [START_REF] Ingster | Detection boundary in sparse regression[END_REF] are essentially proved in [START_REF] Baraud | Non asymptotic minimax rates of testing in signal detection[END_REF] and [START_REF] Verzélen | Minimax risks for sparse regressions: Ultra-high dimensional phenomenons[END_REF]. However, in those papers they are stated in somewhat different form, so for completeness we give a brief proof in Section 7, which is very close to the proofs of the lower bounds [START_REF]Hoeffding Probability inequalities for sums of bounded random variables[END_REF] and [START_REF] Ingster | Some problems of hypothesis testing leading to infinitely divisible distributions[END_REF]. The upper bounds [START_REF] Ingster | Nonparametric Goodness-of-Fit Testing Under Gaussian Models[END_REF] are straightforward in view of ( 19) and ( 21). Indeed, for example, to prove [START_REF] Ingster | Nonparametric Goodness-of-Fit Testing Under Gaussian Models[END_REF] with q = 0 and u = s, we fix some A > 0 and consider the test ( 26)

∆ * = 1 { N >(A/2)(ψ √ Q σ (s,d)) 1/2 } .
Then, writing for brevity ψ = ψ √ Q σ (s, d) and applying Chebyshev's inequality, we have

R 0,s (Aψ) ≤ P 0 (∆ * = 1) + sup θ∈Θ 0,s (A √ ψ) P θ (∆ * = 0) (27) ≤ P 0 ( N > A ψ/2) + sup θ∈B 0 (s) P θ ( N -θ 2 ≤ -A ψ/2) ≤ 2 sup θ∈B 0 (s) E θ ( N -θ 2 ) 2 (A/2) 2 ψ ≤ C * A -2
for some absolute constant C * > 0, where the last inequality follows from [START_REF] Golubev | An oracle approach to adaptive estimation of linear functionals in a Gaussian model[END_REF]. Choosing A ε as a solution of C * A -2 ε = ε we obtain [START_REF] Ingster | Nonparametric Goodness-of-Fit Testing Under Gaussian Models[END_REF]. The case 0 < q < 2 is treated analogously by introducing the test

∆ * q = 1 { N >(A/2)(ψ √ Q σ,q (r,d)) 1/2 }
and using [START_REF] Ibragimov | Nonparametric estimation of the value of a linear functional in Gaussian white noise[END_REF] rather than [START_REF] Golubev | An oracle approach to adaptive estimation of linear functionals in a Gaussian model[END_REF] to get the upper bound [START_REF] Ingster | Nonparametric Goodness-of-Fit Testing Under Gaussian Models[END_REF]. Furthermore, as a simple corollary we obtain a non-asymptotic analog of the Ingster-Donoho-Jin theory. Consider the problem of testing the hypothesis H 0 : θ = 0 against the alternative H 1 : θ ∈ Θ s (δ) where ( 28)

Θ s (δ) = {θ ∈ R d : θ 0 = s, θ j ∈ {0, δ}, j = 1, . . . , d}
for some integer s ∈ [1, d] and some δ > 0.

[22] and [START_REF] Donoho | Higher criticism for detecting sparse heterogeneous mixtures[END_REF] studied a slightly different but equivalent problem (with θ j taking values 0 and δ at random) assuming in addition that s = d a for some a ∈ (0, 1/2). In an asymptotic setting when σ → 0 and d = d σ → ∞, [START_REF] Ingster | Some problems of hypothesis testing leading to infinitely divisible distributions[END_REF] obtained the detection boundary in the exact minimax sense, that is the value λ = λ σ such that asymptotic analogs of ( 24) and ( 25) hold with A ε = a ε and ε = 0. [START_REF] Donoho | Higher criticism for detecting sparse heterogeneous mixtures[END_REF] proved that the detection boundary is attained at the Higher Criticism test. Extensions to the regression and classification problems and more references can be found in [START_REF] Ingster | Classification of sparse high-dimensional vectors[END_REF], [START_REF] Ingster | Detection boundary in sparse regression[END_REF], [START_REF] Arias-Castro | Global testing under sparse alternatives: ANOVA, multiple comparisons and the higher criticism[END_REF]. Note that the alternatives in these papers are defined not exactly in the same way as in [START_REF] Johnstone | Gaussian Estimation: Sequence and Wavelet Models[END_REF].

A natural non-asymptotic analog of these results consists in establishing the minimax rate of testing on Θ s (δ) in the sense of the definition ( 24) -( 25). This is done in the next corollary that covers not only Θ s (δ) but also the following more general class:

Θ * s (δ) = θ ∈ R d : θ 0 = s, min j: θ j =0 |θ j | ≥ δ .
We define the minimax rate of testing on the classes Θ s and Θ * s similarly as such rate was defined for Θ q,u , by modifying ( 24) -( 25) in an obvious way.

Corollary 2. Let s and d be integers satisfying 1 ≤ s ≤ d, and let σ > 0. The minimax rate of testing on Θ s is equal λ = σ log(1 + d/s 2 ) for s ≤ √ d. Furthermore, the minimax rate of testing on Θ * s is equal to

λ = σ log(1 + d/s 2 ) if s < √ d, σd 1/4 / √ s if s ≥ √ d.
The proof of the upper bound in this corollary is essentially the same as in Theorem 12. We take the same test statistic ∆ * and then act as in ( 27) using that Θ s (Aλ) and Θ * s (Aλ) are included in Θ 0,s (Aλ √ s). The proof of the lower bound for the case s ≤ √ d is also the same as in Theorem 12 since the measure µ ρ used in the proofs (cf. Section 7) is supported on s-sparse vectors θ with all coefficients taking the same value. For s > √ d we need a slightly different lower bound argument -see Section 7 for the details.

[22] and [START_REF] Donoho | Higher criticism for detecting sparse heterogeneous mixtures[END_REF] derived the asymptotic rate of testing in the form λ = c(a)σ √ log d where the exact value c(a) > 0 is explicitly given as a function of a appearing in the relation s = d a , 0 < a < 1/2. Corollary 2 allows us to explore more general behavior of s leading to other types of rates. For example, we find that the minimax rate of testing is of the order σ if s = √ d and it is of the order σ √ log log d if s ≍ √ d/(log d) γ for any γ > 0. Such effects are not captured by the previous asymptotic results. Note also that the test ∆ * (cf. [START_REF] Johnstone | Chi-square oracle inequalities[END_REF]) that achieves the minimax rates in Corollary 2 is very simple -it is a plug-in test based on the estimator of the ℓ 2 -norm. We do not need to invoke refined techniques as the Higher Criticism test. However, we do not prove that our method achieves the exact constant c(a) in the specific regime considered by [START_REF] Ingster | Some problems of hypothesis testing leading to infinitely divisible distributions[END_REF] and [START_REF] Donoho | Higher criticism for detecting sparse heterogeneous mixtures[END_REF].

7 Proofs of the lower bounds

General tools

The proofs of the lower bounds in this section use a technique based on a reduction to testing between two probability measures, one of which is a mixture measure. This is a special case of what is called the method of fuzzy hypotheses or Le Cam's method since Le Cam [START_REF] Cam | Convergence of estimates under dimensionality restrictions[END_REF] was apparently the first to consider this kind of argument.

Let µ be a probability measure on Θ. Denote by P µ the mixture probability measure

P µ = Θ P θ µ(dθ).
A vector θ ∈ R d is called s-sparse if θ 0 = s. For an integer s such that 1 ≤ s ≤ d and ρ > 0, we denote by µ ρ the uniform distribution on the set of s-sparse vectors in R d with all nonzero coefficients equal to σρ. Let χ 2 (P ′ , P ) = (dP ′ /dP ) 2 dP -1 be the chi-square divergence between two mutually absolutely continuous probability measures P ′ and P .

The following lemma is obtained by combining arguments of [START_REF] Baraud | Non asymptotic minimax rates of testing in signal detection[END_REF] and [START_REF] Cai | Minimax Estimation of Linear Functionals Over Nonconvex Parameter Spaces[END_REF].

Lemma 1. For all σ > 0, ρ > 0, 1 ≤ s ≤ d, we have

χ 2 (P µρ , P 0 ) ≤ 1 - s d + s d e ρ 2 s -1.
For completeness, the proof of this lemma is given in the Appendix. We will also need a second lemma, which is a special case of Theorem 2.15 in [START_REF] Tsybakov | Introduction to Nonparametric Estimation[END_REF]: Lemma 2. Let Θ be a subset of R d containing 0. Assume that there exists a probability measure µ on Θ and numbers v > 0, β > 0 such that T (θ) = 2v for all θ ∈ supp(µ) and χ 2 (P µ , P 0 ) ≤ β, Then

inf T sup θ∈Θ P θ | T -T (θ)| ≥ v ≥ 1 4 exp(-β),
where inf T denotes the infimum over all estimators.

Proof of the lower bound (4) in Theorem 1

Set ρ = log(1 + d/s 2 ). Then, by Lemma 1,

(29) χ 2 (P µρ , P 0 ) ≤ 1 - s d + s d 1 + d s 2 s -1 = 1 + 1 s s -1 ≤ e -1.
Next, L(θ) = σsρ for all θ ∈ supp(µ ρ ), and also supp(µ ρ ) ⊆ B 0 (s). Thus, the assumptions of Lemma 2 are satisfied with Θ = B 0 (s), β = e -1, v = σsρ/2 = (1/2)σs log(1 + d/s 2 ) and T (θ) = L(θ). An application of Lemma 2 yields inf T sup θ∈B 0 (s)

P θ | T -L(θ)| ≥ (1/2)σs log(1 + d/s 2 ) ≥ 1 4 exp(1 -e),
which implies (4).

Proof of Theorem 4

We start by rewriting in a more convenient form the lower rates we need to prove. For this, consider separately the cases

s ≥ √ d and s < √ d. Case s ≥ √ d.
The lower rate we need to prove in this case is min{κ 4 , max(σ 2 κ 2 , σ 4 d)}. It is easy to check that we can write it as follows:

min{κ 4 , max(σ 2 κ 2 , σ 4 d)} =    σ 2 κ 2 if κ 4 > σ 4 d 2 , σ 4 d if σ 4 d < κ 4 ≤ σ 4 d 2 , κ 4 if κ 4 ≤ σ 4 d. (30)
Note that the lower rate σ 4 d for σ 4 d < κ

P θ | T -Q(θ)| ≥ (3b/8)σκ ≥ 1 4 exp(-b 2 /4),
where inf T denotes the infimum over all estimators of Q.

P θ | T -Q(θ)| ≥ κ 2 /(2 max(b, 1)) ≥ 1 4 exp(1 -e),
where inf T denotes the infimum over all estimators of Q.

Remark 3. At first sight, the proof of the lower bound seems to exhibit a paradox: the proof for the rate σ 2 κ 2 involves a two-point comparison, while the trivial rate κ 4 needs a more elaborate proof. But, in fact it is not surprising since the rate σ 2 κ 2 is independent from the dimension d, so that it is natural that the proof only uses simple arguments that also hold for d = 1. On the other hand, the bound κ 4 needs a construction based on multiple hypotheses, since the dimension-dependent rate σ 4 d derives from it in view of the above argument.

Proof of Proposition 1

Consider the vectors θ = (κ, 0, . . . , 0) and θ ′ = (κbσ/2, 0, . . . , 0). Clearly, θ and θ ′ belong to B 2 (κ) ∩ B 0 (1). We have

d(θ, θ ′ ) Q(θ) -Q(θ ′ ) = |σ 2 b 2 /4 -κσb| > 3σκb/4,
and the Kullback-Leibler divergence between P θ and P θ ′ satisfies

K(P θ , P θ ′ ) = θ -θ ′ 2 2 2σ 2 = b 2 8 .
We now apply Theorem 2.2 and (2.9) in [START_REF] Tsybakov | Introduction to Nonparametric Estimation[END_REF] to obtain the result.

Proof of Proposition 2

Set ρ = κ/(σ max(b, 1)s). Then ρ 2 ≤ log(1+d/s 2 ) and due to (29) we have χ 2 (P µρ , P 0 ) ≤ e-1. Next, Q(θ) = θ 2 2 = sσ 2 ρ 2 = κ 2 / max(b, 1) for all θ ∈ supp(µ ρ ), which implies supp(µ ρ ) ⊆ B 2 (κ). We also have supp(µ ρ ) ⊆ B 0 (s) by construction. Therefore, the assumptions of Lemma 2 are satisfied with Θ = B 2 (κ) ∩ B 0 (s), β = e -1, v = κ 2 /(2 max(b, 1)) and T (θ) = Q(θ). An application of Lemma 2 yields the result.

Proof of Theorem 2

In order to prove Theorem 2, we will need the following proposition.

Proposition 3. Let b > 0. If κ 2 ≤ b 2 σ 2 s 2 log(1 + d/s 2 ) and 1 ≤ s ≤ d, then inf T sup θ∈B 1 (κ)∩B 0 (s) P θ | T -L(θ)| ≥ κ/(2 max(b, 1)) ≥ 1 4 exp(1 -e),
where inf T denotes the infimum over all estimators.

Proof. We proceed as in the proof of Proposition 2 with the following modifications. We now set ρ = κ/(max(b, 1)σs). Then χ 2 (P µρ , P 0 ) ≤ e -1 and L(θ) = θ 1 = sσρ = κ/ max(b, 1) for all θ ∈ supp(µ ρ ), so that supp(µ ρ ) ⊆ Θ = B 1 (κ) ∩ B 0 (s) and Lemma 2 applies with β = e -1, v = κ/(2 max(b, 1)) and T (θ) = L(θ).

Proof of Theorem 2. First notice that, for an integer s ∈ [1, d], and 0 < q < 1, κ > 0,

B 1 (κ) ∩ B 0 (s) ⊂ B q (r) if s 1-q κ q = r q .

We will prove the theorem by considering separately the cases m = 0 and m ≥ 1.

Case m = 0. Then, r 2 < σ 2 log(1 + d) and the assumption of Proposition 3 is satisfied with s = 1, b = 1, and κ = r. Applying Proposition 3 with these parameters and using [START_REF] Laurent | Adaptive estimation of a quadratic functional by model selection[END_REF] with s = 1 we easily deduce that R * L (B q (r)) ≥ Cr 2 . Case m ≥ 1. We now use the embedding [START_REF] Laurent | Adaptive estimation of a quadratic functional by model selection[END_REF] with s = m. Then [START_REF] Cam | Convergence of estimates under dimensionality restrictions[END_REF] κ

= rm 1-1/q ≥ σm log(1 + d/m 2 )
where the last inequality follows from the definition of m. Furthermore, the fact that m ≥ 1 and the definition of m imply (35)

2 -2/q r 2 m -2/q ≤ r 2 (m + 1) -2/q < σ 2 log(1 + d/(m + 1) 2 ) ≤ σ 2 log(1 + d/m 2 ).
This proves that for κ defined in [START_REF] Cam | Convergence of estimates under dimensionality restrictions[END_REF] we have κ 2 ≤ 2 2/q σ 2 m 2 log(1 + d/m 2 ). Thus, the assumption of Proposition 3 is satisfied with s = m, b = 2 1/q and κ defined in [START_REF] Cam | Convergence of estimates under dimensionality restrictions[END_REF]. Applying Proposition 3 with these parameters and using [START_REF] Laurent | Adaptive estimation of a quadratic functional by model selection[END_REF] with s = m we deduce that R * L (B q (r)) ≥ Cκ 2 . This and (34

) yield R * L (B q (r)) ≥ Cσ 2 m 2 log(1 + d/m 2 )
, which is the desired lower bound.

Proof of Theorem 6

First notice that, for an integer s ∈ [1, d], and 0 < q < 2, κ > 0, [START_REF] Nemirovski | Topics in Nonparametric Statistics[END_REF] B 2 (κ) ∩ B 0 (s) ⊂ B q (r) if s 1-q/2 κ q = r q .

Consider separately the cases m = 0, 1 ≤ m ≤ √ d, and m > √ d. Case m = 0. Then, r 2 < σ 2 log(1 + d) so that the assumption of Proposition 2 is satisfied with s = 1, b = 1, and κ = r. Applying Proposition 2 with these parameters and using [START_REF] Nemirovski | Topics in Nonparametric Statistics[END_REF] with s = 1 and κ = r we get that R * Q (B q (r)) ≥ Cr 4 . Case 1 ≤ m ≤ √ d. We start by using [START_REF] Nemirovski | Topics in Nonparametric Statistics[END_REF] with s = m. Then

(37) κ = rm 1/2-1/q ≥ σ m log(1 + d/m 2 )
where the last inequality follows from the definition of m. For this κ, using [START_REF] Lepski | On estimation of the Lr norm of a regression function[END_REF] we obtain κ 2 ≤ 2 2/q σ 2 m log(1 + d/m 2 ). Thus, the assumption of Proposition 2 is satisfied with s = m, b = 2 2/q and κ defined in [START_REF] Rigollet | Exponential Screening and optimal rates of sparse estimation[END_REF]. Applying Proposition 2 with these parameters and using [START_REF] Nemirovski | Topics in Nonparametric Statistics[END_REF] with s = m we deduce that R * Q (B q (r)) ≥ Cκ 4 . This and (37) prove the lower bound

R * Q (B q (r)) ≥ Cσ 4 m 2 log 2 (1 + d/m 2 ).
To show that R * Q (B q (r)) ≥ Cσ 2 r 2 , we use [START_REF] Nemirovski | Topics in Nonparametric Statistics[END_REF] with s = 1 and κ = r. Now, m ≥ 1, which implies r 2 ≥ σ 2 log(1 + d) ≥ σ 2 (log 2). Thus, the assumption of Proposition 1 is satisfied with s = 1, κ = r, and any 0 < b < √ log 2, leading to the bound R * Q (B 2 (κ) ∩ B 0 (1)) ≥ Cσ 2 r 2 . This inequality and the embedding in [START_REF] Nemirovski | Topics in Nonparametric Statistics[END_REF] 7.9 Proof of the lower bound [START_REF] Ingster | Some problems of hypothesis testing leading to infinitely divisible distributions[END_REF] in Theorem 9

If m = 0 we have r 2 < σ 2 log(1 + d). In this case, set ρ = r/σ, s = 1. Then, ρ < log(1 + d) and due to [START_REF] Juditsky | Nonparametric estimation via convex programming[END_REF] with s = 1 we have χ 2 (P µρ , P 0 ) ≤ 1. Next, θ 2 = θ q = r for all θ ∈ supp(µ ρ ). Thus, supp(µ ρ ) ⊆ B q (r) and the assumptions of Lemma 2 are satisfied with

Θ = B q (r), β = 1, v = r/2 and T (θ) = θ 2 , which implies the bound R * √ Q (B q (r)) ≥ Cr 2 for m = 0. Case 1 ≤ m ≤ √ d.
Use the same construction as in the proof of (20) replacing there s with m. Then, θ 2 = σ m log(1 + d/m 2 ), and θ q = σρm 1/q = σm 1/q log(1 + d/m 2 ) for all θ ∈ supp(µ ρ ). By definition of m, we have σm 1/q log(1 + d/m 2 ) ≤ r guaranteeing that supp(µ ρ ) ⊆ B q (r). Other elements of the argument remain as in the proof of [START_REF]Hoeffding Probability inequalities for sums of bounded random variables[END_REF].

Case m > √ d. Use the same construction as in the proof of ( 20) with s = √ d (assuming without loss of generality that √ d is an integer). Then ρ = √ log 2, θ 2 = σd 1/4 √ log 2, and θ q = σd 1/(2q) √ log 2 ≤ r (by definition of m) for all θ ∈ supp(µ ρ ). Other elements of the argument remain as in the proof of (20).

Proof of the lower bounds in Theorem 12 and in Corollary 2

The following lemma reduces the proof to the argument, which is very close to that of the previous two proofs. Lemma 3. If µ is a probability measure on Θ, then

inf ∆ P 0 (∆ = 1) + sup θ∈Θ P θ (∆ = 0) ≥ 1 -χ 2 (P µ , P 0 )
where inf ∆ is the infimum over all {0, 1}-valued statistics.

Proof. For any {0, 1}-valued statistic ∆,

P 0 (∆ = 1) + sup θ∈Θ P θ (∆ = 0) ≥ P 0 (∆ = 1) + Θ P θ (∆ = 0)µ(dθ) = P 0 (∆ = 1) + P µ (∆ = 0) ≥ 1 -V (P µ , P 0 ) ≥ 1 -χ 2 (P µ , P 0 )
where V (•, •) denotes the total variation distance and the last two inequalities follow from the standard properties of this distance (cf. Theorem 2.2(i) and (2.27) in [START_REF] Tsybakov | Introduction to Nonparametric Estimation[END_REF]).

Proof of the lower bound in Theorem 12 for q = 0. We use a slightly modified argument of Subsection 7.8. As in Subsection 7.8, it suffices to prove the result in the case s < √ d. Then,

ψ √ Q σ (s, d) = σ 2 s log(1 + d/s 2 )
, so that our aim is to show that the lower rate of testing on B 0 (s) is λ = σ s log(1 + d/s 2 ). Fix A ∈ (0, 1). We use Lemma 3 with Θ = Θ 0,s (Aλ) and µ = µ ρ where we take ρ = A log(1 + d/s 2 ). For all θ ∈ supp(µ ρ ) we have θ 2 = σρ √ s = Aλ while supp(µ ρ ) ⊆ B 0 (s) by construction. Hence supp(µ ρ ) ⊆ Θ 0,s (Aλ), so that we can apply Lemma 3. Next, by Lemma 1,

(38) χ 2 (P µρ , P 0 ) ≤ 1 - s d + s d 1 + d s 2 A 2 s -1 ≤ 1 + A 2 s s -1 ≤ exp(A 2 ) -1
where we have used that

(1 + x) A 2 -1 ≤ A 2 x for 0 < A < 1, x > 0.
The last display and Lemma 3 imply that R 0,s (Aλ) ≥ 1exp(A 2 ) -1. Choosing a ε such that exp(a 2 ε ) -1 = ε proves [START_REF] Ingster | Detection boundary in sparse regression[END_REF].

Proof of the lower bound in Theorem 12 for 0 < q < 2 follows along similar lines but now we modify, in the same spirit, the argument of Subsection 7.9 rather than that of Subsection 7.8. The corresponding ρ in Subsection 7.9 is multiplied by a suitable A ∈ (0, 1) and then Lemma 3 is applied. We omit the details.

Proof of the lower bound in Corollary 2. As explained after the statement of Corollary 2, we need only to consider the case s > √ d for the class Θ * s . Then, λ = σd 1/4 / √ s. Instead of µ ρ we consider now a slightly different measure μρ , which is the uniform distribution on the set of s-sparse vectors in R d with nonzero coefficients taking values in {-σρ, σρ}. Then, similarly to Lemma 1,

(P μρ , P 0 ) ≤ 1 - s d + s d cosh(ρ 2 ) s -1, (39) χ 2
cf. formula [START_REF] Johnstone | Thresholding for weighted χ 2[END_REF] in [START_REF] Baraud | Non asymptotic minimax rates of testing in signal detection[END_REF]. Fix A ∈ (0, 1). We now use Lemma 3 with Θ = Θ * s (Aλ) and µ = μρ where we take ρ = Ad 1/4 / √ s. For all θ ∈ supp(μ ρ ) we have |θ j | = σρ = Aσd 1/4 / √ s = Aλ and also supp(μ ρ ) ⊆ { θ 0 = s} by construction. Hence supp(μ ρ ) ⊆ Θ * s (Aλ), so that we can apply Lemma 3. Since s > √ d we have ρ < 1. Using [START_REF] Tsybakov | Introduction to Nonparametric Estimation[END_REF] and the fact that cosh(x) ≤ 1 + x 2 for 0 < x < 1 we obtain

χ 2 (P μρ , P 0 ) ≤ 1 + sρ 4 d s -1 ≤ exp(A 4 ) -1
and we conclude the proof in the same way as it is done after [START_REF] Sampford | Some inequalities on Mills ratio and related functions[END_REF].

Proofs of the upper bounds

We will use the following lemma.

Lemma 4. For X ∼ N (0, 1) and any x > 0 we have

(40) 4 √ 2π(x + √ x 2 + 4) e -x 2 /2 ≤ P |X| > x ≤ 4 √ 2π(x + √ x 2 + 2) e -x 2 /2 , (41) E X 2 1 {|X|>x} ≤ 2 π x + 2 x e -x 2 /2 , (42) E X 4 1 {|X|>x} ≤ 2 π x 3 + 3x + 1 x e -x 2 /2 .
Inequality ( 40) is due to [START_REF] Birnbaum | An inequality for Mills ratio[END_REF] and [START_REF] Sampford | Some inequalities on Mills ratio and related functions[END_REF]. Inequalities (41) and (42) follow from integration by parts.

In this section, we will use the notation

(43) x = 2 log(1 + d/s 2 ), Ŝ = {j : |y j | > σx}, S = {j : θ j = 0}.
We also recall that the observations are of the form y j = θ i + σξ j , j = 1, . . . , d, with i.i.d. errors ξ j ∼ N (0, 1). We will denote by C i , i = 1, 2, . . . , absolute positive constants, and by C absolute positive constants that can vary from line to line.

Proof of the bound (3) in Theorem 1

Clearly, E θ ( d j=1 y j -L(θ)) 2 = σ 2 d. Thus, in view of ( 5), to prove (3) it is enough to show that for s ≤ √ d we have

(44) sup θ∈B 0 (s) E θ ( L * -L(θ)) 2 ≤ Cσ 2 s 2 log(1 + d/s 2 )
where

L * = d j=1 y j 1 {|y j |>σ √ 2 log(1+d/s 2 )}
and C > 0 is an absolute constant. Recalling the notation set in (43) we have

(45) L * -L(θ) = j∈S (y j -θ j ) - j∈S\ Ŝ y j + j∈ Ŝ\S y j .
Thus, for θ ∈ B 0 (s), we obtain

E θ ( L * -L(θ)) 2 ≤ 3 E j∈S σξ j 2 + 3 E θ j∈S y j 1 {|y j |≤σx} 2 + 3 E j∈S c σξ j 1 {|ξ j |>x} 2 ≤ 3σ 2 (s + s 2 x 2 ) + j∈S c E ξ 2 j 1 {|ξ j |>x} ≤ 3σ 2 (s + s 2 x 2 ) + d 2 π x + 2 x e -x 2 /2
(by (41))

≤ 3σ 2 (s + s 2 x 2 ) + s 2 2 π x + 2 x ,
and (44) follows since x ≥ √ 2 log 2 for s ≤ √ d.

Proof of Theorem 3

We will consider only the sparse zone 1 ≤ m ≤ √ d since the cases m = 0 and m > √ d are trivial. Fix θ ∈ B q (r). We will use the notation

d = 1 + d/m 2 , x = 2 2 log d, S = {j : |θ j | > σx/2}. Note that (46) Card( S) ≤ 2r σx q < 2 -q/2 (m + 1) ≤ 2 1-q/2 m,
where the first inequality is due to the fact that θ ∈ B q (r) and the second follows from the definition of m.

Consider first the bias of Lq . Lemma 5 yields

E θ ( Lq ) -L(θ) 2 ≤ C d j=1 min(|θ j |, σx) 2 ≤ C d j=1 |θ j | q (σx) 1-q 2 (47) ≤ C r σx 2q σ 2 log d ≤ Cσ 2 m 2 log d,
where we have used (46). Next, the variance of Lq has the form

Var θ ( Lq ) = d j=1
Var θ (y j 1 {|y j |>σ x} ).

Here, for indices j belonging to S, using (46) we have

j∈ S Var θ (y j 1 {|y j |>σ x} ) ≤ 2 j∈ S Var θ (y j ) + 2 j∈ S Var θ (y j 1 {|y j |≤σ x} ) (48)
≤ 2Card( S)σ 2 (1 + x2 ) ≤ Cσ 2 m log d.
For indices j belonging to Sc , we have

j∈ Sc Var θ (y j 1 {|y j |>σ x} ) ≤ j∈ Sc E θ (y 2 j 1 {|y j |>σ x} ) (49) ≤ 2 j∈ Sc θ 2 j + 2σ 2 j∈ Sc E θ (ξ 2 j 1 {|y j |>σ x} ) ≤ 2 j∈ Sc |θ j | 2 + 2σ 2 j∈ Sc E(ξ 2 j 1 {|ξ j |> √ 2 log d}
).

Using the same argument as in (47) we find (50

) j∈ Sc |θ j | 2 ≤ C d j=1 min(|θ j |, σx) 2 ≤ Cσ 2 m 2 log d.
Finally, (41) implies

σ 2 j∈ Sc E(ξ 2 j 1 {|ξ j |> √ 2 log d} ) ≤ Cσ 2 (d/ d) log d ≤ Cσ 2 m 2 log d (51)
where for the last inequality we have used that log d ≥ log 2 for m ≤ √ d. Combining (48) -(51) we obtain that Var θ ( Lq ) ≤ Cσ 2 m 2 log d.

Together with (41), this yields the desired result:

sup θ∈Bq(r) E θ ( Lq -L(θ)) 2 ≤ Cσ 2 m 2 log d.

Proof of Theorem 5

We will use the notation set in (43). Moreover, we recall the definition of the estimator studied here:

Q * = d j=1 y 2 j -dσ 2 if κ 4 ≥ max{σ 2 κ 2 , σ 4 d}, 0 if κ 4 < max{σ 2 κ 2 ,
Q σ (s, d, κ) = ψ σ (s, d, κ) = max(σ 2 κ 2 , σ 4 d).
To prove this bound, note that

Q * -Q(θ) = 2σ d j=1 θ j ξ j + σ 2 d j=1 (ξ 2 j -1).
Thus, for all θ ∈ B 2 (κ),

E θ ( Q * -Q(θ)) 2 = 4σ 2 E d j=1 θ j ξ j 2 + σ 4 E d j=1 (ξ 2 j -1) 2 = 4σ 2 θ 2 2 + 2σ
Q′ -Q(θ) = j∈S (y 2 j -ασ 2 -θ 2 j ) - j∈S\ Ŝ(y 2 j -ασ 2 ) + j∈ Ŝ\S (y 2 j -ασ 2 ),
where S and Ŝ are defined in (43). Thus, (54)

E θ Q′ -Q(θ) 2 ≤ 3 E θ j∈S (y 2 j -ασ 2 -θ 2 j ) 2 + j∈S\ Ŝ(y 2 j -ασ 2 ) 2 + j∈ Ŝ\S (y 2 j -ασ 2 ) 2 .
For θ ∈ B 2 (κ) ∩ B 0 (s), the first term on the right-hand side satisfies

E θ j∈S (y 2 j -ασ 2 -θ 2 j ) 2 = E j∈S (2σθ j ξ j + σ 2 (ξ 2 j -α)) 2 ≤ 4σ 2 θ 2 2 + 2σ 4 s 2 (α 2 + 3) (55) ≤ 4σ 2 θ 2 2 + 2σ 4 s 2 (25x 4 + 3)
, where the last inequality derives from (53). Hence, using the definition of x in (43) we find

E θ j∈S (y 2 j -ασ 2 -θ 2 j ) 2 ≤ C 1 σ 2 θ 2 2 + σ 4 s 2 log 2 (1 + d/s 2 ) (56) ≤ C 1 σ 2 κ 2 + σ 4 s 2 log 2 (1 + d/s 2 ) .
Furthermore, by definition of Ŝ,

E θ j∈S\ Ŝ(y 2 j -ασ 2 ) 2 ≤ 4σ 4 s 2 log 2 (1 + d/s 2 ) + 2σ 4 s 2 α 2 ≤ C 2 σ 4 s 2 log 2 (1 + d/s 2 )
for any θ ∈ B 0 (s). Finally, α was chosen such that, for any j ∈ S,

E θ y 2 j -ασ 2 1 {|y j |>σx} = σ 2 E X 2 -α 1 {|X|>x} = 0,
where X ∼ N (0, 1). Thus, by independence we have

E θ j∈ Ŝ\S (y 2 j -ασ 2 ) 2 = j ∈S E θ y 2 j -ασ 2 2 1 {|y j |>σx} ≤ σ 4 d E X 2 -α 2 1 {|X|>x} (57) ≤ 16σ 4 d E X 4 1 {|X|>x} since α ≤ 5X 2 on the event {|X| > x}, cf. (53). Now, Lemma 4 implies E θ j∈ Ŝ\S (y 2 j -ασ 2 ) 2 ≤ C 3 σ 4 d x 3 e -x 2 /2 ,
and by definition of x,

E θ j∈ Ŝ\S (y 2 j -ασ 2 ) 2 ≤ C 4 σ 4 s 2 x 3 ≤ (C 4 / 2 log 2)σ 4 s 2 x 4 ≤ C 5 σ 4 s 2 log 2 (1 + d/s 2 ),
where we have used the fact that x ≥ √ 2 log 2. Combining the above displays yields

sup θ∈B 2 (κ)∩B 0 (s) E θ Q′ -Q(θ) 2 ≤ C 6 max(σ 2 κ 2 , σ 4 s 2 log 2 (1 + d/s 2 )).
Remark 4. This proof elucidates why we have chosen the threshold x in the form (43). In (54), the three terms on the right hand side are of the order respectively σ 2 κ 2 + σ 4 s 2 x 4 , σ 4 s 2 x 4 , and σ 4 dx 3 e -x 2 /2 . Among these, the expressions containing x are balanced if σ 4 s 2 x 4 ≍ σ 4 dx 3 e -x 2 /2 , which is equivalent to xe x 2 /2 ≍ d/s 2 . This leads to a choice of x in the form 2 log(d/s 2 )log log(d/s 2 ) ≍ 2 log(d/s 2 ).

Proof of Theorem 7

Fix θ ∈ B q (r). We will prove the theorem only for 1 ≤ m ≤ √ d since the case m = 0 is trivial and the result for the case m > √ d follows from (52) and the fact that θ 2 ≤ θ q ≤ r. In this proof, we will write for brevity α = αm , d = 1 + d/m 2 , x = 2(2 log d) 1/2 . Let J ⊆ {1, . . . , d} be the set of indices corresponding to the m largest in absolute value components of θ, and let |θ| (j) denote the jth largest absolute value of the components of θ. It is easy to see that

|θ| (j) ≤ θ q j 1/q .
This implies

j∈J c θ 2 j = j≥m+1 |θ| 2 (j) ≤ |θ| 2-q (m) j≥m+1 |θ| q (j) ≤ θ q m 1/q 2-q θ q q = θ 2 q m 1-2/q .
Therefore, since θ ∈ B q (r) and due to the definition of m,

j∈J c θ 2 j ≤ r 2 m 1-2/q ≤ σ 2 m log d, (58)

and

(59)

∀ j ∈ J c : |θ j | ≤ rm -1/q ≤ σ log d ≤ σx/2.
We have

Qq -Q(θ) = j∈J y 2 j -ασ 2 -θ 2 j - j∈J\ S y 2 j -ασ 2 (60) + j∈ S\J y 2 j -ασ 2 - j∈J c θ 2 j ,
where S = {j : |θ j | > σx/2}. Consider the first sum on the right hand side of (60). Since Card(J) = m, and α ≤ 40 log d (which is obtained analogously to (53) recalling that now α = αm instead of α = α s ), the same argument as in (56) leads to

E θ j∈J y 2 j -ασ 2 -θ 2 j 2 ≤ C(σ 2 θ 2 2 + σ 4 m 2 log 2 d). (61)
Next, consider the second sum on the right hand side of (60). By definition of S,

E θ j∈J\ S y 2 j -ασ 2 2 ≤ j∈J σ 2 (x + α) 2 ≤ Cσ 4 m 2 log 2 d. (62)
Let us now turn to the third sum on the right hand side of (60). The bias-variance decomposition yields

E θ j∈ S\J y 2 j -ασ 2 2 = E θ j∈J c (y 2 j -ασ 2 ) 1 {|y j |>σ x} 2 = j∈J c
Var θ (y 2 jασ 2 )

1 {|y j |>σ x} + j∈J c E θ (y 2 j -ασ 2 ) 1 {|y j |>σ x} 2 .
Here,

Var θ (y 2 j -ασ 2 ) 1 {|y j |>σ x} ≤ E θ (y 2 j -ασ 2 ) 1 {|y j |>σ x} 2 ≤ CE θ (θ 4 j + σ 4 ξ 4 j + α 2 σ 4 ) 1 {|y j |>σ x} ≤ C θ 4 j + α 2 σ 4 + σ 4 E ξ 4 j 1 {|ξ j |>x/2}
(by ( 59)).

Using now the same argument as in (57) to bound E ξ 4 j 1 {|ξ j |>x/2} we obtain

j∈J c Var θ (y 2 j -ασ 2 ) 1 {|y j |>σ x} ≤ C j∈J c θ 4 j + σ 4 m 2 log 2 d ≤ C j∈J c θ 2 j 2 + σ 4 m 2 log 2 d .
Furthermore, by Lemma 6,

j∈J c E θ (y 2 j -ασ 2 ) 1 {|y j |>σ x} ≤ C j∈J c θ 2 j .
Combining the above displays leads to the following bound :

E θ j∈ S\J y 2 j -ασ 2 2 ≤ C j∈J c θ 2 j 2 + σ 4 m 2 log 2 d . (63)
From ( 60) -(63) we deduce that

E θ ( Qq -Q(θ)) 2 ≤ C σ 2 θ 2 2 + j∈J c θ 2 j 2 + σ 4 m 2 log 2 d .
The result now follows if we use (58) and note that θ 2 ≤ θ q ≤ r.

Proof of the upper bound (19) in Theorem 8

Fix θ ∈ B 0 (s) and set for brevity τ = ψ

√ Q σ (s, d) 1/2 . We will bound the risk E θ ( N -θ 2 ) 2
separately for the cases θ 2 ≤ τ and θ 2 > τ .

Case θ 2 ≤ τ . Using the elementary inequality (ab) 2 ≤ 2(a 2b 2 ) + 4b 2 , we find

E θ ( N -θ 2 ) 2 ≤ 2 E θ (max{ Q• , 0} -Q(θ)) + 4Q(θ) ≤ 2 E θ ( Q• -Q(θ)) 2 1/2 + 4τ 2 .
Note that Q• = Q if we set κ = τ in the definition of Q. Furthermore, θ ∈ B 0 (s) and, in the case under consideration θ belongs to B 2 (τ ). Now, use that for all θ ∈ B 2 (τ ) ∩ B 0 (s), due to Theorem 5, we have

E θ ( Q• -Q(θ)) 2 ≤ Cψ Q σ (s, d, τ ).
Using this inequality and the fact that

ψ Q σ (s, d, τ ) = ψ √ Q σ (s, d) 2
, we obtain the desired rate:

E θ ( N -θ 2 ) 2 ≤ C 7 ψ √ Q σ (s, d) + 4τ 2 = (C 7 + 4)ψ √ Q σ (s, d). Case θ 2 > τ . Using the elementary inequality ∀ a > 0, b ≥ 0, (a -b) 2 ≤ (a 2 -b 2 ) 2 /a 2 , we find E θ ( N -θ 2 ) 2 ≤ E θ ( Q• -Q(θ)) 2 θ 2 2 . Now, we bound E θ ( Q• -Q(θ)) 2
along the lines of the proof of Theorem 5. In particular, if s ≥ √ d we have Q• = Q * , τ = σd 1/4 and using (52) we obtain

E θ ( Q• -Q(θ)) 2 θ 2 2 ≤ 4σ 2 + 2σ 4 d θ 2 2 ≤ 4σ 2 + 2σ 4 d τ 2 ≤ C 8 σ 2 √ d, which is the desired rate. If s < √ d, we have Q• = Q′ , τ = σ s log(1 + d/s 2
) and using (56) and the subsequent bounds in the proof of Theorem 5, we obtain

E θ ( Q• -Q(θ)) 2 θ 2 2 ≤ 3 C 1 σ 2 θ 2 2 + (C 1 + C 2 + C 5 )σ 4 s 2 log 2 (1 + d/s 2 ) θ 2 2 (64) ≤ C 9 σ 2 + σ 4 s 2 log 2 (1 + d/s 2 ) τ 2 ≤ C 10 σ 2 s log(1 + d/s 2 ),
which is again the desired rate.

Proof of the upper bound (21) in Theorem 9

The case m = 0 is trivial. For m ≥ 1, we use the same method of reduction to the risk of estimators of Q as in the proof of [START_REF] Golubev | An oracle approach to adaptive estimation of linear functionals in a Gaussian model[END_REF]. The difference is that now we set τ = ψ

√ Q σ,q (r, d) 1/2 ,
we replace s by m, and we apply Theorem 7 rather than to Theorem 5. In particular, an analog of (64) with s = m is obtained using (61).

Proof of Theorem 10

Here, we will use the notation set in (43). As in the proof of the bound (3) and with the same notation, we have, for θ ∈ B 0 (s),

E θ ( L -L(θ)) 2 ≤ 3E j∈S σξ j 2 + 3E θ j∈S y j 1 {|y j |≤σx} 2 + 3E j∈S c σξ j 1 {σ|ξ j |>σx} 2 ≤ 3 (sσ 2 + s 2 E θ (σ 2 )x 2 ) + σ 2 j∈S c E ξ 2 j 1 {σ|ξ j |>σx} .
Here,

E θ ξ 2 j 1 {σ|ξ j |>σ √ 2 log(1+d/s 2 )} = E θ ξ 2 j 1 {σ|ξ j |>σ √ 2 log(1+d/s 2 )} 1 {σ>σ} + E θ ξ 2 j 1 {σ|ξ j |>σ √ 2 log(1+d/s 2 )} 1 {σ≤σ} .
The first term on the right hand side satisfies

E θ ξ 2 j 1 {σ|ξ j |>σ √ 2 log(1+d/s 2 )} 1 {σ>σ} ≤ E θ ξ 2 j 1 {|ξ j |> √ 2 log(1+d/s 2 )} ≤ Cs 2 d log(1 + d/s 2 ) (by (41)).
For the second term, we use Lemma 7 to get

E θ ξ 2 j 1 {σ|ξ j |>σ √ 2 log(1+d/s 2 )} 1 {σ≤σ} ≤ E(ξ 4 1 ) P θ (σ ≤ σ) ≤ C √ d exp(- √ d/C).
Combining the above displays and using Lemma 7 to bound E θ (σ 2 ) we obtain

E θ ( L -L(θ)) 2 ≤ Cσ 2 s 2 log(1 + d/s 2 ).

Proof of Theorem 11

Set S = {j : |y j | ≥ σ√ 2 log d} and recall that S = {j : θ j = 0}. As in the proof of Theorem 5 we get

E θ Q -Q(θ) 2 ≤ 3 E θ j∈S (y 2 j -θ 2 j ) 2 + j∈S\ S y 2 j 2 + j∈ S\S y 2 j 2 .
We bound separately the three terms on the right hand side. For θ ∈ B 2 (κ) ∩ B 0 (s), the first term on the right-hand side satisfies, due to (56) with α = 0,

E θ j∈S (y 2 j -θ 2 j ) 2 ≤ C σ 2 θ 2 2 + σ 4 s 2 ≤ C σ 2 κ 2 + σ 4 s 2 . ( 65
)
Using Lemma 7 we find

E θ j∈S\ S y 2 j 2 = E θ j∈S y 2 j 1 {|y j |<σ √ 2 log d} 2 ≤ s 2 E θ (σ 4 )(2 log d) 2 ≤ Cσ 4 s 2 log 2 d. (66)
Finally, we write the third term as follows

E θ j∈ S\S y 2 j 2 = E θ j ∈S σ 2 ξ 2 j 1 {σ|ξ j |>σ √ 2 log d} 2 ≤ 2(A 1 + A 2 ) (67)
where

A 1 = E θ d j=1 σ 2 ξ 2 j 1 {σ|ξ j |>σ √ 2 log d} 1 {σ> √ 2σ} 2 , A 2 = E θ d j=1 σ 2 ξ 2 j 1 {σ≤ √ 2σ} 2 .
Using (42) we obtain

A 1 ≤ σ 4 E θ d j=1 ξ 2 j 1 {|ξ j |>2 √ log d} 2 ≤ 2σ 4 d 2 E X 4 1 {|X|>2 √ log d} (68) ≤ Cσ 4 (log d) 3/2
where X ∼ N (0, 1). Next,

A 2 ≤ σ 4 E θ d j=1 ξ 2 j 1 {σ≤ √ 2σ} 2 ≤ σ 4 d 2 max 1≤j≤d E θ ξ 4 j 1 {σ≤ √ 2σ} .
Using (42) we find

E θ ξ 4 j 1 {σ≤ √ 2σ} ≤ E θ ξ

Appendix: Auxiliary lemmas

Proof of Lemma 1. We first follow the lines of the proof of Theorem 7 in [START_REF] Cai | Minimax Estimation of Linear Functionals Over Nonconvex Parameter Spaces[END_REF] and then apply a result of [START_REF] Aldous | Exchangeability and Related Topics, École d'été de Saint-Flour XIII -1983[END_REF] (cf. also Section 6 in [START_REF]Hoeffding Probability inequalities for sums of bounded random variables[END_REF]) in the same spirit as it was done in [START_REF] Baraud | Non asymptotic minimax rates of testing in signal detection[END_REF]. Let ϕ σ be a density of normal distribution with mean 0 and variance σ 2 . For I ∈ S(s, d), let g I (y 1 , . . . , y d ) = .

As shown in [START_REF] Aldous | Exchangeability and Related Topics, École d'été de Saint-Flour XIII -1983[END_REF], J coincides in distribution with the conditional expectation E[Z|B] where Z is a binomial random variable with parameters (s, s/d) and B is a suitable σ-algebra. This fact and Jensen's inequality lead to the following bound implying the lemma:

g 2 f ≤ E exp(ρ 2 Z) = 1 - s d + s d e ρ 2 s .
In the next two lemmas, we will use the notation D i (t) = E X i 1 {X>t} for i ≥ 0, t > 0, where X ∼ N (0, 1). Clearly, D 0 (t) = 1 -Φ(t), and D 1 (t) = φ(t) where Φ and φ are the standard normal c.d.f. and density respectively. For i ≥ 2 integration by parts gives D i (t) = t i-1 φ(t) + (i -1)D i-2 (t). It follows that D i (t) = O(t i-1 e -t 2 /2 ) as t → ∞, and each D i as well as each of its derivatives is uniformly bounded. Since all D i and their derivatives are uniformly bounded the result follows.

Lemma 6. Let y ∼ N (a, σ 2 ), and τ > 0. Let α be such that E (X 2α) 1 {|X|>τ } = 0, where X ∼ N (0, 1). Then there exists C > 0 such that

E (y 2 -ασ 2 ) 1 {|y|>στ } ≤ Ca 2 .
Proof. We have where S = {j : θ j = 0}. For any i ∈ S ∩ F and any j ∈ S c ∩ F c , we have

y 2 i ≤ σ 2 ξ 2 j .
Furthermore, Card(S ∩ F ) = Card(S c ∩ F c ). Therefore,

σ2 ≤ 9σ 2 d i∈S c ξ 2 i .
This implies (70). We now prove (71). Let G be the set of indices i corresponding to the ⌊d -√ d⌋ smallest y 2 i . Here, ⌊x⌋ denotes the largest integer less than or equal to x. The first term on the right hand side of (72) satisfies where C > 0 is an absolute constant. Finally, the second term on the right hand side of (72) satisfies

P max i∈S c ξ 2 i ≥ √ d 18 ≤ d exp - √ d 36
in view of [START_REF] Verzélen | Minimax risks for sparse regressions: Ultra-high dimensional phenomenons[END_REF]. Plugging the last two displays in (72) we obtain (71).

Proposition 2 .

 2 Let b > 0. If κ 4 ≤ b 2 σ 4 s 2 log 2 (1 + d/s 2 ) and 1 ≤ s ≤ d, then inf T sup θ∈B 2 (κ)∩B 0 (s)

  with s = 1 yield the result. Case m > √ d. It suffices to note that the argument used above in the case 1 ≤ m ≤ √ d remains valid for m > √ d and s = √ d instead of s = m (assuming without loss of generality that √ d is an integer).

7. 8

 8 Proof of the lower bound (20) in Theorem 8 Let s < √ d. Set ρ = log(1 + d/s 2 ). Due to (29) we have χ 2 (P µρ , P 0 ) ≤ e -1. Next, θ 2 = σρ √ s = σ s log(1 + d/s 2 ) for all θ ∈ supp(µ ρ ), and supp(µ ρ ) ⊆ B 0 (s) by construction. Therefore, the assumptions of Lemma 2 are satisfied with Θ = B 0 (s), β = e -1, v = σ s log(1 + d/s 2 )/2 and T (θ) = θ 2 . An application of Lemma 2 yields the result for s < √ d. To obtain the lower bound for s ≥ √ d, it suffices to consider the case s = √ d (assuming without loss of generality that √ d is an integer) and to repeat the above argument with this value of s.

ϕ 1 where 2

 12 σ (y jf j ) where f j = σρ1 j∈I . The density of P µρ is f is a density of n i.i.d. normal random variables with mean 0 and variance σ 2 . Now, I∈S(s,d) I ′ ∈S(s,d)g I g I ′ f .It is easy to see thatg I g I ′ f = exp(ρ 2 Card(I ∩ I ′ )), which implies g 2 f = E exp(ρ 2 J)where J is a random variable with hypergeometric distribution,

Lemma 5 .

 5 Let y ∼ N (a, σ 2 ) and T = y 1 {|y|>στ } where τ > 0. Set B(a) = E( T )a. Then there exists C > 0 such that |B(a)| ≤ C min(|a|, στ ). Proof. Note that B(a) = E(y 1 {|y|≤στ } ), so that |B(a)| ≤ στ. Thus, it remains to show that there exists C > 0 such that |B(a)| ≤ C|a|. We have B(a) = a D 0 (τ + a/σ) + D 0 (τa/σ) + σ D 1 (τ + a/σ) -D 1 (τa/σ) .

E (y 2 -Lemma 7 . 2 i -σ 2 i∈S c ∩F c ξ 2 i

 27222 ασ 2 ) 1 {|y|>στ } = σ 2 D 2 (τ + a/σ) + D 2 (τa/σ) + 2aσ D 1 (τ + a/σ) -D 1 (τa/σ) + (a 2ασ 2 ) D 0 (τ + a/σ) + D 0 (τa/σ) .Using that D 0 is bounded and D 1 is Lipschitz continuous, we see that it is enough to check the condition |f (a)| ≤ Ca 2 forf (a) = σ 2 D 2 (τ + a/σ) + D 2 (τa/σ)α D 0 (τ + a/σ) + D 0 (τa/σ) .Now, f (0) = 0 by definition of α and f ′ (0) = 0 because f is symmetric. Since the second derivatives of D 2 and D 0 are uniformly bounded Taylor's theorem gives the result. For any θ such that θ 0 ≤ √ d we have(70) E θ (σ 2 ) ≤ 9σ 2 , E θ (σ 4 ) ≤ Cσ 4 , and(71)P θ (σ ≤ σ) ≤ Cd exp(-√ d/C)for some absolute constant C > 0.Proof. Since θ 0 ≤ √ Denote by F the set of indices i corresponding to the dθ 0 smallest values y 2 i

P 3 i∈S c ξ 2 i 3 i∈S c ξ 2 i

 232 ≤ d ≤ P U D -D ≤ -2d/3 + √ dwhere D = Card(S c ), and U D is a χ 2 random variable with D degrees of freedom. A standard bound on the tails of χ 2 random variables (see, e.g.[START_REF] Laurent | Adaptive estimation of a quadratic functional by model selection[END_REF]) yieldsP(U D -D ≤ -t) ≤ exp(-t 2 /(4D)), ∀ t > 0.Thus, for d > 2, we obtainP ≤ d ≤ exp(-(2d/3 -√ d) 2 /(4D)) ≤ exp(-d/C)

  σ 4 d}. The upper bound κ 4 for κ 4 < ψ σ (s, d, κ) is trivial since the risk of the zero estimator is equal to κ 4 . Let now κ 4 ≥ ψ σ (s, d, κ). We analyze separately the cases s ≥ √ d, κ 4 ≥ ψ σ (s, d, κ), and s < √ d, κ 4 ≥ ψ σ (s, d, κ). Case s ≥ √ d and κ 4 ≥ ψ σ (s, d, κ). Then, Q = Q * and Theorem 5 claims a bound with the rate ψ

  4 d ≤ 6 max(σ 2 κ 2 , σ 4 d). = max(σ 2 κ 2 , σ 4 s 2 log 2 (1 + d/s 2 )).Here and below in this proof, we set for brevity α = α s .

	(52)
	Case s <	√	d and κ 4 ≥ ψ σ (s, d, κ). Then, Q = Q′ where
					d
				Q′ =	j=1	(y 2 j -ασ 2 ) 1 {|y j |>σ	√	2 log(1+d/s 2 )}
	and ψ Q σ (s, d, κ) Let x be defined in (43). Since s < that, for s ≤ √ d,	√ d, we have x ≥	√ 2 log 2. Using Lemma 4, we find
	(53)	α =	E X 2 1 {|X|>x} P |X| > x	≤ (x + 2/x)(x + 1) ≤ 5x 2 = 10 log(1 + d/s 2 ).
	Similarly to (45), we get

  (log d) 3/2 + 16(log d) 2 P θ (σ ≤ √ 2σ).The last two displays and the bound for P θ (σ ≤ √ 2σ) from Lemma 7 yieldA 2 ≤ Cσ 4 (log d) 3/2 .

	C d 2 (69) ≤	4 j 1 {|ξ j |>2 √ log d} + E θ ξ 4 j 1 {|ξ j |≤2 √ log d} 1 {σ≤	√ 2σ}
	Combining (65) -(69) proves the theorem.

  Then we have

	Thus,
	(72)	P θ (σ ≤	√	2σ) ≤ P 9σ 2 ≤ P 9 i∈S c i∈S c ξ 2 i ≤ 3d + P 18 max ξ 2 i -18 √ dσ 2 max i∈S c ξ 2 i ≤ 2dσ 2 i∈S c ξ 2 i ≥ √ d .
	j≤d-where we have used that Card(G c ) ≤ 2 √ d y 2 (j) = i∈G y 2 i ≥ σ 2 √ i∈S c ∩G d. This implies: ξ 2 i ≥ σ 2 i∈S c	ξ 2 i -2 √	d σ 2 max i∈S c ξ 2 i ,
				σ2 ≥	9σ 2 d i∈S c	ξ 2 i -	18σ 2 √ d	max i∈S c ξ 2 i .

Acknowledgement

We would like to thank Nicolas Verzelen for remarks on the text that helped to improve the presentation. The work of A.B.Tsybakov was supported by GENES and by the French National Research Agency (ANR) under the grants IPANEMA (ANR-13-BSH1-0004-02), Labex ECODEC (ANR -11-LABEX-0047), and ANR -11-IDEX-0003-02. It was also supported by the "Chaire Economie et Gestion des Nouvelles Données", under the auspices of Institut Louis Bachelier, Havas-Media and Paris-Dauphine.


Renaud Hédouin

Olivier Commowick

Aymeric Stamm

Christian Barillot

Interpolation and Averaging of Multi-Compartment Model Images

Multi-compartment diffusion models (MCM) are increasingly used to characterize the brain white matter microstructure from diffusion MRI. We address the problem of interpolation and averaging of MCM images as a simplification problem based on spectral clustering. As a core part of the framework, we propose novel solutions for the averaging of MCM compartments. Evaluation is performed both on synthetic and clinical data, demonstrating better performance for the "covariance analytic" averaging method. We then present an MCM template of normal controls constructed using the proposed interpolation.

Introduction

Diffusion Weighted Imaging (DWI) is a unique MRI acquisition strategy, which can provide invaluable insights into the white matter architecture in-vivo and non-invasively. A number of diffusion models have been devised, with the aim to characterize the underlying tissue microstructure. The most widespread model is known as Diffusion Tensor Imaging (DTI) [START_REF] Basser | Microstructural and physiological features of tissues elucidated by quantitative diffusion-tensor MRI[END_REF] which, under the assumption of homogeneous diffusion in each voxel, describes the random motion of water as a single Gaussian process with a diffusion tensor. However, many regions of crossing fibers exist in low-resolution clinical DWI and the DTI model fails at correctly representing them. Multi-compartment models (MCM) have been extensively proposed and studied as alternative diffusion models to cope with the intrinsic voxelwise diffusion heterogeneity [START_REF] Ferizi | A ranking of diffusion MRI compartment models with in vivo human brain data[END_REF]. The key principle of MCM is to explicitly model the diffusion in a number of pre-specified compartments akin to groups of cells inducing similar diffusion properties. MCMs may have a great impact on patient care, as they allow for a better characterization of brain tissue microstructure, which enables the identification of more specific biomarkers such as proportion of free water (edema), proportion of water in axons (partial disruption or complete loss of axons, axonal injury), etc.

A critical step to identify relevant biomarkers on a large database is the creation of an atlas from individual estimated MCM images. This is achieved using registration and interpolation of MCMs. To date, only few approaches have addressed this issue. Among them, Barmpoutis et al. [START_REF] Barmpoutis | Registration of high angular resolution diffusion MRI images using 4th order tensors[END_REF] or Geng et al. [START_REF] Geng | Diffusion MRI Registration Using Orientation Distribution Functions[END_REF] introduced registration methods specifically tuned for Orientation Distribution Functions (ODF) on the sphere. Goh et al. [START_REF] Goh | A nonparametric Riemannian framework for processing high angular resolution diffusion images and its applications to ODF-based morphometry[END_REF] introduced an interpolation method for ODFs in a spherical harmonics basis as a Riemannian average. However, this approach does not apply to MCMs as they are not expressed in the same basis. Taquet et al. [START_REF] Taquet | Registration and analysis of white matter group differences with a multi-fiber model[END_REF] proposed an interpolation approach seen as a simplification problem of all weighted compartments from a set of voxels into a smaller set of compartments. However, they assume that a single compartment belongs to the exponential family which is not the case for all MCMs.

We introduce a new interpolation method for MCM images also as a simplification problem. It relies on the fuzzy spectral clustering [START_REF] Ng | On spectral clustering: Analysis and an algorithm[END_REF] of input compartments, from MCMs provided e.g. from trilinear interpolation, into a predefined number of output compartments. Then, each cluster is used to compute an interpolated compartment, providing an output MCM. This method is very generic as it relies only on the definition of a similarity measure between compartments and of a weighted averaging scheme for compartments. It can therefore be applied to any MCM as long as those two components may be defined.

In the following, we present MCM interpolation / averaging as a simplification problem based on spectral clustering (Section 2.1). Then, we define 4 possible compartment averaging methods for the Diffusion Directions Imaging (DDI) model [START_REF] Stamm | A new multi-fiber model for low angular resolution diffusion mri[END_REF] in Section 3 and similarity measures related to each of those averaging schemes. We demonstrate qualitatively and quantitatively the interest of both the averaging schemes and interpolation framework on simulated and in vivo data. We finally apply this framework to compute an atlas of DDI (Section 3) which clearly highlights average crossing fiber regions.

Theory

Model interpolation as a simplification problem

We consider m MCM M i (i = 1, ..., m) each containing c(i) compartments of constrained water diffusion and a free water compartment describing isotropic unconstrained water diffusion. We note F i j the j-th compartment of M i and F i free its free water compartment, their respective weights being w i j and w i free and sum to 1. Each of these M i has an associated weight α i . For example, in the case of a trilinear interpolation, we have 8 MCM with spatial weights α i . We formulate the interpolation problem as merging the M i into one MCM with a predetermined number of compartments q and one free water compartment. There are therefore two different averaging parts: compartments and free water compartment.

The averaging of all compartments coming from M i into q compartments is performed using spectral clustering [START_REF] Ng | On spectral clustering: Analysis and an algorithm[END_REF]. Having defined a similarity matrix S between compartments, spectral vectors are extracted from S. These spectral vectors are then clustered using fuzzy C-Means. Hence, we obtain q sets of n weights (n being the total number of compartments) β i j,k that are probabilities for the j-th compartment of M i to belong to the k-th cluster. We define θ i j,k the weight of the j-th compartment of M i in the k-th cluster and θ i the weight of the free water compartment of M i :

θ i j,k = α i w i j β i j,k , θ i = α i w i free (1)
From θ i j,k and θ i , we compute weights φ k and φ free of the output compartments.

∀k = 1, ..., q φ k = m i=1 c(i) j=1 θ i j,k , φ free = m i=1 θ i (2)
We also define θi j,k and θi two different sets of normalized weights from θ i j,k and θ i . This framework is very generic and can be applied to any MCM as long as we provide a way to compute a similarity matrix between compartments. Free water averaging is common to any MCM and is described in Section 2.2. We derive MCM compartments averaging for DDI in Section 2.3 and similarity matrix computation in Section 2.4.

Free water compartments averaging

We estimate from the isotropic diffusivities d i free of M i the diffusivity d free of the average model associated to weight φ free . Free diffusion follows an isotropic Gaussian distribution with covariance matrix D i free = d i free I 3 (where I 3 is the identity matrix). The averaging is performed using the log-Euclidean framework [START_REF] Arsigny | Log-Euclidean metrics for fast and simple calculus on diffusion tensors[END_REF]:

D free = exp( m i=1 θi log(D i free )) ⇒ d free = exp( m i=1 θi log(d i free )) (3)

MCM Compartments Averaging

We propose four different methods to average DDI compartments into a single one: classic, tensor, log VMF, and covariance analytic. For each cluster k, we wish to average the set of F i j with weights θi j,k into a compartment C k with weight φ k . To simplify notations, we now just consider n compartments F i (i = 1, ..., n) with their corresponding weights w i .

Specification of the DDI model

Each MCM has specific parameters and models for compartments. The compartment averaging part therefore cannot be exactly similar for any MCM. We choose to detail several compartments averaging methods for one particular MCM: the DDI model.

In addition to the free water compartment, a number of axonal compartments can be added to DDI to model how water molecules diffuse in axonal bundles with various orientations. Diffusing water molecules in a particular axonal compartment are assumed to undergo a random displacement that is the independent sum of a von Mises & Fisher (VMF) vector on S 2 of radius r and a Gaussian vector on R 3 . Hence, the resulting diffusion probability density function describing this random displacement is given by the 3D convolution of the VMF distribution with the Gaussian distribution:

p µ,κ,d,ν = Convolution(VMF(µ, κ, r), Gaussian(0, (1 -ν)d κ + 1 [I 3 + κµµ T ]) (4)
where µ ∈ S 2 is the principal axis of diffusion, κ an index of the concentration of diffusion around µ, d the diffusivity along µ, ν the proportion of extra-axonal space in the compartment, r the radius of the VMF sphere given by r = √ νd. Σ is the covariance matrix of the Gaussian part. Let µ i , κ i , ν i , d i be the parameters of F i and µ, κ, ν, d be the parameters of the average compartment F .

Common part of compartment averaging

We choose to average the sphere of radius r as the one whose surface is the average of the input sphere surfaces. This corresponds to a Euclidean average of the individual r 2 i :

r 2 = n i=1 w i r 2
i . This also gives us a direct relation between ν and d leading to only 3 parameters to estimate (µ, κ and ν), d being computed as d = r 2 /ν.

Simple averaging

The simplest approach performs a weighted Euclidean averaging on each parameter except µ. Each µ i is a direction in S 2 . However, for the DDI model, they do not represent a direction but an orientation. The simplest way to solve this problem (as two opposite directions) is to put all µ i in the top hemisphere and average them on the sphere to obtain µ.

Tensor averaging

The simple averaging is however only a partial solution, especially for directions close to the sphere equator. We now consider µ i as orientations instead of directions. µ i is represented as a cigar-shaped tensor T i ∈ S + 3 (R) defined as:

T i = µ i µ T i + εI 3 (5)
With ε small to have non degenerated tensors. Then, we can average T i using the log-Euclidean framework similarly to Eq. (3). We define the average µ as the principal direction of T (eigenvector with the largest eigenvalue). The other parameters are obtained as for simple averaging.

Covariance analytic

Another approach uses information from covariance matrices Σ i of DDI compartments. These Σ i matrices belong to S + 3 (R) and can be averaged into Σ similarly to Eq. ( 3). We wish to extract all parameters from the average Σ. We start by approximating Σ by a cigar-shaped tensor to match the DDI compartment model. To do that, we need to enforce two equal secondary eigenvalues λ ⊥ . In the log-Euclidean framework, this amounts to compute λ ⊥ as λ ⊥ = √ λ 2 λ 3 where λ 2 , λ 3 are the two lowest eigenvalues of Σ. We now have Σ the cigar-shaped tensor of F :

Σ = (1 -ν)d κ + 1 [I 3 + κµµ T ] (6)
Proceeding by identification and given that r 2 = νd, we obtain that µ is the principal eigenvector of Σ. ν and κ are given by:

ν = r 2 λ + r 2 , κ = 2 λ -λ ⊥ λ ⊥ (7)
2.3.6 log VMF We now explore the option to use the VMF to compute µ and κ and recover only ν from Σ. We consider a VMF distribution as a point in a Riemannian manifold, similarly to the approach presented by McGraw et al. [START_REF] Mcgraw | Von Mises-Fisher mixture model of the diffusion ODF[END_REF]. To interpolate several points, a geodesic on these manifolds is defined (refer to [START_REF] Mcgraw | Von Mises-Fisher mixture model of the diffusion ODF[END_REF] for details). Orientation averaging is similar to tensor averaging as in Section 2.

l κ = n i=1 w i log( κ i κ ) (8)
κ = κ exp(l κ ) (9)
Knowing all parameters except ν, we obtain it from Σ as:

ν = r 2 [2r 2 + λ + λ ⊥ (1 + κ)] 2(r 2 + λ)[r 2 + λ ⊥ (1 + κ)] (10)

Similarity measure between compartments

To perform spectral clustering, we need a similarity measure between compartments. To stay coherent with the compartment averaging part, they are defined following metrics associated with each method. In each case except covariance analytic, we compute separately the distance between µ, κ, r and add them with normalization terms α, β to give each parameters the same influence. For two compartments F 1 and F 2 , the similarity measures are defined as follows:

         d simple (F 1 , F 2 ) =< µ 1 , µ 2 > 2 +α|κ 1 -κ 2 |+β|r 1 -r 2 | d tensor (F 1 , F 2 ) = ||log(T 1 ) -log(T 2 )||+α|κ 1 -κ 2 |+β|r 1 -r 2 | d logVMF (F 1 , F 2 ) = ||log(T 1 ) -log(T 2 )||+α|log(κ 1 ) -log(κ 2 )|+β|r 1 -r 2 | d covariance analytic (F 1 , F 2 ) = ||log(Σ 1 ) -log(Σ 2 )|| ( 11
)
3 Experiments and Results

Compartment averaging evaluation on simulated data

We first evaluate compartment averaging into a single one. To do so, we simulate random DDI compartments by drawing parameter values from uniform distribution between different bounds depending on the parameter: 0 and 20 for κ, 5.10 -4 m.s -2 and 5.10 -3 m.s -2 for d, 0 and 1 for ν, and random orientation on S 2 for µ. Four random DDI compartments are computed, they correspond to the four corners of a grid of size 11 × 11 that we want to extrapolate. To perform a robust experiment, we created a database of 500 sets of 4 corners. The reference is a grid containing 4 compartments pixel with a weight proportional to the position of the voxel with respect to each corner (see Fig. 1.e). For each method, we average each pixel of the reference image into only one DDI compartment.

To quantitatively evaluate DDI averaging, we simulate, for each method and the reference, a DWI signal from DDI models following Eq. ( 6) in [START_REF] Stamm | A new multi-fiber model for low angular resolution diffusion mri[END_REF] on 60 directions for each of 3 different b-values. A Euclidean distance between simulated DWIs of the 4 methods and the reference provides quantitative results. The Euclidean distances on the 500 random images are normalized so that the simple error mean is 100. The result for the different methods are: simple: 100, tensor: 31.6, log VMF: 28.0, covariance analytic: 11.1. We present in Fig. 1 representative images from averaged DDI models superimposed on the corresponding error maps. The simple method has a large error explained by direction averaging. The tensor method is better: thanks to the orientation averaging part. However, there are still large errors which can be explained by large κ values in regions averaging orthogonal directions, which is not realistic. log VMF suffers from the same problem as tensor. Covariance analytic performs much better than all other methods. This is mainly due to smaller errors in crossing fibers. This is logical as when two orthogonal compartments are averaged, the best single compartment representing them is almost spherical, meaning a low κ value. The Euclidean distance map in the DWI signal confirms this idea.

MCM extrapolation on real data

The second experiment was to test the entire MCM interpolation pipeline including spectral clustering and free water compartment averaging. We tested methods on a set of 20 real DDI images estimated from DWI with 128 × 128 × 55 voxels with a 2 × 2 × 2mm 3 resolution, 30 gradient directions with one b-value = 1000 s.mm -2 . In order to assess the quality of interpolation, we extrapolate voxels from their neighborhood. To do so, one in every two voxels are removed and extrapolated from the known remaining values. Input DDI models have three compartments, and so will the extrapolated DDI. Again we compute the Euclidean distance between extrapolated DDI and the original one on the DWI corresponding images. Means are respectively simple: 100, tensor: 84.6, log VMF: 107.0, covariance analytic: 66.2. These results show that covariance analytic performs significantly better than all other methods (paired t-test, p < 1.0 × 10 -5 ) also when used in the complete MCM interpolation framework on real data.

DDI Atlas Construction

The ultimate step of registration of MCM images is the production of an average atlas of the white matter microstructure. We computed an atlas from the 20 DDI images following Guimond et al. atlas construction method [START_REF] Guimond | Average brain models: A convergence study[END_REF]. This atlas construction was performed using non linear DTI registration as proposed by Suarez et al. [START_REF] Suarez | Automated delineation of white matter fiber tracts with a multiple region-of-interest approach[END_REF]. Then, the obtained transformations were applied to the DDI models. We interpolated the DDI models using our clustering approach with the covariance analytic averaging. In addition, when applying a transformation to oriented models, it is necessary to apply the local linear part of the transformation to the interpolated models. We used a technique similar to finite-strain reorientation for tensors [START_REF] Ruiz-Alzola | Nonrigid registration of 3D tensor medical data[END_REF] by applying the local rotation to the µ i directions of each compartment of the interpolated DDI. We present the visual result of the atlas and a zoomed area in Fig. 2. This atlas provides a clear distinction of crossing fibers and will be of great interest in future studies for example of white matter microstructure destruction in diseases.

Conclusion

We have addressed the problem of interpolation and averaging of MCM images. As MCMs become increasingly popular and used, the issue of interpolation (e.g. for a registration purpose) or averaging (e.g. for atlas creation) becomes acute in the absence of relevant dedicated solutions yet. We have proposed to perform interpolation as a MCM simplification problem, relying on spectral clustering and compartment averaging methods handling both free water and compartment parameters. For this latter part, we have proposed and compared four different alternatives, these methods being evaluated with synthetic and real data. According to these different experimental conditions, the covariance analytic solution exhibits significantly better performance than the others. This can be explained by its capability to better handle the diffusion dispersion parameter (κ) around each compartment principal orientation. Although this study has been validated on one MCM model (DDI), the method proposed is generic and may be extended to all currently available MCMs.

3 . 4 .

 34 The interpolation of κ is done recursively by projection in McGraw et al. Letting κ = κ 1 , repeat until convergence (i.e until l κ < ε):

Fig. 1 .

 1 Fig. 1. First four images (a-d) illustrate DDI averaging using the four methods superimposed on their local error maps. Image (d) is the reference.

Fig. 2 .

 2 Fig. 2. Example of a DDI atlas superimposed on the average B0 image.