Karine Bertin
email: karine.bertin@uv.cl

Erwan Le Pennec
email: lepennec@math.jussieu.fr

Vincent Rivoirard
email: vincent.rivoirard@math.u-psud.fr

Adaptive Dantzig density estimation

Keywords: Calibration, Concentration inequalities, Dantzig estimate, Density estimation, Dictionary, Lasso estimate, Oracle inequalities, Sparsity AMS subject classification : 62G07, 62G05, 62G20

de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Various estimation procedures based on l 1 penalization (exemplified by the Dantzig procedure in [START_REF] Candès | The Dantzig selector: statistical estimation when p is much larger than n[END_REF] and the LASSO procedure in [START_REF] Tibshirani | Regression shrinkage and selection via the Lasso[END_REF]) have extensively been studied recently. These procedures are computationally efficient as shown in [START_REF] Efron | Least angle regression[END_REF][START_REF] Osborne | a) On the Lasso and its dual[END_REF][START_REF] Osborne | A new approach to variable selection in least squares problems[END_REF], and thus are adapted to high-dimensional data. They have been widely used in regression models, but only the Lasso estimator has been studied in the density model (see [START_REF] Bunea | Sparse density estimation with l 1 penalties[END_REF][START_REF] Bunea | Spades and Mixture Models[END_REF][START_REF] Van De Geer | High dimensional generalized linear models and the Lasso[END_REF]). Although we will mostly consider the Dantzig estimator in the density model for which no result exists so far, we recall some of the classical results obtained in different settings by procedures based on l 1 penalization.

The Dantzig selector has been introduced by Candès and Tao [START_REF] Candès | The Dantzig selector: statistical estimation when p is much larger than n[END_REF] in the linear regression model. More precisely, given

Y = Aλ 0 + ε,
where Y ∈ R n , A is a n by M matrix, ε ∈ R n is the noise vector and λ 0 ∈ R M is the unknown regression parameter to estimate, the Dantzig estimator is defined by λD = arg min

λ∈R M ||λ|| ℓ1 subject to ||A T (Aλ -Y )|| ℓ∞ ≤ η,
where || • || ℓ∞ is the sup-norm in R M , || • || ℓ1 is the ℓ 1 norm in R M , and η is a regularization parameter. A natural companion of this estimator is the Lasso procedure or more precisely its relaxed form λL = arg min

λ∈R M 1 2 ||Aλ -Y || 2 ℓ2 + η||λ|| ℓ1 ,
where η plays exactly the exact same role as for the Dantzig estimator. This ℓ 1 penalized method is also called basis pursuit in signal processing (see [START_REF] Chen | Atomic decomposition by basis pursuit[END_REF][START_REF] Donoho | Stable recovery of sparse overcomplete representations in the presence of noise[END_REF]). Candès and Tao [START_REF] Candès | The Dantzig selector: statistical estimation when p is much larger than n[END_REF] have obtained a bound for the ℓ 2 risk of the estimator λD , with large probability, under a global condition on the matrix A (the Restricted Isometry Property) and a sparsity assumption on λ 0 , even for M ≥ n. Bickel et al. [START_REF] Bickel | Simultaneous analysis of Lasso and Dantzig selector[END_REF] have obtained oracle inequalities and bounds of the ℓ p loss for both estimators under weaker assumptions. Actually, Bickel et al. [START_REF] Bickel | Simultaneous analysis of Lasso and Dantzig selector[END_REF] deal with the non parametric regression framework in which one observes

Y i = f (x i ) + e i , i = 1, . . . , n
where f is an unknown function while (x i ) i=1,...,n are known design points and (e i ) i=1,...,n is a noise vector. There is no intrinsic matrix A in this problem but for any dictionary of functions Υ = (ϕ m ) m=1,...,M one can search f as a weighted sum f λ of elements of Υ

f λ = M m=1
λ m ϕ m and introduce the matrix A = (ϕ m (x i )) i,m , which summarizes the information on the dictionary and on the design. Notice that if there exists λ 0 such that f = f λ0 then the model can be rewritten exactly as the classical linear model. However, if it is not the case and if a model bias exists, the Dantzig and Lasso procedures can be after all applied under similar assumptions on A. Oracle inequalities are obtained for which approximation theory plays an important role in [START_REF] Bickel | Simultaneous analysis of Lasso and Dantzig selector[END_REF][START_REF] Bunea | Aggregation for Gaussian regression[END_REF][START_REF] Bunea | Sparsity Oracle Inequalities for the LASSO[END_REF][START_REF] Van De Geer | High dimensional generalized linear models and the Lasso[END_REF].

Let us also mention that in various settings, under various assumptions on the matrix A (or more precisely on the associated Gram matrix G = A T A), properties of these estimators have been established for subset selection (see [START_REF] Bunea | Consistent selection via the Lasso for high dimensional approximating regression models[END_REF][START_REF] Lounici | Sup-norm convergence rate and sign concentration property of Lasso and Dantzig estimators[END_REF][START_REF] Meinshausen | High dimensional graphs and variable selection with the Lasso[END_REF][START_REF] Meinhausen | Lasso-type recovery of sparse representations for highdimensional data[END_REF][START_REF] Yu | On model selection consistency of Lasso estimators[END_REF][START_REF] Zhang | The sparsity and bias of the Lasso selection in highdimensional linear regression[END_REF]) and for prediction (see [START_REF] Bickel | Simultaneous analysis of Lasso and Dantzig selector[END_REF][START_REF] Knight | Asymptotics for lasso-type estimators[END_REF][START_REF] Lounici | Sup-norm convergence rate and sign concentration property of Lasso and Dantzig estimators[END_REF][START_REF] Meinhausen | Lasso-type recovery of sparse representations for highdimensional data[END_REF][START_REF] Zou | The adaptive Lasso and its oracle properties[END_REF]).

Our goals and results

We consider in this paper the density estimation framework already studied for the Lasso estimate by Bunea et al [START_REF] Bunea | Sparse density estimation with l 1 penalties[END_REF][START_REF] Bunea | Spades and Mixture Models[END_REF] and van de Geer [START_REF] Van De Geer | High dimensional generalized linear models and the Lasso[END_REF]. Namely, our goal is to estimate f 0 , an unknown density function, by using the observations of an n-sample of variables X 1 , . . . , X n of density f 0 . As in the non parametric regression setting, we introduce a dictionary of functions Υ = (ϕ m ) m=1,...,M , and search again estimates of f 0 as linear combinations f λ of the dictionary functions. We rely on the Gram matrix associated with Υ and on the empirical scalar products of f 0 with ϕ m βm =

1

n n i=1 ϕ m (X i ).
The Dantzig estimate f D is then obtained by minimizing ||λ|| ℓ1 over the set of parameters λ satisfying the adaptive Dantzig constraint:

∀ m ∈ {1, . . . .M }, |(Gλ) m -βm | ≤ η γ,m
where for m ∈ {1, . . . , M }, (Gλ) m is the scalar product of f λ with ϕ m ,

η γ,m = 2σ 2 m γ log M n + 2||ϕ m || ∞ γ log M 3n , σ2
m is a sharp estimate of the variance of βm and γ is a constant to be chosen. Section 2 gives precise definitions and heuristics for using this constraint. We just mention here that η γ,m comes from sharp concentration inequalities to give tight constraints. Our idea is that if f 0 can be decomposed on Υ as

f 0 = M m=1 λ 0,m ϕ m ,
then we force the set of feasible parameters λ to contain λ 0 with large probability and to be as small as possible. Significant improvements in practice are expected.

Our goals in this paper are mainly twofold. First, we aim at establishing sharp oracle inequalities under very mild assumptions on the dictionary. Our starting point is that most of the papers in the literature assume that the functions of the dictionary are bounded by a constant independent of M and n, which constitutes a strong limitation, in particular for dictionaries based on histograms or wavelets (see for instance [START_REF] Bunea | Aggregation and sparsity via ℓ 1 penalized least squares[END_REF], [START_REF] Bunea | Sparse density estimation with l 1 penalties[END_REF], [START_REF] Bunea | Aggregation for Gaussian regression[END_REF], [START_REF] Bunea | Sparsity Oracle Inequalities for the LASSO[END_REF], [START_REF] Bunea | Consistent selection via the Lasso for high dimensional approximating regression models[END_REF] or [START_REF] Van De Geer | High dimensional generalized linear models and the Lasso[END_REF]). Such assumptions on the functions of Υ will not be considered in our paper. Likewise, our methodology does not rely on the knowledge of ||f 0 || ∞ that can even be infinite (as noticed by Birgé [4] for the study of the integrated L 2 -risk, most of the papers in the literature typically assume that the sup-norm of the unknown density is finite with a known or estimated bound for this quantity). Finally, let us mention that, in contrast with what Bunea et al [START_REF] Bunea | Spades and Mixture Models[END_REF] did, we obtain oracle inequalities with leading constant 1, and furthermore these are established under much weaker assumptions on the dictionary than in [START_REF] Bunea | Spades and Mixture Models[END_REF].

The second goal of this paper deals with the problem of calibrating the so-called Dantzig constant γ: how should this constant be chosen to obtain good results in both theory and practice? Most of the time, for Lasso-type estimators, the regularization parameter is of the form a log M n with a a positive constant (see [START_REF] Bickel | Simultaneous analysis of Lasso and Dantzig selector[END_REF], [START_REF] Bunea | Sparse density estimation with l 1 penalties[END_REF], [START_REF] Bunea | Aggregation and sparsity via ℓ 1 penalized least squares[END_REF], [START_REF] Bunea | Sparsity Oracle Inequalities for the LASSO[END_REF], [START_REF] Candès | Near-ideal model selection by l1 minimization[END_REF], [START_REF] Lounici | Sup-norm convergence rate and sign concentration property of Lasso and Dantzig estimators[END_REF] or [START_REF] Meinhausen | Lasso-type recovery of sparse representations for highdimensional data[END_REF] for instance). These results are obtained with large probability that depends on the tuning coefficient a. In practice, it is not simple to calibrate the constant a. Unfortunately, most of the time, the theoretical choice of the regularization parameter is not suitable for practical issues. This fact is true for Lasso-type estimates but also for many algorithms for which the regularization parameter provided by the theory is often too conservative for practical purposes (see [START_REF] Juditsky | On minimax density estimation on R[END_REF] who clearly explains and illustrates this point for their thresholding procedure). So, one of the main goals of this paper is to fill the gap between the optimal parameter choice provided by theoretical results on the one hand and by a simulation study on the other hand. Only a few papers are devoted to this problem. In the model selection setting, the issue of calibration has been addressed by Birgé and Massart [START_REF] Birgé | Minimal penalties for Gaussian model selection[END_REF] who considered ℓ 0 -penalized estimators in a Gaussian homoscedastic regression framework and showed that there exists a minimal penalty in the sense that taking smaller penalties leads to inconsistent estimation procedures. Arlot and Massart [START_REF] Arlot | Data-driven calibration of penalties for least-squares regression[END_REF] generalized these results for non-Gaussian or heteroscedastic data and Reynaud-Bouret and Rivoirard [START_REF] Reynaud-Bouret | Calibration of thresholding rules for Poisson intensity estimation[END_REF] addressed this question for thresholding rules in the Poisson intensity framework. Now, let us describe our results. By using the previous data-driven Dantzig constraint, oracle inequalities are derived under local conditions on the dictionary that are valid under classical assumptions on the structure of the dictionary. We extensively discuss these assumptions and we show their own interest in the context of the paper. Each term of these oracle inequalities is easily interpretable. Classical results are recovered when we further assume:

||ϕ m || 2 ∞ ≤ c 1 n log M ||f 0 || ∞ ,
where c 1 is a constant. This assumption is very mild and, unlike in classical works, allows to consider dictionaries based on wavelets. Then, relying on our Dantzig estimate, we build an adaptive Lasso procedure whose oracle performances are similar. This illustrates the closeness between Lasso and Dantzig-type estimates.

Our results are proved for γ > 1. For the theoretical calibration issue, we study the performance of our procedure when γ < 1. We show that in a simple framework, estimation of the straightforward signal f 0 = 1 [0,1] cannot be performed at a convenient rate of convergence when γ < 1. This result proves that the assumption γ > 1 is thus not too conservative.

Finally, a simulation study illustrates how dictionary-based methods outperform classical ones. More precisely, we show that our Dantzig and Lasso procedures with γ > 1, but close to 1, outperform classical ones, such as simple histogram procedures, wavelet thresholding or Dantzig procedures based on the knowledge of ||f 0 || ∞ and less tight Dantzig constraints.

Outlines

Section 2 introduces the density estimator of f 0 whose theoretical performances are studied in Section 3. Section 4 studies the Lasso estimate proposed in this paper. The calibration issue is studied in Section 5.1 and numerical experiments are performed in Section 5.2. Finally, Section 6 is devoted to the proofs of our results.

2 The Dantzig estimator of the density f 0 As said in Introduction, our goal is to build an estimate of f 0 as a linear combination of functions of Υ = (ϕ m ) m=1,...,M , where we assume without any loss of generality that, for any m, ϕ m 2 = 1:

f λ = M m=1 λ m ϕ m .
For this purpose, we naturally rely on natural estimates of the L 2 -scalar products between f 0 and the ϕ m 's. So, for m ∈ {1, . . . , M }, we set

β 0,m = ϕ m (x)f 0 (x)dx, (1)
and we consider its empirical counterpart

βm = 1 n n i=1 ϕ m (X i ) (2)
that is an unbiased estimate of β 0,m . The variance of this estimate is Var( βm ) =

σ 2 0,m
n where

σ 2 0,m = ϕ 2 m (x)f 0 (x)dx -β 2 0,m . (3)
Note also that for any λ and any m, the L 2 -scalar product between f λ and ϕ m can be easily computed:

ϕ m (x)f λ (x)dx = M m ′ =1 λ m ′ ϕ m ′ (x)ϕ m (x)dx = (Gλ) m
where G is the Gram matrix associated to the dictionary Υ defined for any 1 ≤ m, m ′ ≤ M by

G m,m ′ = ϕ m (x)ϕ m ′ (x)dx.
Any reasonable choice of λ should ensure that the coefficients (Gλ) m are close to βm for all m. Therefore, using Candès and Tao's approach, we define the Dantzig constraint:

∀ m ∈ {1, . . . .M }, |(Gλ) m -βm | ≤ η γ,m (4)
and the Dantzig estimate f D by f D = f λD,γ with λD,γ = argmin λ∈R M ||λ|| ℓ1 such that λ satisfies the Dantzig constraint (4),

where for γ > 0 and m ∈ {1, . . . , M },

η γ,m = 2σ 2 m γ log M n + 2||ϕ m || ∞ γ log M 3n , (5)
with

σ2 m = σ2 m + 2||ϕ m || ∞ 2σ 2 m γ log M n + 8||ϕ m || 2 ∞ γ log M n (6)
and

σ2 m = 1 n(n -1) n i=2 i-1 j=1 (ϕ m (X i ) -ϕ m (X j )) 2 . ( 7
)
Note that η γ,m depends on the data, so the constraint (4) will be referred as the adaptive Dantzig constraint in the sequel. We now justify the introduction of the density estimate f D . The definition of η λ,γ is based on the following heuristics. Given m, when there exists a constant c 0 > 0 such that f 0 (x) ≥ c 0 for x in the support of ϕ m satisfying ϕ m 2 ∞ = o n (n(log M ) -1 ), then, with large probability, the deterministic term of ( 5) is negligible with respect to the random one. In this case, the random term is the main one and we asymptotically derive

η γ,m ≈ 2γ logM σ2 m n . (8)
Having in mind that σ2 m /n is a convenient estimate for Var( βm ) (see the proof of Theorem 1), the shape of the right hand term of the formula (8) looks like the bound proposed by Candès and Tao [START_REF] Candès | The Dantzig selector: statistical estimation when p is much larger than n[END_REF] to define the Dantzig constraint in the linear model. Actually, the deterministic term of (5) allows to get sharp concentration inequalities. As often done in the literature, instead of estimating Var( βm ), we could use the inequality

Var( βm ) = σ 2 0,m n ≤ ||f 0 || ∞ n
and we could replace σ2 m with ||f 0 || ∞ in the definition of the η γ,m . But this requires a strong assumption: f 0 is bounded and ||f 0 || ∞ is known. In our paper, Var( βm ) is estimated, which allows not to impose these conditions. More precisely, we slightly overestimate σ 2 0,m to control large deviation terms and this is the reason why we introduce σ2 m instead of using σ2 m , an unbiased estimate of σ 2 0,m . Finally, γ is a constant that has to to be suitably calibrated and plays a capital role in practice.

The following result justifies previous heuristics by showing that, if γ > 1, with high probability, the quantity | βm -β 0,m | is smaller than η γ,m for all m. The parameter η γ,m with γ close to 1 can be viewed as the "smallest" quantity that ensures this property.

Theorem 1. Let us assume that M satisfies n ≤ M ≤ exp(n δ ) ( 9
)
for δ < 1. Let γ > 1. Then, for any ε > 0, there exists a constant C 1 (ε, δ, γ) depending on ε, δ and γ such that

P ∀m ∈ {1, . . . , M }, |β 0,m -βm | ≥ η γ,m ≤ C 1 (ε, δ, γ)M 1-γ 1+ε .
In addition, there exists a constant C 2 (δ, γ) depending on δ and γ such that

P ∀m ∈ {1, . . . , M }, η (-) γ,m ≤ η γ,m ≤ η (+) γ,m ≤ C 2 (δ, γ)M 1-γ
where, for m ∈ {1, . . . , M },

η (-) γ,m = σ 0,m 8γ log M 7n + 2||ϕ m || ∞ γ log M 3n and η (+) γ,m = σ 0,m 16γ log M n + 10||ϕ m || ∞ γ log M n .
This result is proved in Section 6.1. The first part is a sharp concentration inequality proved by using Bernstein type controls. The second part of the theorem proves that, up to constants depending on γ, η γ,m is of order σ 0,m

log M n + ||ϕ m || ∞ log M n
with high probability. Note that the assumption γ > 1 is essential to obtain probabilities going to 0.

Finally, let λ 0 = (λ 0,m ) m=1,...,M ∈ R M such that

P Υ f 0 = M m=1 λ 0,m ϕ m
where P Υ is the projection on the space spanned by Υ. We have

(Gλ 0 ) m = (P Υ f 0 )ϕ m = f 0 ϕ m = β 0,m .
So, Theorem 1 proves that λ 0 satisfies the adaptive Dantzig constraint (4) with probability larger than 1-C 1 (ε, δ, γ)M 1-γ 1+ε for any ε > 0. Actually, we force the set of parameters λ satisfying the adaptive Dantzig constraint to contain λ 0 with large probability and to be as small as possible. Therefore, f D = f λD,γ is a good candidate among sparse estimates linearly decomposed on Υ for estimating f 0 .

We mention that Assumption (9) can be relaxed and we can take M < n provided the definition of η γ,m is modified.

Results for the Dantzig estimators

In the sequel, we will denote λD = λD,γ to simplify the notations, but the Dantzig estimator f D still depends on γ. Moreover, we assume that ( 9) is true and we denote the vector η γ = (η γ,m ) m=1,...,M considered with the Dantzig constant γ > 1.

The main result under local assumptions

Let us state the main result of this paper. For any J ⊂ {1, . . . , M }, we set J C = {1, . . . , M } J and define λ J the vector which has the same coordinates as λ on J and zero coordinates on J C . We introduce a local assumption indexed by a subset J 0 .

• Local Assumption Given J 0 ⊂ {1, . . . , M }, for some constants κ J0 > 0 and µ J0 > 0 depending on J 0 , we have for any λ,

||f λ || 2 ≥ κ J0 ||λ J0 || ℓ2 -µ J0 ||λ J C 0 || ℓ1 -||λ J0 || ℓ1 + . (LA(J 0 , κ J0 , µ J0 ))
We obtain the following oracle type inequality without any assumption on f 0 .

Theorem 2. Let J 0 ⊂ {1, . . . , M } be fixed. We suppose that (LA(J 0 , κ J0 , µ J0 )) holds. Then, with probability at least

1 -C 1 (ε, δ, γ)M 1-γ 1+ε , we have for any β > 0, || f D -f 0 || 2 2 ≤ inf λ∈R M    ||f λ -f 0 || 2 2 + β Λ(λ, J c 0 ) 2 |J 0 | 1 + 2µ J0 |J 0 | κ J0 2 + 16|J 0 | 1 β + 1 κ 2 J0 ||η γ || 2 ℓ∞    , (10) with
Λ(λ, J c 0 ) = ||λ J C 0 || ℓ1 + || λD || ℓ1 -||λ|| ℓ1 + 2 .
Let us comment each term of the right hand side of [START_REF] Bunea | Spades and Mixture Models[END_REF]. The first term is an approximation term which measures the closeness between f 0 and f λ . This term can vanish if f 0 can be decomposed on the dictionary. The second term is a price to pay when either λ is not supported by the subset J 0 considered or it does not satisfy the condition || λD || ℓ1 ≤ ||λ|| ℓ1 which holds as soon as λ satisfy the adaptive Dantzig constraint. Finally, the last term, which does not depend on λ, can be viewed as a variance term corresponding to the estimation on the subset J 0 . Indeed, remember that η γ,m relies on an estimate of the variance of βm . Furthermore, we have with high probability:

||η γ || 2 ℓ∞ ≤ 2 16σ 2 0,m γ log M n + 10||ϕ m || ∞ γ log M n 2 . So, if f 0 is bounded then, σ 2 0,m ≤ ||f 0 || ∞ and if there exists a constant c 1 such that for any m, ||ϕ m || 2 ∞ ≤ c 1 n log M ||f 0 || ∞ , (11)
(which is true for instance for a bounded dictionary), then

||η γ || 2 ℓ∞ ≤ C||f 0 || ∞ log M n ,
(where C is a constant depending on γ and c 1 ) and tends to 0 when n goes to ∞. We obtain thus the following result.

Corollary 1. Let J 0 ⊂ {1, . . . , M } be fixed. We suppose that (LA(J 0 , κ J0 , µ J0 )) holds. If [START_REF] Bunea | Consistent selection via the Lasso for high dimensional approximating regression models[END_REF] is satisfied then, with probability at least 1 -C 1 (ε, δ, γ)M 1-γ 1+ε , we have for any β > 0, for any λ that satisfies the adaptive Dantzig constraint

|| f D -f 0 || 2 2 ≤ ||f λ -f 0 || 2 2 + βc 2 (1 + κ -2 J0 µ 2 J0 |J 0 |) ||λ J C 0 || 2 ℓ1 |J 0 | + c 3 (β -1 + κ -2 J0 )|J 0 |||f 0 || ∞ log M n , (12)
where c 2 is an absolute constant and c 3 depends on c 1 and γ.

The parameter β calibrates the weights given for the bias and variance terms. Remark that if f 0 = f λ0 and if (LA(J 0 , κ J0 , µ J0 )) holds with J 0 = J λ0 , under [START_REF] Bunea | Consistent selection via the Lasso for high dimensional approximating regression models[END_REF], the proof of Theorem 2 yields the more classical inequality

|| f D -f 0 || 2 2 ≤ C ′ |J 0 |||f 0 || ∞ log M n ,
where

C ′ = c 3 κ -2 J0 , with at least the same probability 1 -C 1 (ε, δ, γ)M 1-γ 1+ε . Assumption (LA(J 0 , κ J0 , µ J0
)) is local, in the sense that the constants κ J0 and µ J0 (or their mere existence) may highly depend on the subset J 0 . For a given λ, the best choice for J 0 in Inequalities ( 10) and ( 12) depends thus on the interaction between these constants and the value of λ itself. Note that the assumptions of Theorem 2 are reasonable as the next section gives conditions for which Assumption (LA(J 0 , κ J0 , µ J0 )) holds simultaneously with the same constant κ and µ for all subsets J 0 of the same size.

Results under global assumptions

As usual, when M > n, properties of the Dantzig estimate can be derived from assumptions on the structure of the dictionary Υ. For l ∈ N, we denote

φ min (l) = min |J|≤l min λ∈R M λJ =0 ||f λJ || 2 2 ||λ J || 2 ℓ2 and φ max (l) = max |J|≤l max λ∈R M λJ =0 ||f λJ || 2 2 ||λ J || 2 ℓ2 .
These quantities correspond to the "restricted" eigenvalues of the Gram matrix G. Assuming that φ min (l) and φ max (l) are close to 1 means that every set of columns of G with cardinality less than l behaves like an orthonormal system. We also consider the restricted correlations

θ l,l ′ = max |J|≤l |J ′ |≤l ′ J∩J ′ =∅ max λ,λ ′ ∈R M λJ =0,λ ′ J ′ =0 f λJ , f λ ′ J ′ ||λ J || ℓ2 ||λ ′ J ′ || ℓ2
.

Small values of θ l,l ′ mean that two disjoint sets of columns of G with cardinality less than l and l ′ span nearly orthogonal spaces. We will use one of the following assumptions considered in [START_REF] Bickel | Simultaneous analysis of Lasso and Dantzig selector[END_REF].

• Assumption 1 For some integer 1 ≤ s ≤ M/2, we have

φ min (2s) > θ s,2s . (A1(s))
Oracle inequalities of the Dantzig selector were established under this assumption in the parametric linear model by Candès and Tao in [START_REF] Candès | The Dantzig selector: statistical estimation when p is much larger than n[END_REF]. It was also considered by Bunea, Ritov and Tsybakov [START_REF] Bickel | Simultaneous analysis of Lasso and Dantzig selector[END_REF] for non-parametric regression and for the Lasso estimate. The next assumption, proposed in [START_REF] Bickel | Simultaneous analysis of Lasso and Dantzig selector[END_REF], constitutes an alternative to Assumption 1.

• Assumption 2 For some integers s and l such that

1 ≤ s ≤ M 2 , l ≥ s and s + l ≤ M, (13)
we have lφ min (s + l) > sφ max (l). (A2(s,l))

If Assumption 2 is true for s and l such that l ≫ s, then Assumption 2 means that φ min (l) cannot decrease at a rate faster than l -1 and this condition is related to the "incoherent designs" condition stated in [START_REF] Meinhausen | Lasso-type recovery of sparse representations for highdimensional data[END_REF].

In the sequel, we set, under Assumption 1,

κ 1 (s) = φ min (2s) 1 - θ s,2s φ min (2s) > 0, µ 1 (s) = θ s,2s sφ min (2s)
and under Assumption 2,

κ 2 (s, l) = φ min (s + l) 1 - sφ max (l) lφ min (s + l) > 0, µ 2 (s, l) = φ max (l) l .
Now, to apply Theorem 2, we need to check (LA(J 0 , κ J0 , µ J0 )) for some some subset J 0 of {1, . . . , M }. Either Assumption 1 or Assumption 2 implies this assumption. Indeed, we have the following result.

Proposition 1. Let s and l two integers satisfying [START_REF] Candès | The Dantzig selector: statistical estimation when p is much larger than n[END_REF]. We suppose that (A1(s

)) or (A2(s,l)) is true. Let J 0 ⊂ {1, . . . , M } of size |J 0 | = s and λ ∈ R M , then we have ||f λ || 2 ≥ κ||λ J0 || ℓ2 -µ ||λ J C 0 || ℓ1 -||λ J0 || ℓ1
+ with κ = κ 1 (s) and µ = µ 1 (s) under (A1(s)) (respectively κ = κ 2 (s, l) and µ = µ 2 (s, l) under (A2(s,l)). If (A1(s)) and (A2(s,l)) are both satisfied, κ = max(κ 1 (s), κ 2 (s, l)) and µ = min(µ 1 (s), µ 2 (s, l)).

Proposition 1 proves that Theorem 2 can be applied under Assumptions 1 or 2. In addition, the constants κ J0 and µ J0 only depend on |J 0 |. From Theorem 2, we deduce the following result. Theorem 3. Let s and l two integers satisfying [START_REF] Candès | The Dantzig selector: statistical estimation when p is much larger than n[END_REF]. We suppose that (A1(s)) or (A2(s,l)) is true. Then, with probability at least 1 -C 1 (ε, δ, γ)M 1-γ 1+ε , we have for any β > 0,

|| f D -f 0 || 2 2 ≤ inf λ∈R M inf J0⊂{1,...,M} |J0|=s ||f λ -f 0 || 2 2 + β Λ(λ, J c 0 ) 2 s 1 + 2µ √ s κ 2 + 16s 1 β + 1 κ 2 ||η γ || 2 ℓ∞ where Λ(λ, J c 0 ) = ||λ J C 0 || ℓ1 + || λD || ℓ1 -||λ|| ℓ1 + 2 .
Remark that the best subset J 0 of cardinal s in Theorem 3 can be easily chosen for a given λ: it is given by the set of the s largest coordinates of λ. This was not necessarily the case in Theorem 2 for which a different subset may give a better local condition and then may provide a smaller bound. If we further assume the mild assumption [START_REF] Bunea | Consistent selection via the Lasso for high dimensional approximating regression models[END_REF] on the sup norm of the dictionary introduced in the previous section, we deduce the following result.

Corollary 2. Let s and l two integers satisfying [START_REF] Candès | The Dantzig selector: statistical estimation when p is much larger than n[END_REF]. We suppose that (A1(s)) or (A2(s,l)) is true. If [START_REF] Bunea | Consistent selection via the Lasso for high dimensional approximating regression models[END_REF] is satisfied, with probability at least 1 -C 1 (ε, δ, γ)M 1-γ 1+ε , we have for any β > 0, any λ that satisfies the adaptive Dantzig constraint and for the best subset J 0 of cardinal s (that corresponds to the s largest coordinates of λ in absolute value),

|| f D -f 0 || 2 2 ≤ ||f λ -f 0 || 2 2 + βc 2 (1 + κ -2 µ 2 s) ||λ J C 0 || 2 ℓ1 s + c 3 (β -1 + κ -2 )s||f 0 || ∞ log M n , ( 14
)
where c 2 is an absolute constant and c 3 depends on c 1 and γ.

Note that, when λ is s-sparse so that λ J C 0 = 0, the oracle inequality ( 14) corresponds to the classical oracle inequality obtained in parametric frameworks (see [START_REF] Candès | Near-ideal model selection by l1 minimization[END_REF] or [START_REF] Candès | The Dantzig selector: statistical estimation when p is much larger than n[END_REF] for instance) or in non-parametric settings. See, for instance [START_REF] Bunea | Aggregation and sparsity via ℓ 1 penalized least squares[END_REF], [START_REF] Bunea | Sparse density estimation with l 1 penalties[END_REF], [START_REF] Bunea | Aggregation for Gaussian regression[END_REF], [START_REF] Bunea | Sparsity Oracle Inequalities for the LASSO[END_REF], [START_REF] Bunea | Consistent selection via the Lasso for high dimensional approximating regression models[END_REF] or [START_REF] Van De Geer | High dimensional generalized linear models and the Lasso[END_REF] but in these works, the functions of the dictionary are assumed to be bounded by a constant independent of M and n. So, the adaptive Dantzig estimate requires weaker conditions since under [START_REF] Bunea | Consistent selection via the Lasso for high dimensional approximating regression models[END_REF], ||ϕ m || ∞ can go to ∞ when n grows. This point is capital for practical purposes, in particular when wavelet bases are considered.

Connections between the Dantzig and Lasso estimates

We show in this section the strong connections between Lasso and Dantzig estimates, which has already been illustrated in [START_REF] Bickel | Simultaneous analysis of Lasso and Dantzig selector[END_REF] for non-parametric regression models. By choosing convenient random weights depending on η γ for ℓ 1 -minimization, the Lasso estimate satisfies the adaptive Dantzig constraint. More precisely, we consider the Lasso estimator given by the solution of the following minimization problem

λL,γ = argmin λ∈R M R(λ) + 2 M m=1 η γ,m |λ m | , (15)
where

R(λ) = ||f λ || 2 2 - 2 n n i=1 f λ (X i ).
Note that R(•) is the quantity minimized in unbiased estimation of the risk. For simplifications, we write λL = λL,γ . We denote f L = f λL . As said in Introduction, classical Lasso estimates are defined as the minimizer of expressions of the form

R(λ) + 2η M m=1 |λ m | ,
where η is proportional to log M n . So, λL appears as a data-driven version of classical Lasso estimates.

The first order condition for the minimization of the expression given in (15) corresponds exactly to the adaptive Dantzig constraint and thus Theorem 3 always applies to λL . Working along the lines of the proof of Theorem 3 (Replace f λ by f D and f D by f L in ( 26) and ( 27)), one can prove a slightly stronger result.

|| f D -f 0 || 2 2 -|| f L -f 0 || 2 2 ≤ β || λL J C 0 || 2 ℓ1 s 1 + 2µ √ s κ 2 + 16s 1 β + 1 κ 2 ||η γ || 2 ℓ∞ .
To extend this theoretical result, numerical performances of the Dantzig and Lasso estimates will be compared in Section 5.2.

Calibration and numerical experiments 5.1 The calibration issue

In this section, we consider the problem of calibrating previous estimates. In particular, we prove that the sufficient condition γ > 1 is "almost" a necessary condition since we derive a special and very simple framework in which Lasso and Dantzig estimates cannot achieve the optimal rate if γ < 1 ("almost" means that the case γ = 1 remains an open question). Let us describe this simple framework. The dictionary Υ considered in this section is the orthonormal Haar system:

Υ = φ jk : -1 ≤ j ≤ j 0 , 0 ≤ k < 2 j , with φ -10 = 1 [0,1] , 2 j0+1 = n, and for 0 ≤ j ≤ j 0 , 0 ≤ k ≤ 2 j -1, φ jk = 2 j/2 1 [k/2 j ,(k+0.5)/2 j ] -1 [(k+0.5)/2 j ,(k+1)/2 j ] .
In this case, M = n. In this setting, since functions of Υ are orthonormal, the Gram matrix G is the identity. Thus, the Lasso and Dantzig estimates both correspond to the soft thresholding rule:

f D = f L = M m=1 sign( βm ) | βm | -η γ,m 1 {| βm|>ηγ,m} ϕ m .
Now, our goal is to estimate f 0 = φ -10 = 1 [0,1] by using f D depending on γ and to show the influence of this constant. Unlike previous results stated in probability, we consider the expectation of the L 2 -risk: Theorem 5. On the one hand, if γ > 1, there exists a constant C such that

E|| f D -f 0 || 2 2 ≤ C log n n , (16)
On the other hand, if γ < 1, there exists a constant c and δ < 1 such that

E|| f D -f 0 || 2 2 ≥ c n δ . (17)
This result shows that choosing γ < 1 is a bad choice in our setting. Indeed, in this case, the Lasso and Dantzig estimates cannot estimate a very simple signal (f 0 = 1 [0,1] ) at a convenient rate of convergence.

A small simulation study is carried out to strengthen this theoretical asymptotic result. Performing our estimation procedure 100 times, we compute the average risk R n (γ) for several values of the Dantzig constant γ and several values of n. This computation is summarized in Figure 1 which displays the logarithm of R n (γ) for n = 2 J with, from top to bottom, J = 4, 5, 6, . . . , 13 on a grid of γ's around 1. To discuss our results, we denote by γ min (n) the best γ: γ min (n) = argmin γ>0 R n (γ). We note that 1/2 ≤ γ min (n) ≤ 1 for all values of n, with γ min (n) getting closer to 1 as n increases. Taking γ too small strongly deteriorates the performance while a value close to 1 ensures a risk withing a factor 2 of the optimal risk. The assumption γ > 1 giving a theoretical control on the quadratic error is thus not too conservative. Following these results, we set γ = 1.01 in our numerical experiments in the next subsection.

Numerical experiments

In this section, we present our numerical experiments with the Dantzig density estimator and their results. We test our estimator with a collection of 6 dictionaries, 4 densities described below and for 2 sample sizes. We compare our procedure with the adaptive Lasso introduced in Section 4 and with a non adaptive Dantzig estimator. We also consider a two-step estimation procedure, proposed by Candès and Tao [START_REF] Candès | The Dantzig selector: statistical estimation when p is much larger than n[END_REF], which improves the numerical results.

The numerical scheme for a given dictionary Υ = (ϕ m ) m=1,...,M and a sample (X i ) i=1,...,n is the following. λD,γ m φ m .

η γ,m = 2σ 2 m γ log M n + 2||ϕ m || ∞ γ log M 3n , with σ2 m = σ2 m + 2||ϕ m || ∞ 2σ 2 m γ log M n + 8||ϕ m || 2 ∞ γ log M n and γ = 1.01.
Note that we have implicitly assumed that the Gram matrix G used in the definition of the Dantzig constraint has been precomputed. For the Lasso estimator, the Dantzig minimization of step 4 is replaced by the Lasso minimization [START_REF] Donoho | Stable recovery of sparse overcomplete representations in the presence of noise[END_REF] λL,γ = argmin λ∈R M R(λ) + 2

M m=1 η γ,m |λ m | ,
which is solved using the LARS algorithm. The non adaptive Dantzig estimate is obtained by replacing σ2 m in step 3 by f 0 ∞ . The two-step procedure of Candès and Tao adds a least-square step between step 4 and step 5. More precisely, let ĴD,γ be the support of the estimate λD,γ . This defines a subset of the dictionary on which the density is regressed

λD+LS,γ ĴD,γ = G -1 ĴD,γ ( βm ) ĴD,γ
where G ĴD,γ is the submatrix of G corresponding to the subset chosen. The values of λD+LS,γ outside ĴD,γ are set to 0 and f D+LS,γ is set accordingly.

We describe now the dictionaries we consider. We focus numerically on densities defined on the interval [0, 1] so we use dictionaries adapted to this setting. The first four are orthonormal systems, which are used as a benchmark, while the last two are "real" dictionaries. More precisely, our dictionaries are

• the Fourier basis with M = n + 1 elements (denoted "Fou"),

• the histogram collection with the classical number √ n/2 ≤ M = 2 j0 < √ n of bins (denoted "Hist"),

• the Haar wavelet basis with maximal resolution n/2 < M = 2 j1 < n and thus M = 2 j1 elements (denoted "Haar"),

• the more regular Daubechies 6 wavelet basis with maximal resolution n/2 ≤ M = 2 j1 < n and thus M = 2 j1 elements (denoted "Wav"),

• the dictionary made of the union of the Fourier basis and the histogram collection and thus comprising M = n + 1 + 2 j0 elements. (denoted "Mix"),

• the dictionary which is the union of the Fourier basis, the histogram collection and the Haar wavelets of resolution greater than 2 j0 comprising M = n + 1 + 2 j1 elements (denoted "Mix2").

The orthonormal families we have chosen are often used by practitioners. Our dictionaries combine very different orthonormal families, sine and cosine with bins or Haar wavelets, which ensures a sufficiently incoherent design. We test the estimators of the following 4 functions shown in Figure 2 (with their Dantzig and Dantzig+Least Square estimates with the "Mix2" dictionary):

• a very spiky density

f 1 (t) = .47 × (4t × 1 t≤.5 + 4(1 -t) × 1 t>.5 ) + .53 × 75 × 1 .5≤t≤.5+ 1 75 ,
• a mix of Gaussian and Laplacian type densities

f 2 (t) = .45 × e -(t-.45) 2 /(2(.125) 2 )
1 0 e -(u-.45) 3 and4 summarize our numerical experiments for n = 500 and n = 2000 and 100 repetitions of the procedures. The left column deals with the comparison between Dantzig and Lasso, the center column shows the effectiveness of our data driven constraint and the right column illustrates the improvement of the two-step method. As expected, Dantzig and Lasso estimators are strictly equivalent when the dictionary is orthonormal and very close otherwise. For both algorithms and most of the densities, the best solution appears to be the "Mix2" dictionary, except for the density f 1 where the Haar wavelets are better for n = 500. This shows that the dictionary approach yields an improvement over the classical basis approach. One observes also that the "Mix" dictionary is better than the best of its constituent, namely the Fourier basis and the histogram family, which corroborates our theoretical results. The adaptive constraints are much tighter than their non adaptive counterparts and yield to much better numerical results. Our last series of experiments shows the significant improvement obtained with the least square step. As hinted by Candès and Tao [START_REF] Candès | The Dantzig selector: statistical estimation when p is much larger than n[END_REF], this can be explained by the bias common to ℓ 1 methods which is partially removed by this final least square adjustment. Studying directly the performance of this estimator is a challenging task.

Boxplots of Figures

Proofs

Proof of Theorem 1

To prove the first part of Theorem 1, we fix m ∈ {1, . . . , M } and we set for any i ∈ {1, . . . , n},

W i = 1 n (ϕ m (X i ) -β 0,m )
that satisfies almost surely

|W i | ≤ 2||ϕ m || ∞ n .
Then, we apply Bernstein's Inequality (see [START_REF] Massart | Concentration inequalities and model selection[END_REF] on pages 24 and 26) with the variables W i and -W i : for any u > 0,

P   | βm -β 0,m | ≥ 2σ 2 0,m u n + 2u||ϕ m || ∞ 3n   ≤ 2e -u . (18

Now, let us decompose σ2

m in two terms:

σ2 m = 1 2n(n -1) i =j (ϕ m (X i ) -ϕ m (X j )) 2 = 1 2n n i=1 (ϕ m (X i ) -β 0,m ) 2 + 1 2n n j=1 (ϕ m (X j ) -β 0,m ) 2 - 2 n(n -1) n i=2 i-1 j=1 (ϕ m (X i ) -β 0,m )(ϕ m (X j ) -β 0,m ) = s n - 2 n(n -1) u n with s n = 1 n n i=1 (ϕ m (X i ) -β 0,m ) 2 and u n = n i=2 i-1 j=1 (ϕ m (X i ) -β 0,m )(ϕ m (X j ) -β 0,m ). ( 19
)
Let us first focus on s n that is the main term of σ2 m by applying again Bernstein's Inequality with

Y i = σ 2 0,m -(ϕ m (X i ) -β 0,m ) 2 n which satisfies Y i ≤ σ 2 0,m n .
One has that for any u > 0

P σ 2 0,m ≥ s n + √ 2v m u + σ 2 0,m u 3n ≤ e -u with v m = 1 n E σ 2 0,m -(ϕ m (X i ) -β 0,m ) 2 2 .
But we have

v m = 1 n σ 4 0,m + E (ϕ m (X i ) -β 0,m ) 4 -2σ 2 0,m E (ϕ m (X i ) -β 0,m ) 2 = 1 n E (ϕ m (X i ) -β 0,m ) 4 -σ 4 0,m ≤ σ 2 0,m n (||ϕ m || ∞ + |β 0,m |) 2 ≤ 4σ 2 0,m n ||ϕ m || 2 ∞ .
Finally, with for any u > 0

S(u) = 2 √ 2σ 0,m ||ϕ m || ∞ u n + σ 2 0,m u 3n , we have P(σ 2 0,m ≥ s n + S(u)) ≤ e -u . (20)
The term u n is a degenerate U-statistics that satisfies for any u > 0

P(|u n | ≥ U (u)) ≤ 6e -u , (21)
with for any u > 0

U (u) = 4 3 Au 2 + 4 √ 2 + 2 3 Bu 3 2 + 2D + 2 3 F u + 2 √ 2C √ u,
where A, B, C, D and F are constants not depending on u that satisfy

A ≤ 4||ϕ m || 2 ∞ , B ≤ 2 √ n -1||ϕ m || 2 ∞ , C ≤ n(n -1) 2 σ 2 0,m , D ≤ n(n -1) 2 σ 2 0,m , and
F ≤ 2 √ 2||ϕ m || 2 ∞ (n -1) log(2n)
(see [START_REF] Reynaud-Bouret | On the influence of the support of functions for density estimation[END_REF]). Then, we have for any u > 0,

2 n(n -1) U (u) ≤ 32 3 ||ϕ m || 2 ∞ n(n -1) u 2 + 16 √ 2 + 8 3 ||ϕ m || 2 ∞ n √ n -1 u 3 2 + 2 √ 2 σ 2 0,m n(n -1) + 8 √ 2 3 log(2n)||ϕ m || 2 ∞ n √ n -1 u + 4σ 2 0,m n(n -1) √ u.
Now, we take u that satisfies

u = o(n) (22)
and log(2n) ≤ √ 2u.

Therefore, for any ε 1 > 0, we have for n large enough,

2 n(n -1) U (u) ≤ ε 1 σ 2 0,m + 16 √ 2 + 8 ||ϕ m || 2 ∞ n √ n -1 u 3 2 + 32 3 ||ϕ m || 2 ∞ n(n -1) u 2 .
So, for n large enough,

2 n(n -1) U (u) ≤ ε 1 σ 2 0,m + C 1 ||ϕ m || 2 ∞ u n 3 2 , (24)
where C 1 = 16 √ 2 + 19. Using Inequalities ( 20) and ( 21), we obtain

P σ 2 0,m ≥ σ2 m + S(u) + 2 n(n -1) U (u) = P σ 2 0,m ≥ s n - 2 n(n -1) u n + S(u) + 2 n(n -1) U (u) ≤ P σ 2 0,m ≥ s n + S(u) + P (u n ≥ U (u)) ≤ 7e -u .
Now, using [START_REF] Osborne | a) On the Lasso and its dual[END_REF], for any 0 < ε 2 < 1, we have for n large enough,

σ2 m + S(u) + 2 n(n -1) U (u) = σ2 m + 2 √ 2σ 0,m ||ϕ m || ∞ u n + σ 2 0,m u 3n + 2 n(n -1) U (u) ≤ σ2 m + 2 √ 2σ 0,m ||ϕ m || ∞ u n + σ 2 0,m u 3n + ε 1 σ 2 0,m + C 1 ||ϕ m || 2 ∞ u n 3 2 ≤ σ2 m + 2 √ 2σ 0,m ||ϕ m || ∞ u n + ε 2 σ 2 0,m + C 1 ||ϕ m || 2 ∞ u n 3 2 .
Therefore,

P (1 -ε 2 )σ 2 0,m ≥ σ2 m + 2 √ 2σ 0,m ||ϕ m || ∞ u n + C 1 ||ϕ m || 2 ∞ u n 3 2 ≤ 7e -u . (25)
Now, let us set

a = 1 -ε 2 , b = √ 2||ϕ m || ∞ u n , c = σ2 m + C 1 ||ϕ m || 2 ∞ u n 3 2
and consider the polynomial

P (x) = ax 2 -2bx -c, with roots b± √ b 2 +ac a
. So, we have

P (σ 0,m ) ≥ 0 ⇐⇒ σ 0,m ≥ b + √ b 2 + ac a ⇐⇒ σ 2 0,m ≥ c a + 2b 2 a 2 + 2b √ b 2 + ac a 2 .
It yields

P σ 2 0,m ≥ c a + 2b 2 a 2 + 2b √ b 2 + ac a 2 ≤ 7e -u , so, P σ 2 0,m ≥ c a + 4b 2 a 2 + 2b √ c a √ a ≤ 7e -u ,
which means that for any 0 < ε 3 < 1, we have for n large enough,

P σ 2 0,m ≥ (1 + ε 3 ) σ2 m + C 1 ||ϕ m || 2 ∞ u n 3 2 + 8||ϕ m || 2 ∞ u n + 2 √ 2||ϕ m || ∞ u n σ2 m + C 1 ||ϕ m || 2 ∞ u n 3 2 ≤ 7e -u .
Finally, we can claim that for any 0 < ε 4 < 1, we have for n large enough,

P σ 2 0,m ≥ (1 + ε 4 ) σ2 m + 8||ϕ m || 2 ∞ u n + 2||ϕ m || ∞ 2σ 2 m u n ≤ 7e -u .
Now, we take u = γ log M . Under Assumptions of Theorem 1, Conditions ( 22) and ( 23) are satisfied. The previous concentration inequality means that

P σ 2 0,m ≥ (1 + ε 4 )σ 2 m ≤ 7M -γ .
Now, using (18), we have for n large enough,

P |β 0,m -βm | ≥ η γ,m = P |β 0,m -βm | ≥ 2σ 2 m γ log M n + 2||ϕ m || ∞ γ log M 3n , σ 2 0,m < (1 + ε 4 )σ 2 m + P |β 0,m -βm | ≥ η γ,m , σ 2 0,m ≥ (1 + ε 4 )σ 2 m ≤ P   |β 0,m -βm | ≥ 2σ 2 0,m γ(1 + ε 4 ) -1 log M n + 2||ϕ m || ∞ γ(1 + ε 4 ) -1 log M 3n   + P σ 2 0,m ≥ (1 + ε 4 )σ 2 ≤ 2M -γ(1+ε4) -1 + 7M -γ .
Then, the first part of Theorem 1 is proved: for any ε > 0,

P |β 0,m -βm | ≥ η γ,m ≤ C(ε, δ, γ)M -γ 1+ε ,
where C(ε, δ, γ) is a constant that depends on ε, δ and γ.

For the second part of the result, we apply again Bernstein's Inequality with

Z i = (ϕ m (X i ) -β 0,m ) 2 -σ 2 0,m n which satisfies Z i ≤ (ϕ m (X i ) -β 0,m ) 2 n ≤ 4||ϕ m || 2 ∞ n .
One has that for any u > 0

P s n ≥ σ 2 0,m + √ 2v m u + 4||ϕ m || 2 ∞ u 3n ≤ e -u with v m = 1 n E σ 2 0,m -(ϕ m (X i ) -β 0,m ) 2 2 ≤ 4σ 2 0,m n ||ϕ m || 2 ∞ .
So, for any u > 0,

P s n ≥ σ 2 0,m + 2 √ 2σ 0,m ||ϕ m || ∞ u n + 4||ϕ m || 2 ∞ u 3n ≤ e -u .
Now, for any ε 5 > 0, for any u > 0,

P s n ≥ (1 + ε 5 )σ 2 0,m + ||ϕ m || 2 ∞ u n 4 3 + 2 ε 5 ≤ e -u .
Using [START_REF] Massart | Concentration inequalities and model selection[END_REF], with

S(u) = ||ϕ m || 2 ∞ u n 4 3 + 2 ε 5 , P σ2 m ≥ (1 + ε 5 )σ 2 0,m + S(u) + 2 n(n -1) U (u) = P s n - 2 n(n -1) u n ≥ (1 + ε 5 )σ 2 0,m + S(u) + 2 n(n -1) U (u) ≤ P s n ≥ (1 + ε 5 )σ 2 0,m + S(u) + P (-u n ≥ U (u)) ≤ e -u + 6e -u = 7e -u .
Using [START_REF] Osborne | a) On the Lasso and its dual[END_REF],

P σ2 m ≥ (1 + ε 1 + ε 5 )σ 2 0,m + S(u) + C 1 ||ϕ m || 2 ∞ u n 3 2 ≤ 7e -u . Since η γ,m = 2σ 2 m γ log M n + 2||ϕ m || ∞ γ log M 3n , with σ2 m = σ2 m + 2||ϕ m || ∞ 2σ 2 m γ log M n + 8||ϕ m || 2 ∞ γ log M n ,
we have for any ε 6 > 0,

η 2 γ,m ≤ (1 + ε 6 ) 2σ 2 m γ log M n + (1 + ε -1 6 ) 4||ϕ m || 2 ∞ (γ log M ) 2 9n 2 ≤ (1 + ε 6 ) 2γ log M n σ2 m + 2||ϕ m || ∞ 2σ 2 m γ log M n + 8||ϕ m || 2 ∞ γ log M n + 4 9 (1 + ε -1 6 ) ||ϕ m || ∞ γ log M n 2 ≤ (1 + ε 6 ) 2 σ2 m 2γ log M n + 4ε -1 6 (1 + ε 6 ) ||ϕ m || ∞ γ log M n 2 + 16(1 + ε 6 ) ||ϕ m || ∞ γ log M n 2 + 4(1 + ε -1 6 ) 9 ||ϕ m || ∞ γ log M n 2 .
Finally, with u = γ log M , with probability larger than 1 -7M -γ ,

σ2 m < (1 + ε 1 + ε 5 )σ 2 0,m + S(γ log M ) + C 1 ||ϕ m || 2 ∞ γ log M n 3 2
, and

η 2 γ,m < (1 + ε 6 ) 2 (1 + ε 5 + ε 1 )σ 2 0,m 2γ log M n + (1 + ε 6 ) 2 γ log M n 2 ||ϕ m || 2 ∞ 8 3 + 4 ε 5 + 2C 1 (1 + ε 6 ) 2 ||ϕ m || 2 ∞ γ log M n 5 2 + ||ϕ m || 2 ∞ γ log M n 2 4ε -1 6 (1 + ε 6 ) + 16(1 + ε 6 ) + 4(1 + ε -1 6 ) 9 .
Finally, with ε 6 = 1, ε 1 = ε 5 = 1 2 , for n large enough,

P η γ,m ≥ 4σ 0,m γ log M n + 10||ϕ m || ∞ γ log M n ≤ 7M -γ .
Note that 32/3 + 32 + 8 + 32 + 8/9 = 9.1409. For the last part, starting from [START_REF] Osborne | A new approach to variable selection in least squares problems[END_REF] with u = γ log M and ε 2 = 1 7 , we have for n large enough and with probability larger than 1 -7M -γ ,

6 7 σ 2 0,m ≤ σ2 m + 2 √ 2σ 0,m ||ϕ m || ∞ γ log M n + C 1 ||ϕ m || 2 ∞ γ log M n 3 2 ≤ σ2 m + 2 7 σ 2 0,m + 7||ϕ m || 2 ∞ γ log M n + C 1 ||ϕ m || 2 ∞ γ log M n 3 2
.

So, for n large enough,

4 7 σ 2 0,m ≤ σ2 m + 8||ϕ m || 2 ∞ γ log M n ≤ σ2 m and η γ,m > σ 0,m 8γ log M 7n + 2||ϕ m || ∞ γ log M 3n .

Proof of Theorem 2

Let λ = (λ m ) m=1,...,M and set ∆ = λ -λD . We have

||f λ -f 0 || 2 2 = || f D -f 0 || 2 2 + ||f λ -f D || 2 2 + 2 ( f D (x) -f 0 (x))(f λ (x) -f D (x))dx. ( 26
)
We have

||f λ -f D || 2 2 = ||f ∆ || 2 2 .
Moreover, with probability at least 1 -C 1 (ε, δ, γ)M 1-γ 1+ε , we have

( f D (x) -f 0 (x))(f λ (x) -f D (x))dx = M m=1 (λ m -λD m ) (G λD ) m -β 0,m (27)
≤||∆|| ℓ1 2||η γ || ℓ∞ ,
where the last line is a consequence of the definition of the Dantzig estimator and of Theorem 1. Then, we have

|| f D -f 0 || 2 2 ≤ ||f λ -f 0 || 2 2 + 4||η γ || ℓ∞ ||∆|| ℓ1 -||f ∆ || 2 2 .
We use then the following Lemma:

Lemma 1. Let J ⊂ {1, . . . , M }. For any λ ∈ R M ||∆ J C || ℓ1 ≤ ||∆ J || ℓ1 + 2||λ J C || ℓ1 + || λD || ℓ1 -||λ|| ℓ1 + ,
where ∆ = λD -λ.

Proof.[Proof of Lemma 1] This lemma is based on the fact that

|| λD || ℓ1 ≤ ||λ|| ℓ1 + || λD || ℓ1 -||λ|| ℓ1 + , which implies that ||∆ J + λ J || ℓ1 + ||∆ J C + λ J C || ℓ1 ≤ ||λ J || ℓ1 + ||λ J C || ℓ1 + || λD || ℓ1 -||λ|| ℓ1 + ,
and thus

||λ J || ℓ1 -||∆ J || ℓ1 + ||∆ J C || ℓ1 -||λ J C || ℓ1 ≤ ||λ J || ℓ1 + ||λ J C || ℓ1 + || λD || ℓ1 -||λ|| ℓ1 + .
Note that if λ satisfies the Dantzig condition then by definition of λD :

|| λD || ℓ1 -||λ|| ℓ1 + = 0.
Using the previous lemma, we have:

||∆ J C 0 || ℓ1 -||∆ J0 || ℓ1 + ≤ 2||λ J C 0 || ℓ1 + || λD || ℓ1 -||λ|| ℓ1 + . Using now Λ(λ, J c 0 ) = ||λ J C 0 || ℓ1 + (|| λD || ℓ 1 -||λ|| ℓ 1 ) + 2
, so that Λ(λ, J c 0 ) = ||λ J C 0 || ℓ1 as soon as λ satisfies the Dantzig condition, we obtain

||f ∆ || 2 ≥ κ J0 ||∆ J0 || ℓ2 -µ J0 ||∆ J C 0 || ℓ1 -||∆ J0 || ℓ1 + ≥ κ J0 ||∆ J0 || ℓ2 -2µ J0 Λ(λ, J c 0 )
and thus

||∆ J0 || ℓ2 ≤ 1 κ J0 ||f ∆ || 2 + 2 µ J0 κ J0 Λ(λ, J c 0 ).
We deduce thus

||∆|| ℓ1 ≤ 2||∆ J0 || ℓ1 + 2Λ(λ, J c 0 ) ≤ 2 |J 0 |||∆ J0 || ℓ2 + 2 ||λ J C 0 || ℓ1 ≤ 2 |J 0 | κ J0 ||f ∆ || 2 + 2Λ(λ, J c 0 ) 1 + 2µ J0 |J 0 | κ J0
and then since

4||η γ || ℓ∞ 2 |J 0 | κ J0 ||f ∆ || 2 ≤ 16|J 0 |||η γ || 2 ℓ∞ κ 2 J0 + ||f ∆ || 2 2
we have

4||η γ || ℓ∞ ||∆|| ℓ1 -||f ∆ || 2 2 ≤ 16|J 0 |||η γ || 2 ℓ∞ κ 2 J0 + 8||η γ || ℓ∞ Λ(λ, J c 0 ) 1 + 2µ J0 |J 0 | κ J0 ≤ 16|J 0 | 1 β + 1 κ 2 J0 ||η γ || 2 ℓ∞ + β Λ(λ, J c 0 ) 2 |J 0 | 1 + 2µ J0 |J 0 | κ J0 2 ,
which is the result of the theorem.

Consequences of Assumptions 1 and 2

To prove Proposition 1, we establish Lemmas 2 and 3. In the sequel, we consider two integers s and l such that 1 ≤ s ≤ M/2, l ≥ s and s + l ≤ M . We first recall Assumptions 1 and 2. Assumption 1 is stated in a more general form, which allows to unify the statement of the subsequent results.

• Assumption 1 φ min (s + l) > θ l,s+l .

• Assumption 2 lφ min (s + l) > sφ max (l).

In the sequel, we assume that Assumptions 1 and 2 are both true.

Lemma 2. Let J 0 ⊂ {1, . . . , M } with cardinality |J 0 | = s and ∆ ∈ R M . We denote by J 1 the subset of {1, . . . , M } corresponding to the l largest coordinates of ∆ (in absolute value) outside J 0 and we set J 01 = J 0 ∪ J 1 . We denote by P J01 the projector on the linear space spanned by (ϕ m ) m∈J01 . We have:

||P J01 f ∆ || 2 ≥ φ min (s + l)||∆ J01 || ℓ2 -min (µ 1 , µ 2 ) ||∆ J C 0 || ℓ1 , with µ 1 = θ l,s+l lφ min (s + l) and µ 2 = φ max (l) l .
Proof. For k > 1, we denote by J k the indices corresponding to the coordinates of ∆ outside J 0 whose absolute values are between the ((k -1) × l + 1)-th and the (k × l)-th largest ones (in absolute value). Note that this definition is consistent with the definition of J 1 . Using this notation, we have

||P J01 f ∆ || 2 ≥ ||P J01 f ∆J 01 || 2 -|| k≥2 P J01 f ∆J k || 2 ≥ ||f ∆J 01 || 2 - k≥2 ||P J01 f ∆J k || 2 .
Since J 01 has s + l elements, we have

||f ∆J 01 || 2 ≥ φ min (s + l)||∆ J01 || ℓ2 .
Note that P J01 f ∆J k = f CJ 01 for some vector C ∈ R M . Since,

P J01 f ∆J k -f ∆J k , P J01 f ∆J k = 0, one obtains that ||P J01 f ∆J k || 2 2 = f ∆J k , f CJ 01
and thus

||P J01 f ∆J k || 2 2 ≤ θ l,s+l ||∆ J k || ℓ2 ||C J01 || ℓ2 ≤ θ l,s+l ||∆ J k || ℓ2 ||f CJ 01 || 2 φ min (s + l) ≤ θ l,s+l φ min (s + l) ||∆ J k || ℓ2 ||P J01 f ∆J k || 2 .
This implies that

||P J01 f ∆J k || 2 ≤ θ l,s+l φ min (s + l) ||∆ J k || ℓ2 = µ 1 √ l||∆ J k || ℓ2 .
Moreover, using that J k has less than l elements, we obtain that

||P J01 f ∆J k || 2 ≤ ||f ∆J k || 2 ≤ φ max (l)||∆ J k || ℓ2 = µ 2 √ l||∆ J k || ℓ2 . Now using that ||∆ J k+1 || ℓ2 ≤ ||∆ J k || ℓ1 / √ l, we obtain k≥2 ||P J01 f ∆J k || 2 ≤ min (µ 1 , µ 2 ) ||∆ J C 0 || ℓ1
and finally

||P J01 f ∆ || 2 ≥ φ min (s + l)||∆ J01 || ℓ2 -min (µ 1 , µ 2 ) ||∆ J C 0 || ℓ1 .
Lemma 3. We use the same notations as in Lemma 2. For c ≥ 0, assume that

||∆ J C 0 || ℓ1 ≤ ||∆ J0 || ℓ1 + c. (28)
Then we have

||P J01 f ∆ || 2 ≥ max (κ 1 , κ 2 ) ||∆ J01 || ℓ2 -min (µ 1 , µ 2 ) c, with κ 1 = φ min (s + l) 1 - θ l,s+l φ min (s + l) s l and κ 2 = φ min (s + l) 1 - sφ max (l) lφ min (s + l) .
Proof. Using Lemma 2 and (28), we obtain that

||P J01 f ∆ || 2 ≥ φ min (s + l)||∆ J01 || ℓ2 -min (µ 1 , µ 2 ) (||∆ J0 || ℓ1 + c). Using ||∆ J0 || ℓ1 ≤ √ s||∆ J0 || ℓ2 , we deduce that ||P J01 f ∆ || 2 ≥ φ min (s + l) - √ s min (µ 1 , µ 2 ) ||∆ J01 || ℓ2 -c min (µ 1 , µ 2 ) ≥ max (κ 1 , κ 2 ) ||∆ J01 || ℓ2 -c min (µ 1 , µ 2 ) .

Proof of Theorem 5

The dictionary considered here is the Haar dictionary (φ jk ) j,k and is double-indexed. As a consequence, in the following, the quantity β 0,jk , βjk , σ 2 0,jk η γ,jk , σ2 jk and σ2 jk are defined as in (1), ( 2), (3), ( 5), ( 6) and [START_REF] Bunea | Sparse density estimation with l 1 penalties[END_REF] where ϕ m is replaced by φ jk . Note that, since f 0 = 1 [0,1] , we have, for j = -1, β 0,jk = 0 and for any j, σ 2 0,jk = 1 if k ∈ {0, . . . , 2 j -1} and 0 otherwise. The proof of ( 16) is provided by using the oracle inequality satisfied by hard thresholding given by Theorem 1 of [START_REF] Reynaud-Bouret | On the influence of the support of functions for density estimation[END_REF] and the rough control of the soft thresholding estimate by the hard one:

| βjk | -η γ,jk 1 {| βjk |≥η γ,jk } ≤ 2| βjk |1 {| βjk |≥η γ,jk } .
An alternative is directly obtained by adapting the oracle results derived for soft thresholding rules in the regression model considered by Donoho and Johnstone [START_REF] Donoho | Ideal spatial adaptation via wavelet shrinkage[END_REF].

To prove [START_REF] Efron | Least angle regression[END_REF], we establish the following lemma.

Lemma 4. Let γ < 1. We consider j ∈ N such that n (log n) α ≤ 2 j < 2n (log n) α , (29)
for some α > 1. Then for all ε > 0 such that γ + 2ε < 1,

2 j -1 k=0 E β2 jk 1 | βjk |≥η γ,jk ≥ 2γ(1 + ε)e -2 π (log n) 1-2α n -(γ+2ε) (1 + o n (1)).
Then, we use the following inequality. For j that satisfies (29), we have for r > 0,

E(|| f D -f 0 || 2 2 ) ≥ 2 j -1 k=0 E | βjk | -η γ,jk 2
1 | βjk |≥η γ,jk ≥ 2 j -1 k=0 E | βjk | -η γ,jk 2
1 | βjk |≥(1+r)η γ,jk ≥ r r + 1 2 2 j -1 k=0 E β2 jk 1 | βjk |≥(1+r)η γ,jk ≥ r r + 1 2 2 j -1 k=0 E β2 jk 1 | βjk |≥η jk,(1+r) 2 γ .
So, if r and ε are such that (1 + r) 2 γ + 2ε < 1, then applying Lemma 4, Inequality ( 17) is proved for any δ such that (1 + r) 2 γ + 2ε < δ < 1.

Proof. [Proof of Lemma 4] Let j that satisfies (29) and 0 ≤ k ≤ 2 j -1. We have

σ2 jk = σ2 jk + 2||φ j,k || ∞ 2γ σ2 jk logn n + 8γ||φ j,k || 2 ∞ logn n . So, for any 0 < ε < 1-γ 2 < 1 2 , σ2 jk ≤ (1 + ε)σ 2 jk + 2γ||φ j,k || 2 ∞ logn n ε -1 + 4 . Now, η γ,jk = 2γ σ2 jk logn n + 2||φ j,k || ∞ γlogn 3n ≤ 2γ logn n (1 + ε)σ 2 jk + 2γ||φ j,k || 2 ∞ logn n (ε -1 + 4) + 2||φ j,k || ∞ γlogn 3n ≤ 2γ(1 + ε)σ 2 jk logn n + 2||φ j,k || ∞ γlogn n 1 3 + 4 + ε -1 .
Furthermore, we have

σ2 jk = s njk - 2 n(n -1) u njk ,
where s njk and u njk are defined as in [START_REF] Knight | Asymptotics for lasso-type estimators[END_REF] and μnj is the largest integer smaller or equal to n2 -j-1 . We have

v nj ∼ 4γ(1 + ε)μ nj log n since (log n) α 4 -1 < n2 -j-1 -1 < μnj ≤ n2 -j-1 ≤ (log n) α 2 .

Now, set

l nj = μnj + 1 2 √ v nj , m nj = μnj - 1 2 √ v nj ,
that are positive for n large enough. If N + j1 = l nj and N - j1 = m nj then we have N + j1 -N - j1 = √ v nj . Finally, we obtain that

2 j -1 k=0 E β2 jk 1 | βjk |≥η γ,jk ≥ 2 2j n 2 v nj P N + j1 = l nj , N - j1 = m nj , |u njk | ≤ U (2logn) ≥ v nj (log n) -2α P N + j1 = l nj , N - j1 = m nj -P (|u njk | > U (2logn)) ≥ v nj (log n) -2α n! l nj !m nj !(n -l nj -m nj )! p lnj+mnj j (1 -2p j ) n-(lnj +mnj ) - 6 n 2 ≥ v nj (log n) -2α × n! l nj !m nj !(n -2μ nj )! p 2μnj j (1 -2p j ) n-2μnj - 6 n 2 , (30)
where p j = 1 [2 -j ,(1+0.5)2 -j [ (x)f 0 (x)dx = 1 [(1+0.5)2 -j ,2 -j+1 [ (x)f 0 (x)dx = 2 -j-1 .

Now, let us study each term of [START_REF] Yu | On model selection consistency of Lasso estimators[END_REF]. We have = exp 2μ nj log n + 2μ nj log(2 -j-1 ) -n2 -j (1 + o n (1)).

It remains to evaluate l nj ! × m nj !: Since 0 < ε < 1-γ 2 < 1 2 , we conclude that there exists δ < 1 such that

l nj ! × m nj ! =

Theorem 4 .

 4 Let us assume that assumptions of Theorem 3 are true. Let J 0 ⊂ {1, . . . , M } of size |J 0 | = s. Then, with probability at least 1 -C 1 (ε, δ, γ)M 1-γ 1+ε , we have for any β > 0,

Figure 1 :

 1 Figure 1: Graphs of γ → log 2 (R n (γ)) for n = 2 J with, from top to bottom, J = 4, 5, 6, . . . , 13

1 . 3 .

 13 Compute βm for all m,2. Compute σ2m , Compute η γ,m as defined in (5) by

4 . 5 .

 45 Compute the coefficients λD,γ of the Dantzig estimate, λD,γ = argmin λ∈R M ||λ|| ℓ1 such that λ satisfies the Dantzig constraint (4)∀ m ∈ {1, . . . .M }, |(Gλ) m -βm | ≤ η γ,mwith the homotopy-path-following method proposed by Asif and Romberg[START_REF] Asif | Dantzig selector homotopy with dynamic measurements[END_REF], Compute the Dantzig estimate f D,γ = M m=1

)

Figure 2 :Figure 3 :Figure 4 :

 234 Figure 2: The different densities and their "Mix2" estimates. Densities are plotted in blue while their estimates are plotted in black. The full line corresponds to the adaptive Dantzig studied in this paper while the dotted line corresponds to its least square variant.

( 1 -( 1 -( 1 -( 1 -

 1111 2μ nj log(p j )) = exp 2μ nj log(2 -j-1 ) , 2p j ) n-2μnj = exp ((n-2μ nj ) log(1 -2p j )) = exp -(n -2μ nj )2 -j + o n (1) = exp -n2 -j (1 + o n (1)),and(n -2μ nj ) n-2μnj = exp ((n -2μ nj ) log (n -2μ nj )) = exp (n -2μ nj ) log n + log 1 -2μ nj n = exp (n -2μ nj ) log n -2μ nj (n -2μ nj ) n (1 + o n (1)) = exp (n log n -2μ nj -2μ nj log n) (1 + o n (1)).Then, using the Stirling relation,n! = n n e -n √ 2πn(1 + o n (1)), we deduce that n! (n -2μ nj )! p 2μnj j 2p j ) n-2μnj = e n-2μnj e n × n n (n -2μ nj ) n-2μnj × p 2μnj j 2p j ) n-2μnj × (1 + o n (1)) = exp (-2μ nj ) × exp (n log n) (n -2μ nj ) n-2μnj × p 2μnj j 2p j ) n-2μnj × (1 + o n (1)) = exp (-2μ nj ) ×exp n log n + 2μ nj log(2 -j-1 ) -n2 -j exp (n log n -2μ nj -2μ nj log n) (1 + o n (1))

  with ϕ m replaced by φ jk . This implies that| βjk |≥ η γ,jk 1 |u njk |≤U(2logn) ) log n+w(ε) log n 1 |u njk |≤U(2logn) .Now, we consider a bounded sequence (w n ) n such that for any n, w n ≥ w(ε) and such that

	that implies that
	2 j -1 k=0	E β2 jk 1 | βjk |≥η γ,jk
	≥ jk 1 ≥ 2 j -1 k=0 E β2 2 j -1 k=0 2 j n 2 E (N + jk -N -jk ) 2 1 | βjk |≥	√ 2γ(1+ε)s njk	log n n +w(ε) 2 j/2 log n n	1 |u njk |≤U(2logn) .
	≥	2 j -1 k=0	2 j n 2 E (N + jk -N -jk ) 2 1	2 n |N + j 2 jk -N -jk |≥	q 2γ(1+ε) 2 j n (N + jk +N -jk ) log n n +w(ε) 2 j/2 log n n	1 |u njk |≤U(2logn)
	≥	2 j -1 k=0	2 j n 2 E (N + jk -N -jk ) 2 1 |N + jk -N -jk |≥	q 2γ(1+ε)(N + jk +N -jk ) log n+w(ε) log n	1 |u njk |≤U(2logn)
	≥	2 2j n 2 E (N + j1 -N -j1 ) 2 1 |N + j1 -N -j1 |≥	q 2γ(1+ε)(N + j1 +N -
											2
	η γ,jk ≤ 2γ(1 + ε)	logn n	s njk + 2γ(1 + ε)	logn n	×	2 n(n -1)	|u njk |+	2||φ j,k || ∞ γlogn n	1 3	+ 4 + ε -1 .
	Using (21), with probability larger than 1 -6n -2 , we have
								|u njk | ≤ U (2logn),

j1

√ vnj 2 is an integer with

v nj = 4γ(1 + ε)μ nj log(n) + w n log(n)

  nj log l nj + m nj log m nj -2μ nj ) × 2π μnj (1 + o n (1)). x nj ) log(1 + x nj ) = (1 + x nj ) x nj -x 2 nj log l nj = μnj (1 + x nj ) log (μ nj (1 + x nj )) = μnj (1 + x nj ) log(1 + x nj ) + μnj (1 + x nj ) log (μ nj ) nj ) + μnj (1 + x nj ) log (μ nj ) .Similarly, we obtain thatm nj log m nj = μnj -x nj + x 2 -x nj ) log (μ nj ) ,that implies thatl nj log l nj + m nj log m nj = μnj x 2 nj + O(x 4 nj ) + 2μ nj log (μ nj ) ≤ μnj x 2 nj + 2μ nj log(n2 -j-1 ) + O(μ nj x 4 nj ). nj x 4 nj ) ≤ (γ + 2ε) log n and l nj log l nj + m nj log m nj ≤ (γ + 2ε) log n + 2μ nj log(n2 -j-1 ).Finally, we havel nj ! × m nj ! = exp (l nj log l nj + m nj log m nj -2μ nj ) × 2π μnj (1 + o n (1)) ≤ exp (γ + 2ε) log n + 2μ nj log(n2 -j-1 ) -2μ nj × 2π μnj (1 + o n (1)).

	and using that
	(1 + nj 2	+	x 3 nj 3	+ O(x 4 nj )
			= x nj -	x 2 nj 2	+	x 3 nj 3	+ x 2 nj -	x 3 nj 2	+ O(x 4 nj )
			= x nj +	x 2 nj 2	-	x 3 nj 6	+ O(x 4 nj ),
	we obtain that
	l = μnj x nj +	x 2 nj 2	-	x 3 nj 6		+ O(x 4
	nj 2 nj ) + μnj (1 Since + x 3 nj 6 + O(x 4 μnj x 2 v nj nj = 4μ
		l nj
		e
	If we set		x nj =		√ v nj 2μ nj	= o n (1),
	then	l nj = μnj + m nj = μnj -	√ v nj 2 √ v nj 2	= μnj (1 + x nj ), = μnj (1 -x nj ),

lnj m nj e mnj 2πl nj 2πm nj (1 + o n (1)) = exp (l nj ∼ γ(1 + ε) log n,

we have, for n large enough, μnj x 2 nj + O(μ

  | βjk |≥η γ,jk ≥ v nj (log n) -2α exp 2μ nj log n + 2μ nj log(2 -j-1 ) -n2 -j exp ((γ + 2ε) log n + 2μ nj log(n2 -j-1 ) -2μ nj ) × 2π μnj -6 n 2 (1 + o n (1))

	2 j -1 k=0 jk 1 ≥ E β2 v nj (log n) -2α 2π μnj	exp (-(γ + 2ε) log n -2) -	6 n 2 (1 + o n (1))
	≥	2γ(1 + ε)e -2 π	(log n) 1-2α n -(γ+2ε) (1 + o n (1))

and Lemma 4 is proved.

and, since σ 2 0,jk = 1

, where c 1 , c 2 , c 3 , c 4 , C 1 and C 2 are universal constants. Finally, with probability larger than 1 -6n -2 , we obtain that

.

So, since γ < 1, there exists w(ε), only depending on ε such that with probability larger than

We set

. Then, we have

with

In particular, we have

Now, we can write


Caroline Peltier

Michel Visalli

Hélène Labouré

Cantin Hélard

Isabelle Andriot

Sylvie Cordelle

Jean-Luc Le Quéré

Pascal Schlich

Automatic pre-treatment and multiblock analysis of flavor release and sensory temporal data simultaneously collected in vivo

à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

▼Searched▼

...

Cite