Xin Jiang

Patricia Reynaud-Bouret

Vincent Rivoirard

Laure Sansonnet

Rebecca Willett

A data-dependent weighted LASSO under Poisson noise

Sparse linear inverse problems appear in a variety of settings, but often the noise contaminating observations cannot accurately be described as bounded by or arising from a Gaussian distribution. Poisson observations in particular are a characteristic feature of several real-world applications. Previous work on sparse Poisson inverse problems encountered several limiting technical hurdles. This paper describes a novel alternative analysis approach for sparse Poisson inverse problems that (a) sidesteps the technical challenges present in previous work, (b) admits estimators that can readily be computed using off-the-shelf LASSO algorithms, and (c) hints at a general weighted LASSO framework for broad classes of problems. At the heart of this new approach lies a weighted LASSO estimator for which data-dependent weights are based on Poisson concentration inequalities. Unlike previous analyses of the weighted LASSO, the proposed analysis depends on conditions which can be checked or shown to hold in general settings with high probability.

Introduction

Poisson noise arises in a wide variety of applications and settings, ranging among PET, SPECT, and pediatric or spectral CT [START_REF] Willett | Platelets: a multiscale approach for recovering edges and surfaces in photon-limited medical imaging[END_REF][START_REF] Lingenfelter | Sparsity regularization for image reconstruction with Poisson data[END_REF][START_REF] Schmidt | Optimal image-based weighting for energy-resolved CT[END_REF] in medical imaging, x-ray astronomy [START_REF]Nonuniform Expansion of the Youngest Galactic Supernova Remnant G1.9+0.3[END_REF][START_REF] Borkowski | Supernova Ejecta in the Youngest Galactic Supernova Remnant G1.9+0.3[END_REF][START_REF] Starck | Astronomical data analysis and sparsity: from wavelets to compressed sensing[END_REF], genomics [START_REF] Sansonnet | Wavelet thresholding estimation in a Poissonian interactions model with application to genomic data[END_REF], network packet analysis [START_REF] Estan | New directions in traffic measurement and accounting: Focusing on the elephants, ignoring the mice[END_REF][START_REF] Lu | Counter Braids: A novel counter architecture for per-flow measurement[END_REF], crime rate analysis [START_REF] Osgood | Poisson-Based Regression Analysis of Aggregate Crime Rates[END_REF], and social media analysis [START_REF] Xu | Socioscope: Spatio-Temporal Signal Recovery from Social Media[END_REF]. In these and other settings, observations are characterized by discrete counts of events (e.g. photons hitting a detector or packets arriving at a network router), and our task is to infer the underlying signal or system even when the number of observed events is very small. Methods for solving Poisson inverse problems have been studied using a variety of mathematical tools, with recent efforts focused on leveraging signal sparsity [START_REF] Jiang | Minimax Optimal Rates for Poisson Inverse Problems with Physical Constraints[END_REF][START_REF] Raginsky | Compressed sensing performance bounds under Poisson noise[END_REF][START_REF] Rish | Sparse Signal Recovery with Exponential-Family Noise[END_REF][START_REF] Raginsky | Performance bounds for expander-based compressed sensing in Poisson noise[END_REF][START_REF] Lingenfelter | Sparsity regularization for image reconstruction with Poisson data[END_REF][START_REF] Starck | Astronomical data analysis and sparsity: from wavelets to compressed sensing[END_REF][START_REF] Rohban | Minimax Optimal Sparse Signal Recovery with Poisson Statistics[END_REF].

Unfortunately, the development of risk bounds for sparse Poisson inverse problems presents some significant technical challenges. Methods that rely on the negative Poisson log-likehood to measure how well an estimate fits observed data perform well in practice but are challenging to analyze. For example, the analysis framework considered in [START_REF] Jiang | Minimax Optimal Rates for Poisson Inverse Problems with Physical Constraints[END_REF][START_REF] Raginsky | Compressed sensing performance bounds under Poisson noise[END_REF][START_REF] Rish | Sparse Signal Recovery with Exponential-Family Noise[END_REF] builds upon a coding-theoretic bound which is difficult to adapt to many of the computationally tractable sparsity regularizers used in the Least Absolute Shrinkage and Selection Operator (LASSO) [START_REF] Tibshirani | Regression shrinkage and selection via the lasso[END_REF] or Compressed Sensing (CS) [START_REF] Candes | Near-optimal signal recovery from random projections: Universal encoding strategies?[END_REF][START_REF] Donoho | Compressed Sensing[END_REF]; those analyses have been based on impractical 0 sparsity regularizers. In contrast, the standard LASSO analysis framework easily handles a variety of regularization methods and has been generalized in several directions [START_REF] Bickel | Simultaneous analysis of Lasso and Dantzig selector[END_REF][START_REF] Bunea | Aggregation for Gaussian regression[END_REF][START_REF] Lounici | Sup-norm convergence rate and sign concentration property of Lasso and Dantzig estimators[END_REF][START_REF] Tibshirani | Regression shrinkage and selection via the lasso[END_REF][START_REF] Van De Geer | High-dimensional generalized linear models and the LASSO[END_REF][START_REF] Bühlmann | Statistics for high-dimensional data[END_REF]. However, it does not account for Poisson noise, which is heterogeneous and dependent on the unknown signal to be estimated.

This paper presents an alternative approach that sidesteps these challenges. We describe a novel weighted LASSO estimator, where the data-dependent weights used in the regularizer are based on Poisson concentration inequalities and control for the ill-posedness of the inverse problem and heteroscedastic noise simultaneously. We establish oracle inequalities and recovery error bounds for general settings, and then explore the nuances of our approach within two specific sparse Poisson inverse problems arising in genomics and imaging.

Problem formulation

We observe a potentially random matrix A = (a kl ) k,l ∈ R n×p + and conditionally on A, we observe

Y ∼ P(Ax * )
where Y ∈ R n + , x * ∈ R p + , and where x * is sparse or compressible. The notation P denotes the Poisson distribution, so that, conditioned on A and x * , we have the likelihood

p(Y k |Ax * ) = e -(Ax * ) k [(Ax * ) k ] Y k /Y k !, k = 1, . . . , n.
Conditioned on Ax * , the elements of Y are independent. The aim is to recover x * , the true signal of interest. The matrix A corresponds to a sensing matrix or operator which linearly projects x * into another space before we collect Poisson observations. Often we will have n < p, but this inverse problem can still be challenging if n ≥ p depending on the signal-to-noise ratio or the condition of the operator A.

Because elements of A are nonnegative, we cannot rely on the standard assumption that A A is close to an identity matrix. However, in many settings there is a proxy operator, denoted A, which is amenable to sparse inverse problems and is a simple linear tranformation of the original operator A. A complementary linear transformation may then be applied to Y to generate proxy observations Y , and we use A and Y in the estimators defined below. In general, the linear transformations are problem-dependent and should be chosen to ensure Assumptions RE, Weights, and/or G (presented in Section 2) are satisfied to achieve the general results of Section 2. We provide explicit examples in Sections 4 and 5.

Weighted LASSO estimator for Poisson inverse problems

The basic idea of our approach is the following. We consider three main estimation methods in this paper:

Least squares estimator on true support: Let S * := supp(x * ) denote the true signal support;

we consider the least squares estimate on S * :

x LS :=I S * ( A S * ) # Y (1.1)
where A S * ∈ R n×s is a submatrix of A with columns of A S * equal to the columns of A on support set S * , ( A S * ) # standing for its pseudo-inverse and I S * ∈ R p×s is a submatrix of the identity matrix I p with columns of I S * equal to the columns of I p on support set S * . Note that this estimator functions as an oracle, since in general the support set S * is unknown. However, we show that the below LASSO estimators are able to correctly identify the support with high probability under certain conditions.

(Classical) LASSO estimator:

x LASSO := argmin

x∈R p Y -Ax 2 2 + γd x 1 , (1.2)
where γ > 2 is a constant and d > 0 is a data-dependent scalar to be defined later.

Weighted LASSO estimator:

x WL := argmin

x∈R p Y -Ax 2 2 + γ p k=1 d k |x k | (1.3)
where γ > 2 is a constant and the d k 's are positive and data-dependent; they will be defined later. Note that the estimator in (1.3) can equivalently be written as

z = argmin z∈R p Y -AD -1 z 2 2 + γ z 1 (1.4a) x WL =D -1 z (1.4b)
where D is a diagonal matrix with the k th diagonal element equal to d k . Since z and D -1 z will always have the same support; this formulation suggests that the weighted LASSO estimator in (1.3) is essentially reweighing the columns of A to account for the heteroscedastic noise.

A weighted LASSO estimator similar to (1.3) has been proposed and analyzed in past work, notably [START_REF] Van De Geer | The adaptive and the thresholded Lasso for potentially misspecified models (and a lower bound for the Lasso)[END_REF][START_REF] Bickel | Simultaneous analysis of Lasso and Dantzig selector[END_REF], where the weights are considered fixed and arbitrary. The analysis in [START_REF] Van De Geer | The adaptive and the thresholded Lasso for potentially misspecified models (and a lower bound for the Lasso)[END_REF], however, does not extend to signal-dependent noise (like we have in Poisson noise settings). In addition, risk bounds in that work hinge on a certain "weighted irrepresentable condition" on the sensing or design matrix A which cannot be verified or guaranteed for the data-dependent weights we consider, even when A is known to satisfy criteria such as the Restricted Eigenvalue condition [START_REF] Bickel | Simultaneous analysis of Lasso and Dantzig selector[END_REF] or Restricted Isometry Property [START_REF] Candès | The restricted isometry property and its implications for compressed sensing[END_REF]. Similarly, the analysis of a weighted LASSO estimator described in [START_REF] Bickel | Simultaneous analysis of Lasso and Dantzig selector[END_REF] cannot directly be adopted in settings with signal-dependent noise and data-dependent weights.

If x * has support of size s, then, over an appropriate range of values of s, the oracle estimator in (1.1) satisfies this very tight bound

x LS -x * 2 2 ≤ 1 (1 -δ s ) 2 k∈S * ( A ( Y -Ax * )) 2 k , (1.5)
where δ s is a parameter associated with the restricted eigenvalue condition of the sensing matrix A (see Proposition 2). Our analysis reveals that if we choose weights d 1 , . . . , d p satisfying

|( A ( Y -Ax * )) k | ≤ d k for k = 1, . . . , p, (1.6)
then similar results hold for the LASSO and weighted LASSO estimates under conditions of Theorem 3:

x WL -x * 2 2 ≤ C γ (1 -δ s ) 2 k∈S * d 2 k (1.7) and x LASSO -x * 2 2 ≤ C γ (1 -δ s ) 2 sd 2 , (1.8)
where C γ only depends on γ. Hence, if we do not have practical constraints such as the fact that the d k 's should only depend on the data, one could take

d k = |( A ( Y -Ax * )) k |
for the weighted LASSO to recover the exact same rates as the oracle, whereas for the LASSO, one could only take

d = max k |( A ( Y -Ax * )) k |
, which only leads to worse bounds.

In practice the weights can only depend on the observed data: we show on two examples (a Bernoulli sensing matrix and random convolution, see Sections 4 and 5) that we can compute such weights from the data (by using Poisson concentration inequalities) such that (1.6) holds with high probability and those weights are small enough to ensure risk bounds consistent with prior art, leading to weighted LASSO estimates that have a better convergence rate than LASSO estimates.

The role of the weights

Our approach, where the weights in our regularizer are random variables, is similar to [START_REF] Bertin | Adaptive Dantzig density estimation[END_REF][START_REF] Hansen | Lasso and probabilistic inequalities for multivariate point processes[END_REF][START_REF] Huang | Adaptive Lasso for sparse high-dimensional regression models[END_REF][START_REF] Zou | The adaptive Lasso and its oracle properties[END_REF]. In some sense, the weights play the same role as the thresholds in the estimation procedure proposed in [START_REF] Donoho | Ideal spatial adaptation by wavelet shrinkage[END_REF][START_REF] Juditsky | On minimax density estimation on R[END_REF][START_REF] Reynaud-Bouret | Near optimal thresholding estimation of a Poisson intensity on the real line[END_REF][START_REF] Reynaud-Bouret | Adaptive density estimation: a curse of support?[END_REF][START_REF] Sansonnet | Wavelet thresholding estimation in a Poissonian interactions model with application to genomic data[END_REF]. The role of the weights are twofold:

• control of the random fluctuations of A Y around its mean, and

• compensate for the ill-posedness due to A. Note that ill-posedness is strengthened by the heteroscedasticity of the Poisson noise.

To understand the role of the weights more deeply, let us look at a very basic toy example where A is a diagonal matrix with decreasing eigenvalues λ 1 , . . . , λ p . It is well known that many classical inverse problems [START_REF] Cavalier | Inverse problems in statistics[END_REF] can be rephrased as this toy example. Informally and since Poisson noise is just a particular case of heteroscedasticity, one could rephrase the direct problem in

y k = λ k x * k + k ,
with k of zero mean and standard deviation σ k . Let us first consider the ramifications of setting Y = Y , A = A. The quantity 1 -δ s appearing in (1.5) is then the smallest eigenvalue of A, that is, λ p . On the other hand, by (1.6), d k should be an upper bound on λ k k . From a very heuristic point of view, d k should therefore be of the order of λ k σ k and the bound (1.5) is actually of the order of k∈S *

λ 2 k σ 2 k λ 2 p
. In particular even if the true support S * is included in the high values of the λ k 's , we still pay the worse case scenario with the division by λ 2 p . On the other hand, the classical inverse problem choice . Then, for the interesting case where the (λ 2 k ) k∈S * 's are larger than λ p , this is much better and we only pay for ill-posedness in the support of x * . Note also that in this set-up, if one wants to choose a constant weight d, then d max k (σ k /λ k ) and one again pays for global ill-posedness and not just ill-posedness in the support of x * .

Y = A -1 Y , A = A -1 A = I p gives that 1 -δ s =
This toy example shows us three things:

(i) The d k 's are indeed balancing both ill-posedness and heteroscedasticity of the problem.

(ii) The choice of the mappings from A to A and Y to Y is really important for the rates.

(iii) The non-constant d k 's allows for "adaptivity" with respect to the local ill-posedness of the problem, in terms of the support of x * .

In the two examples (Bernoulli and Convolution) of Sections 4 and 5, we need to choose A so that the corresponding Gram matrix G = A A is as close as possible to the identity (therefore (1 -δ s ) in (1.5) will be as close as possible to 1) and choose Y such that A ( Y -Ax * ) is as small as possible, which will make the d k 's as small as possible therefore giving the best possible rates. This choice in particular will enable us to get rates consistent with the minimax rates derived in [START_REF] Jiang | Minimax Optimal Rates for Poisson Inverse Problems with Physical Constraints[END_REF] in a slightly different framework.

Organization of the paper

Section 2 describes general oracle inequalities, recovery rate guarantees, and support recovery bounds for the three estimators described above, given weights which satisfy (1.6). We then describe a general framework for finding such weights using the observed data in Section 3. We then describe exact weights and resulting risk bounds for two specific Poisson inverse problems: (a) Poisson compressed sensing using a Bernoulli sensing matrix, which models certain optical imaging systems such as [START_REF] Duarte | Single Pixel Imaging via Compressive Sampling[END_REF], and (b) a ill-posed Poisson deconvolution problem arising in genetic motif analysis, building upon the formulation described in [START_REF] Sansonnet | Wavelet thresholding estimation in a Poissonian interactions model with application to genomic data[END_REF]. We conclude with simulation-based verification of our derived rates.

2 Main result: Theoretical performance bounds for the weighted LASSO

In this section, the bounds that are derived do not take into account the noise structure and could be used whatever the underlying noise. They rely mostly on the following two main assumptions that are proved to be matched with high probability in the next sections. The first is known as the Restricted Eigenvalue Condition (see [START_REF] Bickel | Simultaneous analysis of Lasso and Dantzig selector[END_REF]).

Assumption RE(s, c 0 ) There exists 0 ≤ δ s,c 0 < 1 such that for all J ⊂ {1, . . . , p} with |J| ≤ s and all x ∈ R p satisfying

x J c 1 ≤ c 0 x J 1 , we have Ãx 2 2 x J 2 2 ≥ 1 -δ s,c 0 .
Our other key assumption dictates the necessary relationship between the weights used to regularize the estimates x WL and x LASSO .

Assumption Weights({d

k } k ) For k = 1, . . . , p, | A ( Y -Ax * )| k ≤ d k .
(2.1)

In the sequel, we use the following notation:

d max := max

Recovery error bounds

Our first result is a recovery error bound that does not assume sparsity on the underlying signal.

Theorem 1. Let s > 0 be an integer and let x * s denote the best s-sparse approximation to x * . Let S * := supp(x * s ). Let γ > 2 and assume that Assumption Weights({d k } k ) is satisfied for some positive weights d k 's. Let ρ γ,d be consequently defined by (2.2). Define the bias term

B s := max{ A(x * -x * s ) 2 2 , x * -x * s 1 };
note that B s = 0 when x * is s-sparse. Under Assumption RE(2s, 2ρ γ,d ) with parameter δ 2s,2ρ γ,d , the Weighted LASSO estimator x WL satisfies

x * -x WL 2 ≤ 2 √ 2γ(1 + 2ρ γ,d ) 1 -δ 2s,2ρ γ,d B s + k∈S * d 2 k 1/2 + 3 + 3 (γ -2)d min B s (2.3) x * -x WL 1 ≤ 2 √ 2γ(1 + 2ρ γ,d ) 1 -δ 2s,2ρ γ,d B s + k∈S * d 2 k 1/2 √ s + 3 + 3 (γ -2)d min B s . (2.4)
Remark 1. Under the conditions of Theorem 1, we have for the LASSO estimator

x LASSO x * -x LASSO 2 ≤ 2 √ 2γ(1 + 2ρ γ,d ) 1 -δ 2s,2ρ γ,d (B s + d 2 s) 1/2 + 3 + 3 (γ -2)d B s (2.5) x * -x LASSO 1 ≤ 2 √ 2γ(1 + 2ρ γ,d ) 1 -δ 2s,2ρ γ,d (B s + d 2 s) 1/2 √ s + 3 + 3 (γ -2)d B s . (2.6)
Note that we can take ρ γ,d = γ+2 γ-2 .

Support recovery guarantees

To obtain support recovery guarantees, we need the following much stronger condition.

Assumption G(ξ) Let G := A A be the Gram matrix associated with A. There exists a constant ξ > 0 such that

G -I p k,
≤ ξ for all k, ∈ {1, . . . , p}.

Assumption G(ξ) is stronger than RE(s, c 0 ) for sufficiently small values of ξ by the following result.

Proposition 1. Under Assumption G(ξ) for all x vector of R p , c 0 ≥ 0 and J ⊂ {1, . . . , p} such that

x J c 1 ≤ c 0 x J 1 ,
the following inequality holds:

Ãx 2 2 x J 2 2 ≥ 1 -(1 + 2c 0 )|J|ξ.
Hence Assumption RE(s, c 0 ) holds with constant δ s,c 0 = (1 + 2c 0 )ξs as soon as

s(1 + 2c 0 ) < ξ -1 .
In particular, if c 0 = 0, namely x is supported by J, then we obtain the lower bound of a classical RIP as soon as s < ξ -1 .

(2.7)

Theorem 2. Assume that x * is s-sparse for s a positive integer. Let γ > 2 and Assumptions RE(s, 0) (with parameter δ s,0 ), Weights({d k } k ), and G(ξ) be satisfied. Further assume s satisfies

ξ 2γ 1 -δ s,0 s k∈S * d 2 k 1/2 < γ 2 -1 min k ∈S * d k . (2.8)
Let S * = supp(x * ). Under these conditions,

supp( x WL ) ⊆ supp(x * ).
Theorem 2 is proved in Appendix A.3. This support guarantee is the main ingredient to derive sharper bounds than the ones of Theorem 1 at the price of in general a much stronger condition, namely Assumption G(ξ).

Note that an obvious choice for δ s,0 thanks to Proposition 1 is δ s,0 = sξ but it is possible to have much better constants (see Section 4).

Remark 2. In the special case where

d := d 1 = d 2 = . . . = d p , Theorem 2 implies that if s is small enough, namely (since s(1 -δ s,0 ) -1 is an increasing function of s) if s satisfies s(1 -δ s,0 ) -1 < γ -2 4γ ξ -1 , (2.9)
then LASSO estimator satisfies supp( x LASSO ) ⊆ supp(x * ).

Recovery error bounds for sparse signals

The recovery error bounds in Theorem 1 holds even for non-sparse x * . However, if x * is sufficiently sparse, even tighter bounds are possible, as we show below thanks to the support recovery guarantees. Before giving a better bound for the recovery error bounds than the one given in Theorem 1, let us look more closely at the oracle case.

Proposition 2. Assume that S * = supp(x * ) is known and s = |S * |. If Assumptions RE(s, 0) (with parameter δ s,0 ) is satisfied; then x LS , the least square estimate of x * on S * satisfies

x LS -x * 2 2 ≤ 1 (1 -δ s,0 ) 2 k∈S * ( A ( Y -Ax * )) 2 k .
The weighted LASSO estimate satisfies the following bound.

Theorem 3. Let γ > 2. Assume that x * is s-sparse for s a positive integer satisfying the conditions of Theorem 2 and let S * := supp(x * ). Then

x WL -x * 1 ≤ 2γs 1/2 1 -δ s,0 k∈S * d 2 k 1/2
, (2.10)

x WL -x * 2 ≤ 2γ 1 -δ s,0 k∈S * d 2 k 1/2 , (2.11
)

and x WL -x * ∞ ≤ γd max .
Theorem 3 is proved in Appendix A.5. Remark 4. We deduce that under assumptions of Theorem 3, for any 1 < q < ∞, the weighted lasso estimate x WL satisfies

x WL -x * q q ≤ K γ,q s 1 -δ s,0 d q max ,
for some constant K γ,q only depending on γ and q.

Remark 5. Let us compare the assumptions of Theorem 1 and 2 under the result of Proposition 1. If Assumption G(ξ) is fulfilled and if we can take δ s,c 0 = s(1 + 2c 0 )ξ < 1 with c 0 = 2ρ γ,d , the constraint on the sparsity level s for Theorem 1 can be rewritten as

sξ 1 + 4 γ + 2 γ -2 d max d min < 1.
But on the other hand (2.8) is a consequence of

ξ 2γ 1 -δ s,0 sd max < γ 2 -1 d min ,
with δ s,0 = sξ thanks to Proposition 1. Hence this can be rewritten as

sξ 1 + 4 γ γ -2 d max d min < 1.
Therefore if Assumption G(ξ) holds and if we use δ s,2ρ γ,d = s(1 + 4ρ γ,d )ξ and not sharper constants, then the constraint on the sparsity is less stringent for Theorem 2 than for Theorem 1. Note that the fact that k∈S * d 2 k appears in (2.8) instead of its upper bound sd 2 max makes in fact (2.8) much less troublesome to satisfy that the constraint coming from Assumption RE(s, c 0 ) (see in particular Section 5). Remark 6. We can also easily combine results of Theorems 2 and 3 to get exact support recovery as soon as

min k∈S * |x * k | > γd max .
Indeed, if there exists k 1 such that x * k 1 = 0 and x k 1 = 0, then

|x * k 1 | ≤ x LASSO -x * ∞ ≤

Choosing data-dependent weights

In general, choosing d k s to ensure that Assumption Weights({d k } k ) is satisfied is highly problemdependent, and we give two explicit examples in the following two sections. In this section we present the general strategy we adopt for choosing the weights. The weights d k are chosen so that for all k

|( A ( Y -Ax * )) k | ≤ d k . (3.1)
The modifications Y and A of Y and A that we have in mind are linear, therefore one can generally rewrite for each k,

( A ( Y -Ax * )) k = R k (Y -Ax * ) + r k (A, x * ),
for some vector R k which depends on k and A and for some residual term r k (A, x * ), also depending on k and A. The transformations are chosen such that d k is small. With the previous decomposition, the first term R k (Y -Ax * ) is naturally of null conditional expectation given A and therefore of zero mean. The Y are usually chosen such that r k (A, x * ) is also of zero mean which globally guarantees that E((

A ( Y -Ax * )) k ) = 0.
In the two following examples, the term r k (A, x * ) is either mainly negligible with respect to R k (Y -Ax * ) (Bernoulli case, Section 4) or even identically zero (convolution case, Section 5). Therefore the weights are mainly given by concentration formulas on quantities of the form R (Y -Ax * ) as given by the following Lemma.

Lemma 1. For all vectors R = (R ) =1,...,n ∈ R n , eventually depending on A, let R 2 = (R 2 ) =1,...,n .
Then the following inequality holds for all θ > 0,

P R Y ≥ R Ax * + √ 2vθ + bθ 3 A ≤ e -θ , (3.2)
with v = R 2 E(Y |A) = R 2 Ax * and b = ||R|| ∞ . Moreover P |R Y -R Ax * | ≥ √ 2vθ + bθ 3 A ≤ 2e -θ , (3.3)
P   v ≥ b 2 θ 2 + 5b 2 θ 6 + R 2 Y 2 A   ≤ e -θ (3.4)
and

P |R Y -R Ax * | ≥ b 2 θ 2 + 5b 2 θ 6 + R 2 Y √ 2θ + bθ 3 A ≤ 3e -θ . (3.5)
Equations (3.2) and (3.3) give the main order of magnitude for R (Y -Ax * ) with high probability but are not sufficient for our purpose since v still depends on the unknown x * . That is why Equation (3.4) provides an estimated upper-bound for v with high probability. Equation (3.5) is therefore our main ingredient for giving observable d k 's that are satisfying Assumption Weights({d k } k ). Note that depending on A, one may also find more particular way to define those weights, in particular constant ones. This is illustrated in the two following examples.

Example: Photon-limited compressive imaging

A widely-studied compressed sensing measurement matrix is the Bernoulli or Rademacher ensemble, in which each element of A is drawn iid from a Bernoulli(q) distribution for some q ∈ (0, 1). (Typically authors consider q = 1/2.) In fact, the celebrated Rice single-pixel camera [START_REF] Duarte | Single Pixel Imaging via Compressive Sampling[END_REF] uses exactly this model to position the micromirror array for each projective measurement. This sensing matrix model has also been studied in previous work on Poisson compressed sensing (cf. [START_REF] Jiang | Minimax Optimal Rates for Poisson Inverse Problems with Physical Constraints[END_REF][START_REF] Raginsky | Compressed sensing performance bounds under Poisson noise[END_REF]). In this section, we consider our proposed weighted-LASSO estimator for this sensing matrix.

Rescaling and recentering

Our first task is to define the surrogate design matrix A and surrogate observations Y . In this set-up, one can easily see that the matrix

A = A nq(1 -q) - q1 n×1 1 p×1 nq(1 -q) (4.1)
satisfies E( G) = E( A A) = I p (see Appendix), which will help us to ensure that Assumptions RE and G hold. To make d k as small as possible and still satisfying Assumption Weights({d k } k ), we would like to have E( A ( Y -Ax * )) = 0, as stated previously. Some computations given in the appendix shows that it is sufficient to take

Y = 1 (n -1) nq(1 -q) (nY - n =1 Y 1 n×1 ). (4.2)
In the below, we use the , , and notation to mask absolute constant factors.

Assumption RE holds with high probability

With high probability, the sensing matrix A considered here satisfies the Restricted Isometry property with parameter δ s ≤ 1/2. That is:

Theorem 4 (RIP for Bernoulli sensing matrix (Theorem 2.4 in [START_REF] Mendelson | Uniform uncertainty principle for Bernoulli and subgaussian ensembles[END_REF])). There exists constants

c 1 , c 2 , c 3 , C > 0 such that for any δ s ∈ (0, 1/2), if s ≤ c 1 δ 2 s n α 4 q log(c 2 pα 4 q /δ 2 s n) , and n ≥ α 4 q c 3 δ 2 s log p (4.3)
where

α q := 3 2q(1-q) , q = 1/2 1, q = 1/2 , then for any x -s-sparse, (1 -δ s ) x 2 2 ≤ Ax 2 2 ≤ (1 + δ s ) x 2 2
with probability exceeding 1 -C/p for a universal positive constant C. Lemma 4.1(i) from [START_REF] Bickel | Simultaneous analysis of Lasso and Dantzig selector[END_REF], combined with Lemma 2.1 of [START_REF] Candès | The restricted isometry property and its implications for compressed sensing[END_REF], shows that Assumption RE(s, c 0 ) holds for δ s,c 0 with

1 -δ s,c 0 = 1 -δ 2s 1 - δ 3s c 0 1 -δ 2s .
Using δ 3s ≥ δ 2s , straightforward computations show that Assumption RE(s, c 0 ) holds for δ s,c 0 as soon as δ s,c 0 ≤ δ 3s (1+2c 0 ). We use this result with c 0 = 2ρ γ,d and fix 0 < δ 6s < (2+8ρ γ,d ) -1 . Then, as required by Theorem 1, Assumption RE(2s, 2ρ γ,d ) holds for parameter δ 2s,2ρ γ,d = δ 6s (1+4ρ γ,d ) < 1/2 with probability exceeding 1 -C/p for a universal positive constant C if

s nq 2 (1 -q) 2 ρ 2 γ,d log(pρ 2 γ,d /nq 2 (1 -q) 2 )
and n

ρ 2 γ,d log p q 2 (1-q) 2 .

Assumption G holds with high probability

Proposition 3. There is a universal positive constant C so that, with probability larger than

1 -C/p, |( G -I p ) k | ≤ ξ, with ξ = 6 log p n (1 -q) 2 q + q 2 1 -q + log p n max 1 -q q , q 1 -q .

Choice of the weights

Because the matrix A has a very special form, one can derive two sets of weights. Constant weights are easier to handle with respect to the previous Theorems because d max /d min = 1. However we will see that they may lead to some loss in the rates of convergence depending on the parameter values. Non-constant weights follow the general guidelines given by Lemma 1 and are therefore more easy to derive. However we need in this case to derive very precise upper and lower bounds to control d max /d min .

Constant weights

We can leverage the machinery described in Section 3 to derive an expression for a data-dependent weight d to use in the unweighted LASSO estimator defined in (1.2). Let

W = max u,k=1,...,p w(u, k) with w(u, k) = 1 n 2 (n -1) 2 q 2 (1 -q) 2 n =1 a ,u na ,k - n =1 a ,k 2 . and let N = 1 nq -6nq(1 -q) log(p) -max(q, 1 -q) log(p)   3 log(p) 2 + 5 log(p) 2 + n =1 Y   2 be an estimator of ||x * || 1 .
Then the constant weights are given by

d = 6W log(p) N + log(p) (n -1)q(1 -q) + c 3 log(p) n + 9 max(q 2 , (1 -q) 2 ) n 2 q(1 -q) log(p) 2 N , (4.4)
where c is a constant and one can prove that they satisfy Assumption Weights(d) with high probability (see Proposition 5). Note that the third term in the expression for d in (4.4) is negligible when x * 1 log p/n 1. Furthermore, as shown in Proposition 6, in the range

nq 2 (1 -q) log(p)
we have

d log(p)||x * || 1 n min(q, 1 -q) + log(p)||x * || 1 n + log(p) nq(1 -q) .

Non-constant weights

For all k = 0, . . . , p -1, define the vector V k of size n as

V k, = na ,k -n =1 a ,k n(n -1)q(1 -q) 2 .
The non-constant weights are given by

d k = 6 log(p) 3 log(p) 2(n -1) 2 q 2 (1 -q) 2 + 5 log(p) 2(n -1) 2 q 2 (1 -q) 2 + V k Y + log(p) (n -1)q(1 -q) + (4.5) +c 3 log(p) n + 9 max(q 2 , (1 -q) 2 ) n 2 q(1 -q) log(p) 2 N , (4.6)
where c is a constant. They also satisfy Assumption Weights(d) with high probability (see Proposition 7). Furthermore, as shown in Proposition 8, in the range

nq 2 (1 -q) log(p)
we have

d k log(p) x * k nq + u =k x * u n(1 -q) + log(p)||x * || 1 n + log(p) nq(1 -q) .

Summary of rate results

In this section, we consider the data-dependent LASSO parameter d defined in (4.4) and the datadependent weighted LASSO parameters {d k } k defined in (4.6). In this setting, with probability exceeding 1 -C/p for a universal constant C

d 2 max d 2 min 1 + x * ∞ x * 1 max(q -1 , (1 -q) -1 ) max(q -1 , (1 -q) -1 ) (4.7)
so we may set, by using (2.2),

ρ γ,d γ + 2 γ -2 max(q -1 , (1 -q) -1 ). Fix 0 < δ 6s < (2 + 8ρ γ,d ) -1 . If x * is s-sparse, so that s = | supp(x * )| nq 2 (1 -q) 2 ρ 2 γ,d log(pρ 2 γ,d /nq 2 (1 -q) 2 )
, then we have the following with probability exceeding 1-C/p for a universal constant C (neglecting constants depending on γ and δ s,0 ):

sd 2 log p n x * 1 s min(q, 1 -q) + x * 2 1 s log p n + s log p nq 2 min(q, 1 -q) 2 (4.8a) k∈supp(x * ) d 2 k log p n x * 1 q + x * 1 s (1 -q) + x * 2 1 s log p n + s log p nq 2 (1 -q) 2 .
(4.8b)

We combine the above bounds values with Theorem 1 and Remark 1 to derive the following for 0 < q ≤ 1/2. (The case where 1/2 < q < 1 can be examined using similar methods.) For

s nq 3 (1 -q) 2 log(p/nq 3 (1 -q) 2 ) and n ρ 2 γ,d log p q 2 (1 -q) 2
the oracle least-squares estimator on the true support of x * satisfies

x * -x LS 2 2 log p n x * 1 q + x * 1 s (1 -q) + x * 2 1 s log p n + s log p nq 2 (1 -q) 2 .
If we use the constant weight d, then for the same range of s and n we have

x * -x LASSO 2 2 log p nq x * 1 s q + x * 2 1 s log p n + s log p nq 4 .
If we use the non-constant weights, then for the same range of s and n we have

x * -x WL 2 2 log p nq x * 1 q + x * 1 s (1 -q) + x * 2 1 s log p n + s log p nq 2 (1 -q) 2 .
Note that the rates for x LS and x WL are equivalent up to the factor q -1 and lower than the rate for x LASSO . This suggests that when q < 1/2, for an appropriate range of s there can be some advantage to using the weighted LASSO in (1.3) over using the typical unweighted LASSO in (1.2). Furthermore, we note that the rates above are similar to the rates derived in a similar setting for estimators based on minimizing a regularized negative log-likelihood. Since the model in [START_REF] Jiang | Minimax Optimal Rates for Poisson Inverse Problems with Physical Constraints[END_REF] considered x * sparse in a basis different from the canonical or sampling basis and only considers q = 1/2, the two results are not perfectly comparable. Specifically, in [START_REF] Jiang | Minimax Optimal Rates for Poisson Inverse Problems with Physical Constraints[END_REF], the sensing matrix was scaled differently to model certain physical constraints 1 ; if we adjust the rates in [START_REF] Jiang | Minimax Optimal Rates for Poisson Inverse Problems with Physical Constraints[END_REF] to account for this different scaling, we find a MSE decay rate of s x * 1 log p/nq for x * 1 sufficiently large, and that for smaller x * 1 is MSE is constant with respect to x * 1 but varies instead with p and n; those rates were validated experimentally in [START_REF] Jiang | Minimax Optimal Rates for Poisson Inverse Problems with Physical Constraints[END_REF]. This shows the similarity between the rates derived with the proposed framework and previous results.

Example: Poisson random convolution in genomics

In this section we describe a specific random convolution model that is a toy model for bivariate Hawkes models or even more precise Poissonian interaction functions [START_REF] Hansen | Lasso and probabilistic inequalities for multivariate point processes[END_REF][START_REF] Sansonnet | Wavelet thresholding estimation in a Poissonian interactions model with application to genomic data[END_REF][START_REF] Sansonnet | A model of Poissonian interactions and detection of dependence[END_REF]. Those point processes models have been used in neuroscience (spike train analysis) to model excitation from on neuron on another one or in genomics to model distance interaction along the DNA between motifs or occurrences of any kind of transcription regulatory elements [START_REF] Gusto | FADO: a statistical method to detect favored or avoided distances between occurrences of motifs using the Hawkes' model[END_REF][START_REF] Carstensen | Multivariate Hawkes process models of the occurrence of regulatory elements and an analysis of the pilot ENCODE regions[END_REF]. All the methods proposed in those articles assume that there is a finite "horizon" after which no interaction is possible (i.e. the support of the interaction function is finite and much smaller that the total length of the data) and in this case the corresponding Gram matrix G can be proved to be invertible. However, and in particular in genomics, it is not at all clear that such an horizon exists. Indeed it usually is assumed that the interaction stops after 10000 bases because the 3D structure of DNA makes the "linear distances" on the DNA not real anymore, but if one would have access to real 3D positions (and there are some data going in this direction), would it be possible to estimate the interaction functions without any assumption on its support? Of course, fully taking into account the 3D structure of the DNA might lead to other kind of difficulties, this is why we want to focus as a preliminary study, on the circle case.

Our toy model can be written in the following form. Let U 1 , . . . , U m be a collection of m i.i.d. realizations of a Uniform random variable on the set {0, . . . , p -1}; these have to be thought of as points equally distributed on a circle. Each U i will give birth independently to some Poisson variables. If x * = (x * 0 , . . . , x * p-1 ) is a vector in R p + , then let us define N i U i +j to be a Poisson variable with law P(x * j ) independent of anything else. The variable N i U i +j represents the number of children that a certain individual (parent) U i has at distance j. Here we understand U i + j in a cyclic way, i.e. this is actually U i + j modulus p. We observe at each position k between 0 and p -1 the total number of children regardless of who their parent might be, i.e. Y k = m i=1 N i k . So the problem can be translated as follows: we observe the U i 's and the Y k 's whose law conditioned on the U i 's is given by

Y k ∼ P( m i=1 x * k-U i ).
So this is a discretized version of the model given in [START_REF] Sansonnet | Wavelet thresholding estimation in a Poissonian interactions model with application to genomic data[END_REF] where the data have been binned and in addition put on a circle (which is also quite consistent with the fact that some bacteria genomes are circular). By adapting the assumptions of [START_REF] Sansonnet | Wavelet thresholding estimation in a Poissonian interactions model with application to genomic data[END_REF][START_REF] Sansonnet | A model of Poissonian interactions and detection of dependence[END_REF][START_REF] Hansen | Lasso and probabilistic inequalities for multivariate point processes[END_REF] to this set-up, the "classical" setting amounts to assume that the coordinates of x * are null after a certain horizon s. So the main question is whether it is possible to estimate x * if one only assumes that s coordinates are non zero but that we do not know where they are (i.e. not necessarily at the beginning of the sequence). The sparsity is a reasonable assumption in genomics for instance because if there is indeed a link between the parents and the children, then the main distances of interaction will correspond to particular chemical reactions going on.

The above model actually amounts to a random convolution, as detailed below. Other authors have studied random convolution, notably [START_REF] Romberg | Compressive sensing by random convolution[END_REF][START_REF] Marcia | Compressive coded aperture superresolution image reconstruction[END_REF][START_REF] Harmany | Spatio-temporal compressed sensing with coded apertures and keyed exposures[END_REF][START_REF] Candes | A probabilistic and RIPless theory of compressed sensing[END_REF], but those analyses do not extend to the problem considered here. For example, Candès and Plan [9, p5] consider random convolutions in which they observe a random subset of elements of the product Ax * . They note that A is an isometry if the Fourier components of any line have coefficients with same magnitude. In our setting the Fourier coefficients of A are random and do not have uniform magnitude, and so the analysis in [START_REF] Candes | A probabilistic and RIPless theory of compressed sensing[END_REF] cannot be directly applied in our setting. In particular, the ratio of p (the number of elements in x * and the number of measurements) to m (the number of uniformly distributed parents ) will play a crucial role in our analysis but is not explored in the existing literature.

Poisson random convolution model

Put another way, we may write Y := (Y 0 , . . . , Y p-1 ) and let A ≡ A(U ) be a p × p circulant matrix satisfying

A = m i=1 A i ,
where

A i := e U i e U i +1 e U i +2 • • • e U i +(p-1) , (5.1)
where the subscripts are understood to be modulus p and e i denotes the i th column of a p × p identity matrix. We introduce the multinomial variable N, defined for all k ∈ {0, . . . , p -1} by

N(k) = card {i : U i = k[p]} . (5.2)
It represents the number of parents at position k on the circle. Note that p-1 u=0 N(u) = m, which will be extensively used in proofs, and

A =       N(0) N(p -1) • • • N(1) N(1) N(0) . . . . . . . . . . . . . . . N(p -1) N(p -1) • • • N(1) N(0)       ; that is, A ,k = N( -k).
Using this notation, we are actually perfectly in the set-up of the present article, that is

Y ∼ P(Ax * ).
Note that if it is a convolution model, it is actually a very particular one. Indeed, A is a square matrix satisfying E(A) = m1 p 1 p and therefore all the eigenvalues of the latter are null except the first one. In this sense it is a very badly ill-posed problem. This can also be viewed by the fact that in expectation, we are convoluting the data by a uniform distribution which is known to be a completely unsolvable problem. Therefore and as for many works on compressed sensing, we rely on the randomness to prove that Assumptions such as RE(s, c 0 ) are satisfied. Note that in some sense we are going further than [START_REF] Hansen | Lasso and probabilistic inequalities for multivariate point processes[END_REF] : in their case the Gram matrix was invertible because one knew where the non zero coefficients were, here Assumption RE(s, c 0 ) proves that we can somehow makes this property uniform whatever the (small) set of non zero coefficients is. Finally, m the number of parents is somehow measuring the number observations, since we somehow get m copies of x * plus some noise. Therefore a large m should improve rates. But if m tends to infinity, one should be close to the convolution by a uniform variable and we should not be able to recover the signal either, whereas if m is much smaller than p, there is "room" to see non overlapping shifted x * and the estimation should be satisfying. This explains why our rates are clearly given by a competition between m and p as detailed hereafter.

Rescaling and recentering

As for the Bernoulli case, we first rescale and recenter the sensing matrix

A := 1 √ m A - √ m -1 p 11 ,
which satisfies that E( G) = E( A A) = I p . Moreover for any k ∈ {0, . . . , p -1}, we can easily define:

Y k := 1 √ m Y k - √ m -1 p Y ,
where Y = 1 m Y 1 . Note that because of the particular form of A, E[ Y | A] = Ax * , (see Lemma D.1 in the Appendix) which explains why in this case the remainder term r k described in Section 3 is actually null.

Assumptions RE and G hold with high probability

The matrix G can be reinterpreted thanks to U-statistics (see Proposition 9 in the appendix) and from this one can deduce the following result. Proposition 4. There exists absolute positive constants κ and C and an event of probability larger than 1 -C/p, on which Assumption G(ξ) is satisfied with

ξ := κ log p √ p + log 2 p m . (5.3)
From Proposition 1 one can easily deduce that for all c 0 , Assumption RE(s, c 0 ) is satisfied as long as

s < (1 + 2c 0 ) -1 ξ -1
on an event of probability larger than 1 -C/p. Note that the rate of ξ is up to logarithmic terms max(p -1/2 , m -1 ) and therefore the sparsity level s can be large if both p and m tends to infinity. If we follow the intuition than m is the number of observations, and if only m tends to infinity, then we are rapidly limited by p meaning that even without the Poisson noise we would not be able to recover the whole signal x * , if it has a very large support with respect to √ p. We also see the reverse: if p grows but m is fixed then m is the limiting factor as usual for a fixed number of observations.

Choice of the weights

As for the Bernoulli case, one can have two choices: either constant weights that are using the very particular shape of A or non-constant weights that follows from Lemma 1.

Constant weights

To define the constant weights, let W := max =0,...,p-1 w( ) with for all = 0, . . . , p -1

w( ) = p-1 u=0 1 m 2 N(u) - m -1 p 2 N(u + )
and let

B = max u∈{0,...,p-1} 1 m N(u) - m -1 p .
Then the constant weights are given by

d := 4W log p Y + 5 log p 3m + log p m + 2B log p 3 (5.4)
and one can prove that they satisfy Assumption Weights(d) with high probability (see Proposition 10). Furthermore, as shown in Proposition 11,

d 2 log(p) 2 p + log(p) 3 m ||x * || 1 + log(p) m .

Non-constant weights

For all k = 0, . . . , p -1, the non-constant weights are given by

d k = 4 log p vk + 5B 2 log p 3 + B 2 log p + 2B log p 3 , (5.5)
with for all k in {0, . . . , p -1},

vk = p =1 N( -k) - m -1 p 2 Y m 2 .
They also satisfy Assumption Weights(d) with high probability (see Proposition 12). Furthermore, Proposition 13 shows that in the range log(p) √ p m p log(p) -1 .

(5.6)

we have

x * k log p m + log p p u =k x * u + log 2 p m 2 d 2 k x * k log p m + log 2 p p u =k x * u + log 4 p m 2 .
Note that the non-constant weights are interesting only if we are able to show that they significantly behave in a non-constant fashion. In Appendix D.3, we upper and lower bound them such that they match (2.8) with high probability in the range shown in (5.6) if

s √ p log(p) 2 .
Note that this condition implies sξ log(p) -1 .

Summary of rate results

For the convolution case, we have shown Assumption RE(s, 0) holds as a consequence of Assumption G(ξ); thus, for s-sparse signals x * , Theorem 3 gives better rates. As an illustration of the performance of the proposed approach for this deconvolution problem, we are able to derive the following bounds, that hold with high probability, as an easy consequence of Theorem 3 combined with the sharp bounds derived in Propositions 11 and 13 (neglecting constants depending on γ and δ s,0 ).

If we use the constant weight d, then as soon as

s min √ p log(p) , m log(p)

Simulations

In this section we simulate the random convolution model described above and the performance of the (unweighted) LASSO and weighted LASSO estimators. More specifically, we simulate two-step estimators in which we first estimate the support using the (weighted) LASSO, and then compute a least-squares estimate on the estimated support. This approach, which has been analyzed in [START_REF] Van De Geer | The adaptive and the thresholded Lasso for potentially misspecified models (and a lower bound for the Lasso)[END_REF], reduces the bias of LASSO estimators. Specifically, we define

S LASSO = i : | x LASSO | > 0 (5.7a)
x LASSO-S =I S LASSO ( A S LASSO ) # y (5.7b)

S WL = i : | x WL | > 0 (5.7c) x WL-S =I S WL ( A S WL ) # y (5.7d)
where the matrices I S LASSO and I S WL are used to fill in zeros at the off-support locations. First we examine the MSE of x LASSO-S and x WL-S as a function of m, the number of uniform random events used to define the convolution operator A. We set p = 5000, and true support set of x * is uniformly randomly selected for each experiment. The value of non-zeros are chosen from a exponential series (with a positive offset), and normalized so that the 1 -norm of x * are kept the same for all experiments. The tuning parameter γ is chosen to minimize the MSE. Each point in the plot is averaged over 400 random realizations. Figure 1 shows the normalized (over the 1 -norm of signal) MSE as a functions of m for s = 5 and s = 50. Our rate shows that for both weighted LASSO and least-squares estimators, the MSE scales like x * 1 log(p) m when m is small and

s x * 1 log 2 (p) p
when m is large relative to p; for the LASSO estimator, the MSE scales like s x * 1 log 3 (p) m when m is small relative to p and s x * 1 log 2 (p) p when m is large relative to p. Thus the weighted LASSO and least-squares estimators should outperform the LASSO estimator by a factor of s for small m.

Next we examine the MSE of x LASSO-S and x WL-S as a function of p, the length of x * . In this experiment, we set s = 5, the true support set of x * is uniformly randomly selected for each experiment. The value of non-zeros are chosen from a exponential series (with a positive offset). For each p, we set m ∝ √ p log(p) (thus m varies from 17 to 46 in this experiment). This specific choice of m is made due to the requirement of m √ p log(p) in our rate results. Note that when m ∝ √ p log(p) and s √ p/ log 2 p, the error rate for the weighted-LASSO is x * 1 / √ p while the error rate for LASSO is x * 1 s log 2 p/ √ p, which is worse by a factor of s log 2 p.

Discussion and Conclusions

The data-dependent weighted LASSO method presented in this paper is a novel approach to sparse inference in the presence of heteroscedastic noise. We show that a simple assumption on the weights leads to estimation errors which are within a constant factor of the errors achievable by an oracle with knowledge of the true signal support. To use this technique, concentration inequalities which account for the noise distribution are used to set data-dependent weights which satisfy the necessary assumptions with high probability.

In contrast to earlier work on sparse Poisson inverse problems [START_REF] Jiang | Minimax Optimal Rates for Poisson Inverse Problems with Physical Constraints[END_REF], the estimator proposed here is computationally tractable. In addition, earlier analyses required ensuring that the product Ax * was bounded away from zero, which limited the applicability of the analysis. Specifically, the random convolution problem described in Section 5 could not be directly analyzed using the techniques described in [START_REF] Jiang | Minimax Optimal Rates for Poisson Inverse Problems with Physical Constraints[END_REF].

Our technique can also yield immediate insight into the role of background contamination. Consider a setting in which we observe

Y ∼ P(Ax * + b) where b ∈ R n
+ is a known (typically constant) background intensity. In imaging, for instance, this would correspond to ambient light or alternative photon sources. While b contributes to the noise variance, it does not provide any information about the unknown signal x * . Since b is known, it can easily be subtracted from the observations in the formation of Y and we can use exactly the estimation framework described above (e.g., the estimator in (1.3)). However, because b impacts the variance of the observations, it will increase the value of v in Lemma 1, leading to a proportional increase in the weights and hence the 2 error decay rates. From here we can see that the error decay rates will increase linearly with the amount of background contamination.

It is worth noting that the core results of Section 2 do not use any probabilist arguments and therefore do not rely at all on Poisson noise assumptions. The Poisson noise model is only used to check that the necessary assumptions are fulfilled with high probability under the assumed observation model. To extend our framework to new observation or noise models, we would simply need to complete the following (interdependent) tasks:

1. Determine a mapping from A to A which ensures A satisfies Assumption RE and/or G.

Determine a mapping from

Y to Y so that E[ A ( Y -Ax * )] = 0.

Use concentration inequalities based on the assumed noise model to derive data-dependent

weights which satisfy Assumption Weights.

Once these tasks are complete, the results of Section 2 can be immediately applied to compute recovery error rates. Therefore, the proposed weighted LASSO framework has potential for a variety of settings and noise distributions.

Before proceeding to recovery bounds, we establish the following oracle inequality.

Theorem A.1. Let γ > 2, and d k > 0, k = 1, . . . , p, such that Assumption Weights({d k } k ) holds. Let ρ = ρ γ,d from (2.2). For any s ∈ {1, . . . , p}, let δ s,2ρ > 0 be a parameter such that Assumption RE(s, 2ρ) holds. Then the weighted LASSO estimate x WL defined in (1.3) satisfies

A x WL -Ax * 2 2 ≤ 8γ 2 inf x:| supp(x)|≤s Ax -Ax * 2 2 + k∈supp(x) d 2 k 1 -δ s,2ρ . (A.2)
Furthermore, if x * is s-sparse, under the same assumptions, (A.2) implies

A x WL -Ax * 2 2 ≤ 8γ 2 1 -δ s,2ρ k∈supp(x * ) d 2 k . (A.3)
Theorem A.1 is proved in the sequel of Appendix A.

Remark A.1. Under the assumptions of Theorem A.1, in the special case where

d := d 1 = d 2 = . . . = d p , (A.2) implies that the LASSO estimate x LASSO defined in (1.2) satisfies A x LASSO -Ax * 2 2 ≤ 8γ 2 inf x:| supp(x)|≤s Ax -Ax * 2 2 + sd 2 1 -δ s,2ρ (A.4)
for any s ∈ {1, . . . , p}. Furthermore, if x * is s-sparse, under the same assumptions,

A x LASSO -Ax * 2 2 ≤ 8γ 2 1 -δ s,2ρ sd 2 . (A.5)
For short, in this section, we denote x instead of x WL . Therefore,

x := argmin x∈R p

C(x).

To prove Theorem 2, we introduce the pseudo-estimate x (S * ) defined by

x (S * ) ∈ argmin

x∈R p :supp(x)⊆S * Y -Ax 2 2 + γ p k=1 d k |x k | . (A.6)
We first state the following technical lemma.

Lemma A.2. Let x ∈ R p . If Assumption Weights({d k } k ) holds, we have (γ -2) k / ∈supp(x) d k | x k -x k | ≤ Ax -Ax * 2 2 + (γ + 2) k∈supp(x) d k | x k -x k |, (A.7) and if γ > 2, then A x -Ax * 2 2 ≤ Ax -Ax * 2 2 + 2γ k∈supp(x) d k | x k -x k |. (A.8)
Similarly for x (S * ) , for any x supported by S * , we have

(γ -2) k / ∈supp(x) d k | x (S * ) k -x k | ≤ Ax -Ax * 2 2 + (γ + 2) k∈supp(x) d k | x (S * ) k -x k |, (A.9)
and if γ > 2, then

A x (S * ) -Ax * 2 2 ≤ Ax -Ax * 2 2 + 2γ k∈supp(x) d k | x (S * ) k -x k |. (A.10)
Proof of Lemma A.2. By the optimality of x according to (1.3), we have for any

x ∈ R p , Y -A x 2 2 + γ p k=1 d k | x k | ≤ Y -Ax 2 2 + γ p k=1 d k |x k |.
We obtain:

A x -Ax * 2 2 + (γ -2) p k=1 d k | x k -x k | (A.11) = A x -Y 2 2 + Y -Ax * 2 2 + 2 A x -Y , Y -Ax * + (γ -2) p k=1 d k | x k -x k | ≤ Y -Ax * 2 2 + 2 A x -Y , Y -Ax * + Y -Ax 2 2 + γ p k=1 d k |x k | -γ p k=1 d k | x k | + (γ -2) p k=1 d k | x k -x k | = Ax -Ax * 2 2 + 2 A x -Ax, Y -Ax * + γ p k=1 d k (|x k | -| x k |) + (γ -2) p k=1 d k | x k -x k | = Ax -Ax * 2 2 + 2 x -x, A ( Y -Ax * ) + γ p k=1 d k (|x k | -| x k |) + (γ -2) p k=1 d k | x k -x k | ≤ Ax -Ax * 2 2 + 2 p k=1 d k | x k -x k | + γ p k=1 d k (|x k | -| x k |) + (γ -2) p k=1 d k | x k -x k | ≤ Ax -Ax * 2 2 + γ p k=1 d k (|x k | -| x k | + |x k -x k |) ≤ Ax -Ax * 2 2 + 2γ k∈supp(x) d k |x k -x k |. (A.12)
Now, note that for any x ∈ R p , (γ -2)

k / ∈supp(x) d k | x k -x k | ≤ A x -Ax * 2 2 + (γ -2) p k=1 d k | x k -x k | -(γ -2) k∈supp(x) d k | x k -x k | ≤ Ax -Ax * 2 2 + 2γ k∈supp(x) d k | x k -x k | -(γ -2) k∈supp(x) d k | x k -x k | ≤ Ax -Ax * 2 2 + (γ + 2) k∈supp(x) d k | x k -x k |,
and we obtain (A.7). For γ ≥ 2 we have

A x -Ax * 2 2 ≤ A x -Ax * 2 2 + (γ -2) p k=1 d k | x k -x k | ≤ Ax -Ax * 2 2 + 2γ k∈supp(x) d k | x k -x k |
by (A.11) yielding (A.8). By using similar arguments, we obtain (A.9) and (A.10) by assuming that x is supported by S * .

Proof of Theorem A.1. Let x ∈ R p such that J = supp(x) satisfies |J| ≤ s. Let ∆ = D( x -x), with D a diagonal matrix and for any k, D kk = d k . Our proof structure is inspired by the proof of Theorem 6.1 of [START_REF] Bickel | Simultaneous analysis of Lasso and Dantzig selector[END_REF]. By using (A.8), we have

A x -Ax * 2 2 ≤ Ax -Ax * 2 2 + 2γ ∆ J 1 . (A.13) If 2γ ∆ J 1 ≤ 2γ γ + 2 Ax -Ax * 2 2 ,
then the proof follows easily. So we assume that

1 γ + 2 Ax -Ax * 2 2 < ∆ J 1 .
By (A.13), we have

A x -Ax * 2 2 ≤ Ax -Ax * 2 2 + 2γ k∈J d 2 k 1/2 ( x -x) J 2
and we have to bound ( x -x) J 2 . Using (A.7),

(γ -2) ∆ J c 1 ≤ Ax -Ax * 2 2 + (γ + 2) ∆ J 1 (A.14) ≤ (2γ + 4) ∆ J 1 . (A.15)
We deduce that

( x -x) J c 1 ≤ 2ρ ( x -x) J 1 .
By Assumption RE, we obtain:

( x -x) J 2 2 ≤ A( x -x) 2 2 1 -δ s,2ρ . (A.16)
Using the triangle inequality and the standard inequality 2ab ≤ a 2 /τ + τ b 2 with 0 < τ < 1, a, b > 0, we obtain

A x -Ax * 2 2 ≤ Ax -Ax * 2 2 + 2γ k∈J d 2 k 1/2 (x -x) J 2 (A.17) ≤ Ax -Ax * 2 2 + 2γ k∈J d 2 k 1 -δ s,2ρ 1/2 A( x -x) 2 (A.18) ≤ Ax -Ax * 2 2 + 2γ k∈J d 2 k 1 -δ s,2ρ 1/2 A( x -x * ) 2 + A(x * -x) 2 (A.19) ≤ Ax -Ax * 2 2 + γ 2 τ (1 -δ s,2ρ ) k∈J d 2 k + τ A( x -x * ) 2 2 + τ A(x * -x) 2 2 ;
(A.20) letting τ = 1/(2γ) gives the result.

A.1 Proof of Theorem 1

In this section we prove the following statement, from which Theorem 1 easily follows:

Theorem A.2. Let s > 0 be an integer and let x * s denote the best s-sparse approximation to x * . Let S * := supp(x * s ). Let γ > 2 and assume that Assumption Weights({d k } k ) is satisfied for some positive weights d k 's. Let ρ γ,d be consequently defined by (2.2). Under Assumption RE(2s, 2ρ γ,d ) with parameter δ 2s,2ρ γ,d , the Weighted LASSO estimator x WL satisfies

x * -x WL 2 ≤ 2 √ 2γ(1 + 2ρ γ,d ) 1 -δ 2s,2ρ γ,d A(x * -x * s ) 2 2 + k∈S * d 2 k 1/2 (A.21) + 3 x * -x * s 1 + 2 (γ -2)d min + 1 (γ + 2)d max A(x * -x * s ) 2 2 (A.22) x * -x WL 1 ≤ 2 √ 2γ(1 + 2ρ γ,d ) 1 -δ 2s,2ρ γ,d A(x * -x * s ) 2 2 + k∈S * d 2 k 1/2 √ s (A.23) + 3 x * -x * s 1 + 2 (γ -2)d min + 1 (γ + 2)d max A(x * -x * s ) 2 2 . (A.24)
Proof of Theorem A.2. For simplicity of notation, we denote ρ γ,d as ρ in the following. Let T 0 be the indices of the s largest magnitude elements of x * and T 1 be the indicies of the s largest magnitude elements of

h := x * -x not in T 0 . Let T 01 = T 0 ∪ T 1 . Lemma A.2 with x = x * T 0 gives (γ -2)d min h T c 0 1 ≤ (γ -2)d min x * T c 0 1 + Ax * T c 0 2 2 + (γ + 2)d max h T 0 1 . If (γ -2)d min x * T c 0 1 + Ax * T c 0 2 2 > (γ + 2)d max h T 0 1 , then h T c 0 1 ≤ 2 x * T c 0 1 + 2 (γ-2)d min Ax * T c 0 2 2
and

h 2 ≤ h 1 = h T c 0 1 + h T 0 1 ≤ 2 + (γ -2)d min (γ + 2)d max x * T c 0 1 + 2 (γ -2)d min + 1 (γ + 2)d max Ax * T c 0 2 2 . (A.25) Otherwise, if (γ -2)d min x * T c 0 1 + Ax * T c 0 2 2 ≤ (γ + 2)d max h T 0 1 , then we have h T c
0 1 ≤ 2ρ h T 0 ; thus we may leverage Assumption RE(2s, 2ρ) (with parameter δ 2s,2ρ ) as follows: Note that

h 1 ≤ h T 0 1 + h T c 0 1 ≤ (1 + 2ρ) h T 0 1 ≤ (1 + 2ρ) √ s h T 0 2 ≤ (1 + 2ρ) √ s 1 -δ 2s,2ρ Ah 2 . (A.26)
Furthermore, by Theorem A.1, we have

Ah 2 2 ≤8γ 2 A(x * -x * s ) 2 2 + k∈T 0 d 2 k 1 -δ 2s,2ρ .
Thus

h 1 ≤ 2 √ 2γ(1 + 2ρ) √ s 1 -δ 2s,2ρ   (1 -δ 2s,2ρ ) A(x * -x * s ) 2 2 + k∈T 0 d 2 k   1/2 . (A.27)
For the 2 recovery error bound, note that the k largest magnitude elements of h

T c 0 satisfy |h T c 0 | (k) ≤ h T c 0 1 /k, yielding h T 01 c 2 2 ≤ h T c 0 2 1 k≥s+1 1 k 2 ≤ 1 s h T c 0 2 1 ≤ 4ρ 2 s h T 0 2 1 ≤ 4ρ 2 h T 0 2 2 ≤ 4ρ 2 h T 01 2 2 . (A.28) Thus, h T 01 c 2 ≤ 2ρ h T 01 2
and

h 2 ≤ h T 01 2 + h T 01 c 2 ≤ (1 + 2ρ) h T 01 2 ≤ 1 + 2ρ 1 -δ 2s,2ρ Ah 2 (A.29) ≤ 2 √ 2γ(1 + 2ρ) 1 -δ 2s,2ρ   (1 -δ 2s,2ρ ) A(x * -x * s ) 2 2 + k∈T 0 d 2 k   1/2 . (A.30)
A.2 Proof of Proposition 1

Let x, J and c 0 be as in the statement of Proposition 1. We denote s = |J|, so we have

|| Ax|| 2 2 ≥ || Ax J || 2 + 2x J Gx J c . But || Ax J || 2 -||x J || 2 2 = x J [ G -I p ]x J . Hence by Assumption G(ξ), ||| Ax J || 2 -||x J || 2 2 | ≤ ξ||x J || 2 1 ≤ ξs||x J || 2 2 .
On the other hand

|2x J Gx J c | ≤ 2 k∈J,k ∈J c |x k G k,k x k | ≤ 2ξ||x J || 1 ||x J c || 1 ≤ 2ξc 0 ||x J || 2 1 ≤ 2ξc 0 s||x J || 2 2 ,
which gives the result.

A.3 Proof of Theorem 2

We first prove the following lemma.

Lemma A.3. Under the conditions of Theorem 2,

| A ( Y -A x (S * ) )| k < γd k 2 ∀k / ∈ S *
where x (S * ) is defined in (A.6).

Proof of Lemma A.3. We have from (A.10) with x = x * ,

A x (S * ) -Ax * 2 2 ≤2γ k∈S * d k | x (S * ) k -x * k | (A.31) ≤2γ k∈S * d 2 k 1/2 k∈S * | x (S * ) k -x * k | 2 1/2 . (A.32) Assumption RE applied to x(S * ) -x * gives k∈S * | x (S * ) k -x * k | 2 ≤ (1 -δ s,0 ) -1 A x (S * ) -Ax * 2 2 . (A.33) Thus, A x (S * ) -Ax * 2 2 ≤ 4γ 2 (1 -δ s,0 ) k∈S * d 2 k .
This implies by (A.33)

x (S * ) -x * 2 2 ≤ 4γ 2 (1 -δ s,0 ) 2 k∈S * d 2 k and x (S * ) -x * 1 ≤ s 1/2 x (S * ) -x * 2 ≤ 2γs 1/2 1 -δ s,0 k∈S * d 2 k 1/2 . Since x * -x (S * ) is supported by S * , | G(x * -x (S * ) )| k = ∈S * G k, (x * -x (S * ) ) . But by Assumption G(ξ), if k = , | G k, | ≤ ξ.
Therefore, for all k / ∈ S * ,

| A ( Ax * -A x (S * ) )| k = | G(x * -x (S * ) )| k ≤ ξ||x * -x (S * ) || 1 ≤ ξ 2γ 1 -δ s,0 s k∈S * d 2 k 1/2 . For all k in {0, . . . , p -1}, | A ( Y -Ax * )| k ≤ d k . Therefore, for k / ∈ S * , | A ( Y -A x (S * ) )| k ≤| A ( Y -Ax * )| k + | A ( Ax * -A x (S * ) )| k ≤d k + ξ 2γ 1 -δ s,0 s k∈S * d 2 k 1/2
. This in turn is bounded above by γd k 2 as soon as

ξ 2γ 1 -δ s,0 s k∈S * d 2 k 1/2 < γ 2 -1 min k ∈S * d k .
Lemma A.4. For all a ∈ R p , the function C satisfies

C( x + a) -C( x) ≥ Aa 2 2 .
where the middle inequality comes from Lemma A.4. We thus have

A x = A x (S * )
and so for all k /

∈ S * | A ( Y -A x (S * ) )| k < γd k 2 (A.42) implies | A ( Y -A x)| k < γd k 2 . (A.43)
We then have that supp( x) ⊂ S * if (2.8) is true.

A.4 Proof of Proposition 2

Proof of Proposition 2. By denoting A S * the matrix of size n × |S * | whose columns are the columns of A corresponding to non-zero elements of x * , we have for any k ∈ S * ,

x LS k = (( A H S * A S * ) -1 A H S * Y ) k = ( G -1 S * A H S * Y ) k ,
where G S * = A H S * A S * . Therefore, by setting x LS k = 0 for k / ∈ S * , we have

x LS -x * 2 2 = G -1 S * A H S * ( Y -Ax * ) 2 2 .
Finally, using Assumption RE, we obtain

x LS -x * 2 2 ≤(1 -δ s,0 ) -2 A H S * ( Y -Ax * ) 2 2 ≤(1 -δ s,0 ) -2 k∈S * d 2 k .
A.5 Proof of Theorem 3

Proof of Theorem 3. We have from Lemma A.2, with x = x * ,

A x -Ax * 2 2 ≤2γ k∈S * d k | x k -x * k | (A.44) ≤2γ k∈S * d 2 k 1/2 k∈S * | x k -x * k | 2 1/2 . (A.45) Since supp( x) ⊂ S * , Assumption RE gives k∈S * | x k -x * k | 2 1/2 ≤ (1 -δ s,0 ) -1/2 A x -Ax * 2 .
Thus,

A x -Ax * 2 2 ≤ 4γ 2 1 -δ s,0 k∈S * d 2 k . This implies x -x * 2 2 ≤ 4γ 2 (1 -δ s,0 ) 2 k∈S * d 2 k and x -x * 1 ≤ s 1/2 x -x * 2 ≤ 2γs 1/2 1 -δ s,0 k∈S * d 2 k 1/2 .
We next obtain the the sup-norm bound. By Lemma A.1, for any k,

| A ( Y -A x)| k ≤ γd k 2 . (A.46)
From here we have B Concentration inequality for data-dependent weights (proof of Lemma 1)

x * -x ∞ = A A -A A + I p (x * -x) ∞ (A.47) ≤ A A(x * -x) ∞ + A A -I p (x * -x) ∞ (A.48) = A ( Y -Ax * ) -A ( Y -A x) ∞ + A A -I p (x * -x) ∞ (A.49) ≤d max (1 + γ/2) + ξ x * -x 1 (A.50) ≤d max (1 + γ/2) + 2ξγs 1/2 1 -δ s,0 k∈S * d 2 k 1/2 (A.51) ≤d max (1 + γ/2) + ( γ 2 -
The proof of (3.2) is really classical and follows the lines of Bernstein inequality. Let Z = R Y and z = R Ax * . Conditioned on the sensing matrix A, the Y 's are independent Poisson variables of mean p k=1 a ,k x * k . Therefore for all λ > 0 (eventually depending only on the sensing matrix A)

E e λ(Z-z) A = p =1 E e λR [Y -p k=1 a ,k x * k ] A = p =1 exp e λR -λR -1 p k=1 a ,k x * k .
If λ < (3/b), then by classical computations (see [START_REF] Massart | Concentration inequalities and model selection[END_REF] for instance), for all ,

e λr -λr -1 ≤ λ 2 r 2 /2 1 -λb/3 . Therefore, if λ < (3/b), E e λ(Z-z) A ≤ exp λ 2 v/2 1 -λb/3 .
Hence by Markov's inequality, for all u > 0

P(Z -z ≥ u) ≤ exp λ 2 v/2 1 -λb/3 -λu .
It remains to optimize in λ and conclude as in Bernstein's inequality (see [START_REF] Massart | Concentration inequalities and model selection[END_REF]). For (3.3) it is sufficient to apply (3.2) to both R and -R. For (3.4) it is sufficient to apply (3.2) to -R 2 and for (3.5), to combine both (3.3) and (3.4).

C Validation of assumptions for Bernoulli sensing of Section 4

In the sequel, the notation represents an absolute constant that may change from line to line.

C.1 Rescaling and recentering

First let us prove that E( G) = I p , with G = A A.

Indeed, the (k, k ) element of G is

Gk,k = n =1 (a ,k -q)(a ,k -q) nq(1 -q) . Hence E( Gk,k ) = 0 if k = k and E( Gk,k ) = 1. Next let Z = A ( Y -Ax * ) and let us prove that E(Z) = 0. Z = 1 nq(1 -q) (A -q1 p×1 1 n×1 ) nY -( p k=1 Y k )1 n×1 n -1 -(A -q1 n×1 1 p×1 )x * = 1 nq(1 -q) n n -1 A Y - p k=1 Y k n -1 A 1 n×1 -A Ax * + +q||x * || 1 A 1 n×1 + q1 p×1 1 n×1 Ax * -q 2 ||x * || 1 1 p×1 1 n×1 1 n×1 =T 1 + T 2 with T 1 = 1 nq(1 -q) n n -1 A - A 1 n×1 1 n×1 n -1 (Y -Ax * )
and

T 2 = 1 nq(1 -q) A Ax * -A 1 n×1 1 n×1 Ax * n -1 + q||x * || 1 A 1 n×1 + q1 p×1 1 n×1 Ax * -q 2 n||x * || 1 1 p×1 . Since E(Y |A) = Ax * , E(T 1 |A) = and therefore E(T 1 ) = 0.
Next the kth element of T 2 only depends on A and satisfies

nq(1 -q)T 2,k = 1 n -1   n =1 p k =1 a ,k a ,k x k - n , =1 p k =1 a ,k a ,k x k   + q n =1 a ,k p k =1 x k + q n =1 p k =1 a ,k x k -q 2 n p k =1 x k = -1 n -1 n =1 = p k =1 (a ,k -q)(a ,k -q)x k .
Hence every element of T 2 is a degenerate U-statistics of order 2 and E(T 2 ) = 0. Note that T 2 can also be seen as

T 2 = Mx * with M k,k = -1 (n -1)nq(1 -q) n =1 = (a ,k -q)(a ,k -q).

C.2 Assumption G holds (proof of Proposition 3)

Proof of Proposition 3. We have for any k, ,

G k = n i=1 (a ik -q)(a i -q) nq(1 -q) .
Therefore, E[ G k ] = 1 k= . We apply Bernstein concentration inequality to

X i = (a ik -q)(a i -q) q(1 -q) ,
which are independent. Since, on the one hand

|X i | ≤ b := max 1 -q q , q 1 -q ,
and on the other hand, by setting

v n = n i=1 E (a ik -q) 2 (a i -q) 2 q 2 (1 -q) 2
we have for k = , v n = n and for k = ,

v n = n i=1 E (a ik -q) 2 (a i -q) 2 q 2 (1 -q) 2 = nE (a 1k -q) 4 q 2 (1 -q) 2 = n (1 -q) 2 q + q 2 1 -q with probability larger than 1 -2p 2 e -θ , |n( G -I p ) k | ≤ 2v n θ + bθ 3 .
So, with probability larger than 1 -2p 2 e -θ ,

|( G -I p ) k | ≤ ξ, with ξ = 2θ n (1 -q) 2 q + q 2 1 -q + θ 3n max 1 -q q , q 1 -q .
The proposition follows from setting θ = 3 log p.

C.3 Proofs for data-dependent weights

Proposition 5. Let W = max u,k=1,...,p w(u, k)

with w(u, k) = 1 n 2 (n -1) 2 q 2 (1 -q) 2 n =1 a ,u na ,k - n =1 a ,k 2 .
Then if nq ≥ 12 max(q, 1 -q) log(p), then there exists absolute constants c, c such that with probability larger than 1 -c /p, the choice

d = 6W log(p) N + log(p) (n -1)q(1 -q) + c 3 log(p) n + 9 max(q 2 , (1 -q) 2 ) n 2 q(1 -q) log(p) 2 N ,
where N is an estimator of ||x * || 1 given by

N = 1 nq -6nq(1 -q) log(p) -max(q, 1 -q) log(p)   3 log(p) 2 + 5 log(p) 2 + n =1 Y   2 .
satisfies Assumption Weights(d).

Proposition 6. There exists some absolute constant κ such that if

nq 2 (1 -q) ≥ κ log(p)
then there exists a positive constant C such that with probability larger than

1 -C/p d log(p)||x * || 1 n min(q, 1 -q) + log(p)||x * || 1 n + log(p) nq(1 -q) .
Proposition 7. With the same notations and assumptions as Proposition 5, there exists absolute constants c, c such that with probability larger than 1 -c /p, the choice (depending on k)

d k = 6 log(p) 3 log(p) 2(n -1) 2 q 2 (1 -q) 2 + 5 log(p) 2(n -1) 2 q 2 (1 -q) 2 + V k Y + log(p) (n -1)q(1 -q) + (C.1) +c 3 log(p) n + 9 max(q 2 , (1 -q) 2 ) n 2 q(1 -q) log(p) 2 N , (C.2)
with the vector V k of size n given by

V k, = na ,k -n =1 a ,k n(n -1)q(1 -q) 2 satisfies Assumption Weights({d k } k ).
Proposition 8. There exists some absolute constant κ such that if

nq 2 (1 -q) ≥ κ log(p)
then there exists a positive C such that with probability larger than 1 -C/p

d k log(p) x * k nq + u =k x * u n(1 -q) + log(p)||x * || 1 n + log(p) nq(1 -q) .
C.3.1 Assumption Weights holds (proof of Propositions 5 and 7)

As shown in Appendix C.1, ( A ( Y -Ax * )) k ≤ T 1,k + T 2,k .
To derive the constant weight of Proposition 5, we use a bound on T 1 ∞ + T 2 ∞ . To derive the non-constant weights of Proposition 7, we use a bound on |T 1,k | + T 2 ∞ . These bounds are derived in this section.

Concentration of T 2 Each element of the matrix M is a degenerate U-statistics of order 2 of the form 2U with U = > g(a ,k , a ,k ) to which one can apply [START_REF] Houdré | Exponential inequalities, with constants, for U-statistics of order two[END_REF]. Let us compute the different quantities involved in this concentration formula.

Since q(1 -q) ≤ (q 2 + (1 -q) 2 )/2 ≤ max(q 2 , (1 -q) 2 ), a deterministic upper bound of g does not depend on k, k and is given by

A M = max(q 2 , (1 -q) 2 ) n(n -1)q(1 -q) .
On the other hand for any a ∈ {0, 1},

E(g 2 (a ,k , a)) = (a -q) 2 n 2 (n -1) 2 q(1 -q) . Therefore C 2 M = 1 2n(n-1)
and

B 2 M = max(q 2 , (1 -q) 2 ) n 2 (n -1)q(1 -q) .
Finally D M should be chosen as an upper bound of

E > g(a ,k , a ,k )c (a ,k )b (a ,k ) , for all choice of functions c , b such that E( n =2 c (a ,k ) 2 ) ≤ 1 and E( n-1 =1 b (a ,k ) 2 ) ≤ 1. But =1 E (a ,k -q)b (a ,k ) ≤ E(((a ,k -q) 2 ) E(b (a ,k ) 2 ) ≤ nq(1 -q).
By doing the same for the terms in a ,k , D M = nq(1-q) n(n-1)q(1-q) = 1 n-1 works. For any θ > 0, the concentration inequality of [START_REF] Houdré | Exponential inequalities, with constants, for U-statistics of order two[END_REF] involves up to absolute multiplicative constants, a term of the form

C M √ θ + D M θ + B M θ 3/2 + A M θ 2 in
which the main terms are D M θ and A M θ 2 by the previous computations. Therefore there exists some absolute constants c 1 and c 2 such that as soon as n ≥ 2, with probability larger than 1 -c 1 p 2 e -θ , for all k, k

|M k,k | ≤ c 2 θ n + max(q 2 , (1 -q) 2 ) n 2 q(1 -q) θ 2 . (C.3)
Therefore on the same event

||T 2 || ∞ ≤ c 2 θ n + max(q 2 , (1 -q) 2 ) n 2 q(1 -q) θ 2 ||x * || 1 . (C.4)
a ,k x * k ≤   θ 2 + 5θ 6 + n =1 Y   2 .
But by using Bernstein's inequality, with probability larger than 1 -2pe -θ , for all k,

| n =1 (a ,k -q)| ≤ C n,θ = 2nq(1 -q)θ + max(q, (1 -q)) θ 3 (C.5)
Hence on this event, (nq

-C n,θ )||x|| 1 ≤ xa .
So the first assumption on the range of (n, q) is to assume that nq > C n,θ , which is implied by nq ≥ 4 max(q, 1 -q)θ (C.6)

In this case, with probability larger than 1 -(2p + 1)e -θ ,

||x|| 1 ≤ Nθ := 1 nq -C n,θ   θ 2 + 5θ 6 + n =1 Y   2 . (C.7)
Hence there exists some absolute constant c 3 such that on an event of probability larger than 1 -c 3 p 2 e -θ ,

||T 2 || ∞ ≤ c 2 θ n + max(q 2 , (1 -q) 2 ) n 2 q(1 -q) θ 2 Nθ . (C.8)
Upper-bound for T 1 The upper bound on T 2 does not depend on k, but it is just a residual term. The upper bound for T 1 gives the main tendency and its behavior may be refined k by k leading to a weight d k that depends on k. Recall that for fixed k, T

1,k = R k (Y -Ax * ) with for all = 1, . . . , n, R k, = na ,k -n =1 a ,k n(n -1)q(1 -q)
. By (3.3) of Lemma 1, on an event of probability larger than 1 -2pe -θ ,

|T 1,k | ≤ 2V k Ax * θ + ||R k || ∞ θ 3 , with V k, = R 2 k, . But since the a ,k have values in {0, 1}, one has that ||R k || ∞ ≤ 1 (n -1)q(1 -q) . Moreover, V k Ax * ≤ W ||x * || 1 , with W = max u,k=1,...,p w(u, k) and w(u, k) = 1 n 2 (n -1) 2 q 2 (1 -q) 2 n =1 a ,u na ,k - n =1 a ,k 2 .
Combined with (C.7), this gives that

||T 1 || ∞ ≤ √ 2W θ N + θ 3(n -1)q(1 -q) (C.9)
This combined with (C.8) and the choice θ = 3 log(p) gives Proposition 5. On the other hand, one could have applied (3.5) of Lemma 1 to obtain that on an event of probability larger than 1-3pe -θ ,

|T 1,k | ≤ θ 2(n -1) 2 q 2 (1 -q) 2 + 5θ 6(n -1) 2 q 2 (1 -q) 2 + V k Y √ 2θ + θ 3(n -1)q(1 -q) .
Once again, this combined with (C.8) and the choice θ = 3 log(p) gives Proposition 7.

C.3.2 Bounds on the w(u, k)'s

First let us remark that if we denote

w 1 (u, k) = 1 (n -1) 2 q 2 (1 -q) 2 n =1 a ,u (a ,k -q) 2 and w 2 (u, k) = 1 n 2 (n -1) 2 q 2 (1 -q) 2 n =1 a ,u n =1 (a ,k -q) 2 ,
Then for all ∈ (0, 1),

(1 -)w 1 (u, k) + (1 - 1 )w 2 (u, k) ≤ w(u, k) ≤ (1 + )w 1 (u, k) + (1 + 1 )w 2 (u, k).
In the sequel we consequently need to find an upper-bound for w 2 (u, k) and a lower and upper bound on w 1 (u, k) to obtain bounds for w(u, k).

Upper bound for w 2 (u, k) By (C.5) and remarking that max(q, 1 -q) ≤ 1 , on an event of probability larger than 1 -2pe -θ ,

w 2 (u, k) ≤ nq + 2nq(1 -q)θ + θ 3 n 2 (n -1) 2 q 2 (1 -q) 2 2nq(1 -q)θ + θ 3 2 ≤ n 2 q 2 (1 -q)θ + nqθ 2 + (nq(1 -q)θ) 3/2 + θ 3 n 4 q 2 (1 -q) 2 ≤ θ n 2 (1 -q) + θ 2 n 3 q(1 -q) 2 + θ 3/2 n 5/2 q 1/2 (1 -q) 1/2 + θ 3 n 4 q 2 (1 -q) 2
If one assumes that nq(1 -q) ≥ θ, (C.10) then the leading term in the previous expansion is the first one and

w 2 (u, k) ≤ θ n 2 (1 -q) (C.11)
Now for the control of w 1 (u, k), if u = k then on can rewrite

w 1 (k, k) = 1 (n -1) 2 q 2 (1 -q) 2 n =1 a ,k (a ,k -q) 2 = 1 (n -1) 2 q 2 (1 -q) 2 n =1 (a 3 ,k -2qa 2 ,k + q 2 a ,k ) = 1 (n -1) 2 q 2 (1 -q) 2 n =1 a ,k (1 -q) 2 = 1 (n -1) 2 q 2 n =1 a ,k
So by (C.5), on the same event as before, because of (C.10)

w 1 (k, k) - n (n -1) 2 q ≤ 2nq(1 -q)θ + θ 3 (n -1) 2 q 2 ≤ (1 -q) 1/2 θ 1/2 n 3/2 q 3/2 . (C.12)
On the other hand, if u = k, let us apply Bernstein inequality to Z u,k = a ,u (a ,k -q) 2 . The expectation of Z u,k is given by

E(Z u,k ) = q 2 (1 -q),
whereas its variance is

Var(Z u,k ) =E([Z u,k ] 2 ) -q 4 (1 -q) 2 =E(a 2 ,u )E([a ,k -q] 4 ) -q 4 (1 -q) 2 =qE(a 4 ,k -4qa 3 ,k + 6q 2 a 2 ,k -4q 3 a ,k + q 4 ) -q 4 (1 -q) 2 =q(q -4q 2 + 6q 3 -3q 4 ) -q 4 (1 -q) 2 =q 2 (1 -q)(1 -3q + 3q 2 ) -q 4 (1 -q) 2 =q 2 (1 -q)(1 -3q + 2q 2 + q 3 ) ≤q 2 (1 -q).
Moreover |Z u,k | is bounded by 1. So Bernstein inequality gives that with probability larger than

1 -2p(p -1)e -θ , n =1 Z u,k -nq 2 (1 -q) ≤ 2nq 2 (1 -q)θ + θ 3 . (C.13)
Hence on the same event, because of (C.10), if we additionally assume that

nq 2 (1 -q) ≥ θ (C.14) w 1 (u, k) - n (n -1) 2 (1 -q) ≤ 2nq 2 (1 -q)θ + θ 3 (n -1) 2 q 2 (1 -q) 2 ≤ θ 1/2 n 3/2 q(1 -q) 3/2 . (C.15)
So finally there is a constant κ( ) such that if

nq 2 (1 -q) ≥ κ( )θ (C.16)
then on this event of probability larger than 1 -p 2 e -θ , (

-) 1 nq ≤ w 1 (k, k) ≤ (1 + ) 1 nq , and if u = k (1 -) 1 n(1 -q) ≤ w 1 (u, k) ≤ (1 + ) 1 n(1 -q) . 1
Hence since (C.11) holds, on the same event,

(

-) 2 1 nq + (1 - 1 ) θ n 2 (1 -q) ≤ w(k, k) ≤ (1 + ) 2 1 nq + (1 + 1 ) θ n 2 (1 -q) . 1
This implies up to the eventual replacement of κ( ) by a bigger constant still depending on that

(1 -) 3 1 nq ≤ w(k, k) ≤ (1 + ) 3 1 nq , (C.17)
and in the same way that for u = k that Then by using (C.5), we get that on an event of probability larger than 1 -pe

(1 -) 3 1 n(1 -q) ≤ w(u, k) ≤ (1 + ) 3 1 n(1 -q) . ( C
-θ n =1 Y ≤ ((nq + C n,θ )||x * || 1 + θ) .
This implies that on the same event

N ≤ nq + C n,θ nq -C n,θ ||x * || 1 + θ nq -C n,θ
.

By eventually increasing κ( ) again, we have that under (C.16)

N ≤ 1 + 1 - ||x * || 1 + θ (1 -)nq .
Hence, combining with (C.7), on an event of probability larger that 1 -pe -θ ,

||x * || 1 ≤ N ≤ 1 + 1 - ||x * || 1 + θ (1 -)nq .
Hence, using again (C.16), with eventually a larger κ and fixing = 1/2 say, gives

W θ||x * || 1 + θ||x * || 1 n + θ nq(1 -q) ≤ d ≤ W θ ||x * || 1 + θ nq + θ||x * || 1 n + θ nq(1 -q)
But by the previous computations, W is of the order of 1 n min(q,1-q) , which gives Proposition 6 with θ = 3 log(p).

C.3.4 Control of the non-constant weights (proof of Proposition 8)

Similarly, applying (3.2) and (3.4) of Lemma 1 to V k Y with V k for all k gives that with probability larger than 1 -pe -θ , for all k V k Ax * ≤ θ 2(n -1) 2 q 2 (1 -q) 2 + 5θ 6(n -1) 2 > q 2 (1 -q) 2 + V k Y 2 ≤

V k Ax * + θ n 2 q 2 (1 -q) 2 .

But V k Ax * = p u=1 w(u, k)x * u which is of the order of

1 nq x * k + 1 n(1 -q) u =k x * u .
This gives Proposition 8 with θ = 3 log(p). The result can be now deduced:

E[ Y |U 1 , . . . , U m ] = 1 √ m Ax * - m - √ m p p =1 x * 1 = 1 √ m A - m - √ m p 11 x * = Ax * . But E   u 1 U i =u - 1 p 1 a=u+d - 1 p 2   = E     1 U i =a-d[p] - 1 p 1 - 1 p - 1 p u =a-d[p] 1 U i =u - 1 p   2   .
Moreover the probability that U i = a -d[p] is 1/p. Therefore, by straightforward computations,

E   u 1 U i =u - 1 p 1 a=u+d - 1 p 2   = 1 p 1 - 1 p 2 + p -1 p 2 2 + 1 - 1 p - 2 p 1 - 1 p + p -2 p 2 2 = 1 p 1 - 1 p 2 + 1 p 2 1 - 1 p = 1 p 1 - 1 p ≤ 1 p .
Therefore, E(g 2 (U i , a)) ≤

|a i (U i )| m j=i+1 E(b j (U j ) 2 ) E(g(U i , U j ) 2 |U j )   ≤ 2 √ p E   m-1 i=1 |a i (U i )| m j=i+1 E(b j (U j ) 2 )   ≤ 2 √ m √ p E m-1 i=1 |a i (U i )| ≤ 2m √ p
and D U = 2m √ p works. Therefore, by Theorem 3.4 of [START_REF] Houdré | Exponential inequalities, with constants, for U-statistics of order two[END_REF], for all θ > 0,

P(U(d) ≥ c(C U √ θ + D U θ + B U θ 3/2 + A U θ 2 )) ≤ 2.77e -θ ,
for c an absolute positive constant given in [START_REF] Houdré | Exponential inequalities, with constants, for U-statistics of order two[END_REF][START_REF] Giné | Exponential and moment inequalities for Ustatistics[END_REF]. A union bound gives the second result.

D.3 Proofs for data-dependent weights

Note that

A ( Y -Ax * ) = A I p √ m - √ m -1 pm 1 p 1 p (Y -Ax * ) = A m - m -1 pm 1 p 1 p (Y -Ax * )
Therefore when applying the methodology of Section 3, we identify the th component of R k as

(R k ) = N( -k) m - m -1 pm .
Thanks to this identification one can prove the following results. The same simplifications lead to the upper bound for w(d).

For the lower bounds, remark that by the right hand side of (D.12), (m-1)p -1 < 1/2. Therefore

2 k λ 2 k

 22 1 and that d k should be of the order of σ k /λ k . Therefore the upper bound (1.5) is then of the order of k∈S * σ

Remark 3 .

 3 Similar results to those in Theorem 3 can be derived for the (unweighted) LASSO estimator by letting d = d 1 = . . . = d p .

Figure 2 :

 2 Figure 2: MSE vs. p with m ∝ √ p log p for the estimators in (1.1) and (5.7).

. 18 )C. 3 . 3

 1833 Control of the constant weights (proof of Proposition 6)Applying (3.2) of Lemma 1 with R = 1 n×1 gives that with probability larger than 1 -e -θ ,

D 5 D. 1

 51 Validation of assumptions for random convolution model of Section Rescaling and recenteringNote that Proposition 9 given in the next section proves in particular that E( G) = I p . By Lemma D.1 below, we obtain in particular that E( A H ( Y -Ax * )) = 0 as expected. Lemma D.1. Conditionally on the U i 's, Y is an unbiased estimate of Ax * : E[ Y |U 1 , . . . , U m ] = Ax * . Proof of Lemma D.1. We have first

Finally 1 i=1E

 1 D U is an upper bound over all functions a i , b j such that m-(a i (U i ) 2 ) ≤ 1 and m j=2 E(b j (U j ) 2 ) ≤ 1 of E   i<j a i (U i )g(U i , U j )b j (U j ) (U i , U j )b j (U j )|U j )

  Similarly, by using (D.4), for d = 0, on Ω N (θ) ∩ Ω U (θ),m 2 w(d) = u N(u) 2 N(u + d)

( 2 u

 2 N(u) -(m -1)p -1 ) 2 ≥ (1 -(m -1)p -1 ) 2 ,for all N(u) ≥ 1 and thereforew(0) ≥ (1 -(m -1)p -1 ) 2 m √ p + θ 2 pm -1 ) = pξ(θ). (D.17)But, by using (D.4), on Ω U (θ), since (m -1)p -1 < 1/3,m 2 w(d) ≥ u N(u) 2 N(u + d)

γd max and we obtain a contradiction.

  Note that the bound in (2.11) is within a constant factor of the "optimal" rate associated with knowledge of the support of x * in Proposition 2, as soon as the d k 's are chosen sharply enough to get |( A ( Y -Ax * )) k | d k whereas we lose at least a factor (1 + ρ γ,d ) by only using Theorem 1, even if we assume that δ 2s,2ρ γ,d δ s,0 . This is just a factor depending on γ if the weights are constant, but this can be much worse if the weights are non-constant and if d max >> d min .

	Remark 7.

  In particular the weighted LASSO rate is clearly am improvement over the classical LASSO and proportional to log(p)||x * || 1

	we can derive the following bounds, namely
		||x * -x WL || 2 2	log(p)||x * || 1 m	+	log(p) 2 s||x * || 1 p	+	s log(p) 4 m 2	.
		m	(i.e. independent of s) as soon as
			s min	p m log(p)	,	m||x * || 1 log(p) 3 .
										2 ,
	we have	||x * -x LASSO || 2 2	s	log(p) 2 p	+	log(p) 3 m	||x * || 1 +	log(p) m	.
	In particular as soon as the signal strength ||x s	√ p log(p) 2

* || 1 is larger than log(p)/m, this scales with ||x * || 1 and up to logarithmic term, the rate is of the order of min(p, m) -1 × s||x * || 1 .

If we use the non-constant weights, in the range (5.6) and under the following constraint on the sparsity level s,

  Concentration around ||x * || 1 Since ||x * || 1 is unknown in the previous inequality, if one wants to upper bound T 2 , we need to estimate it. Applying (3.4) of Lemma 1 with R = 1 n×1 gives that with probability larger than 1 -e -θ ,

	xa =
	,k

  Proposition 10. The constant weights given by (5.4) satisfy Assumption Weights(d) with probability larger than 1 -C/p for some absolute positive constant C. Proposition 11. Under the notations of Proposition 10, there exists positive absolute constants c and C and an event of probability larger than 1 -C/p such that on this event Proposition 12. The non-constant weights given by (5.5) satisfy Assumption Weights(d) with probability larger than 1 -C/p for some absolute positive constant C. Proposition 13. Under the notations of Proposition 10, there exists some absolute constants κ 1 , κ 2 , c 1 , c 2 and C positive such that if p ≥ 5 and ifκ 1 log(p) √ p ≤ m ≤ κ 2 p log(p) -1 , (D.9)there exists an event of probability larger than 1 -C/p such that on this event Thanks to those upper and lower bounds on the d k 's it is easy to see that (2.8) is matched as soon asξ 2 4γ 2 (1 -sξ) 2 s ||x * || 1 log(p) m + s 2 ||x * || 1 log(p)2 Both of them are implied by s √ p log(p) -2 .for K an absolute constant large enough. Moreover, under (D.12), we observe that

										θ √ p	≤	m p	≤ 1/θ ≤ 1.
	This gives
					w(0) ≤	1 m	+		θ p	+	θ 2 m √ p	≤	1 m	+	θ p	,
	which gives the result since (D.12) holds.
				d 2 ≤ c	log(p) 2 p		+	log(p) 3 m	||x * || 1 +	log(p) m	.
	c 1	  x * k log p m	+	log p p	u =k	x * u +	log 2 p m 2	  ≤ d 2 k ≤ c 2	  x * k log p m	+	log 2 p p	u =k	x * u +	log 4 p m 2	  .
									p					+	s 2 log(p) 4 m 2	≤	γ 2	-1	2	||x * || 1	log(p) p	+	log(p) 2 m 2	.
	Since ξ log p √ p under (D.9), which is implied by (5.6), as soon as sξ < 1/2 this is implied by
					log(p) 2 p		s	log(p) m	+ s 2 log(p) 2 p	≤ γ	log(p) p	,
	and					log(p) 2 p	s 2 log(p) 4 m 2	≤ γ	log(p) 2 m 2 .

Specifically, the sensing matrix considered in[START_REF] Jiang | Minimax Optimal Rates for Poisson Inverse Problems with Physical Constraints[END_REF] corresponds to our A/qn and the data acquisition time T in[START_REF] Jiang | Minimax Optimal Rates for Poisson Inverse Problems with Physical Constraints[END_REF] corresponds to our nq x * 1. Thus the rates in[START_REF] Jiang | Minimax Optimal Rates for Poisson Inverse Problems with Physical Constraints[END_REF] were essentially derived for the scaled MSE n

q 2 x * -x 2 2 /T 2 .

Acknowledgments

We gratefully acknowledge the support of AFOSR award 14-AFOSR-1103, NSF award CCF-1418976, the University of Nice Sophia Antipolis Visiting Professor program and ANR 2011 BS01 010 01 projet Calibration. The research of Vincent Rivoirard benefited from the support of the Chaire Economie et Gestion des Nouvelles Données, under the auspices of Institut Louis Bachelier, Havas-Media and Paris-Dauphine.

A Proofs of the LASSO bounds of Section 2

In the sequel, we shall use the following classical lemma.

Proof of Lemma A.4. We use Lemma A.1. For any a ∈ R p ,

with s k = sign( x k ) if x k = 0 and |s k | ≤ 1 otherwise. The last step comes from enumeration of the possible signs of all the terms in (A.36).

Proof of Theorem 2. We follow the approach of the proof of Proposition 2.3 of [START_REF] Bunea | Consistent selection via the Lasso for high dimensional approximating regression models[END_REF]. We denote

We define a cost function associated with the optimization problem in (A.6), where the optimization is unconstrained over all vectors z ∈ R |S * | :

Here A (S * ) corresponds to the submatrix of A such that for any ∈ {1, . . . , s * }, the th column of A (S * ) is the i th column of A. Since 1 -δ s,0 > 0, the minimizer of C (S * ) is unique by Lemma A.4 and Assumption RE. Therefore, if z = argmin z C (S * ) (z), then for any ∈ {1, . . . , s * }, z = x (S * ) i . The first-order optimality condition for C (S * ) (z) implies that for all ∈ {1, . . . , s * },

or, equivalently

Thus, x (S * ) satisfies the first-order optimality condition for C and hence x (S * ) minimizes C(x) over all x ∈ R p . This in turn implies

Assumption G holds (proof of Proposition 4)

For this purpose, let us introduce the following degenerate U-statistics of order two, defined for all k ∈ {0, . . . , p -1} by

Proposition 9. Let p, m > 1 be fixed integers. For any k, ∈ {0, . . . , p -1}, we have:

Furthermore, there exists absolute positive constants κ such that for all real number θ > 1 such that there exists an event Ω U (θ) of probability larger than 1 -5.54 pe -θ and, on this event, for all k ∈ {0, . . . , p -1},

Note that this proves actually that Assumption G(ξ(θ)) is satisfied on the event Ω U (θ). Proposition 4 follows with θ = 2 log p. Proof of Proposition 9.

which leads to

Next note that

For k = , we have

Similarly, for k = , we have

For the second result, one can rewrite U(d) as U(d) = i<j g(U i , U j ), with

Therefore U(d) is a completely degenerate U -statistic of order 2, and one can apply concentration inequalities of [START_REF] Houdré | Exponential inequalities, with constants, for U-statistics of order two[END_REF].

and one can take A U = 6. Moreover, for all a ∈ {0, . . . , p -1},

D.3.1 Assumption Weights holds (proof of Propositions 10 and 12)

Proposition 12 is just the application of (3.5) of Lemma 1 to each of the vectors R k with θ = 2 log(p). For Proposition 10 note that

Hence all the v k 's satisfy that

But one could apply Lemma 1 with R = -1 to obtain that

which is equivalent to

Therefore combining (3.3) of Lemma 1 with R k with (D.10) and (D.11) leads to the desired result, taking θ = 2 log(p).

D.3.2 Bounds on the w( )s

To derive bounds on the w( )s, we need to introduce in addition to Ω U (θ) another event, namely Ω N (θ).

Lemma D.2.

There exists an event Ω N (θ) of probability larger than 1 -2pe -θ such that on Ω N (θ), for all u in {0, . . . , p -1},

This is just a classical consequence of Bernstein's inequality to the m i.i.d. variables 1 U i =u . Thanks to this definition, one can prove the following bounds.

Lemma D.3.

There exists an absolute constant c such that for all θ > 1, on the event Ω N (θ), of probability larger than 1 -pe -θ ,

Proof of Lemma D.3. Recall that W = max w( ) with for fixed

Hence on Ω N (θ)

But 1/(p 2 m) ≤ min(θ/p, θ 2 /m), which gives the result. This bound can be refined for a particular range of values for m.