Charles Dossal
email: charles.dossal@math.u-bordeaux1.fr

Marie-Line Chabanol
email: line.chabanol@math.u-bordeaux1.fr

Gabriel Peyré
email: gabriel.peyre@ceremade.dauphine.fr

Jalal Fadili
email: jalal.fadili@greyc.ensicaen.fr

Sharp Support Recovery from Noisy Random Measurements by ℓ 1 minimization

Keywords: Compressed sensing, ℓ 1 minimization, sparsistency, consistency

In this paper, we investigate the theoretical guarantees of penalized ℓ 1 -minimization (also called Basis Pursuit Denoising or Lasso) in terms of sparsity pattern recovery (support and sign consistency) from noisy measurements with non-necessarily random noise, when the sensing operator belongs to the Gaussian ensemble (i.e. random design matrix with i.i.d. Gaussian entries). More precisely, we derive sharp non-asymptotic bounds on the sparsity level and (minimal) signal-to-noise ratio that ensure support identification for most signals and most Gaussian sensing matrices by solving the Lasso with an appropriately chosen regularization parameter.

Our first purpose is to establish conditions allowing exact sparsity pattern recovery when the signal is strictly sparse. Then, these conditions are extended to cover the compressible or nearly sparse case. In these two results, the role of the minimal signal-to-noise ratio is crucial. Our third main result gets rid of this assumption in the strictly sparse case, but this time, the Lasso allows only partial recovery of the support. We also provide in this case a sharp ℓ 2 -consistency result on the coefficient vector.

The results of the present work have several distinctive features compared to previous ones. One of them is that the leading constants involved in all the bounds are sharp and explicit. This is illustrated by some numerical experiments where it is indeed shown that the sharp sparsity level threshold identified by our theoretical results below which sparsistency of the Lasso solution is guaranteed meets the one empirically observed.

Introduction

Problem setup

The conventional wisdom in digital signal processing is the Shannon sampling theorem valid for bandlimited signals. However, such a sampling scheme excludes many signals of interest that are not necessarily bandlimited but can still be explained either exactly or accurately by a small number of degrees of freedom. Such signals are termed sparse signals.

In fact we distinguish two types of sparsity: strict and weak sparsity (the latter is also termed compressibility). A signal x, considered as a vector in a finite dimensional subspace of R p , is strictly or exactly sparse if all but a few of its entries vanish; i.e., if its support I(x) = supp (x) = {1 ≤ i ≤ p | x[i] = 0} is of cardinality k ≪ p. A k-sparse signal is a signal where exactly k samples have a non-zero value. Signals and images of practical interest may be compressible or weakly sparse in the sense that the sorted magnitudes |x sorted [i]| decay quickly. Thus x can be well-approximated as k-sparse up to an error term (this property will be used when we will tackle compressible signals). If a signal is not sparse in its original domain, it may be sparsified in an appropriate orthobasis Φ (hence the importance of the point of view of computational harmonic analysis and approximation theory). Without loss of generality, we assume throughout that Φ is the standard basis.

The compressed sensing/sampling [START_REF] Candès | Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information[END_REF][START_REF] Candès | Near-optimal signal recovery from random projections: Universal encoding strategies?[END_REF][START_REF] Donoho | Compressed sensing[END_REF] asserts that sparse or compressible signals can be reconstructed with theoretical guarantees from far fewer measurements than the ambient dimension of the signal. Furthermore, the reconstruction is stable if the measurements are corrupted by an additive bounded noise. The encoding (or sampling) step is very fast since it gathers n non-adaptive linear measurements that preserve the structure of the signal x 0 :

y = Ax 0 + w ∈ R n , (1)
where A ∈ R n×p is a rectangular measurement matrix, i.e., n < p, and w accounts for possible noise with bounded ℓ 2 norm. In this work, we do not need w to be random and we consider that A is drawn from the Gaussian matrix ensemble1 , i.e., the entries of A are independent and identically distributed (i.i.d.) N (0, 1/n). The columns of A are denoted a i , for i = 1, • • • , p. In the sequel, the sub-matrix A I is the restriction of A to the columns indexed by I(x). To lighten the notation, the dependence of I on x is dropped and should be understood from the context. The signal is reconstructed from this underdetermined system of linear equations by solving a convex program of the form:

x ∈ argmin x∈R p x 1 such that Ax -y ∈ C , ( 2
)
where C is an appropriate closed convex set, and x q := ( i |x[i]| q ) 1/q , q ≥ 1 is the ℓ qnorm of a vector with the usual adaptation for q = ∞: x ∞ = max i |x[i]|. We also denote x 0 as the ℓ 0 pseudo-norm which counts the number of non-zero entries of x. Obviously, x 0 = |I(x)|. For any vector x, the notation x ∈ R |I(x)| means the restriction of x to its support.

Typically, if C = {0} (no noise), we end up with the so-called Basis Pursuit [START_REF] Chen | Atomic decomposition by basis pursuit[END_REF] problem

min x∈R p x 1 such that y = Ax . (BP)
Taking C as the ℓ 2 ball of radius ǫ, we have a noise-aware variant of BP

min x∈R p x 1 such that Ax -y 2 ≤ ǫ (ℓ 1 -constrained)
where the parameter ǫ > 0 depends on the noise level w 2 . This constrained form can also be shown to be equivalent to the ℓ 1 -penalized optimization problem, which goes by the name of Basis Pursuit DeNoising [START_REF] Chen | Atomic decomposition by basis pursuit[END_REF] or Lasso in the statistics community after [START_REF] Tibshirani | Regression shrinkage and selection via the Lasso[END_REF]:

min x∈R p 1 2 y -Ax 2 2 + γ x 1 , (Lasso)
where γ is the regularization parameter. (ℓ 1 -constrained) and (Lasso) are equivalent in the sense that there is a bijection between γ and ǫ such that both problems share the same set of solutions. However, this bijection is unknown explicitly and depends on y and A, so that in practice, one needs to use different algorithms to solve each problem, and theoretical results are stated using one formulation or the other. In this paper, we focus on the Lasso formulation. It is worth noting that the Dantzig selector [START_REF] Candès | Rejoinder: the Dantzig selector: statistical estimation when p is much larger than n[END_REF][START_REF] Bickel | Simultaneous analysis of lasso and Dantzig selector[END_REF] is also a special instance of (2) when C = {z ∈ R p A T z ∞ ≤ γ}.

The convex problems of the form (ℓ 1 -constrained) and (Lasso) are computationally tractable and many algorithms have been developed to solve them, and we only mention here a few representatives. Homotopy continuation algorithms [START_REF] Osborne | On the lasso and its dual[END_REF][START_REF] Efron | Least angle regression[END_REF][START_REF] Donoho | Fast solution of ℓ 1 -norm minimization problems when the solution may be sparse[END_REF] track the whole regularization path. Many first-order algorithms originating from convex non-smooth optimization theory have been proposed to solve (Lasso). These include one-step iterative thresholding algorithms [START_REF] Figueiredo | An EM Algorithm for Wavelet-Based Image Restoration[END_REF][START_REF] Daubechies | An iterative thresholding algorithm for linear inverse problems with a sparsity constraint[END_REF][START_REF] Bect | A ℓ 1 -unified variational framework for image restoration[END_REF][START_REF] Combettes | Signal recovery by proximal forward-backward splitting[END_REF], or accelerated variants [START_REF] Figueiredo | Gradient projection for sparse reconstruction: Application to compressed sensing and other inverse problems[END_REF][START_REF] Dias | A new twIST: Two-step iterative shrinkage/thresholding algorithms for image restoration[END_REF], multi-step schemes such as [START_REF] Nesterov | Gradient methods for minimizing composite objective function[END_REF] or [START_REF] Beck | A fast iterative shrinkage-thresholding algorithm for linear inverse problems[END_REF]. The Douglas-Rachford algorithm [START_REF] Combettes | A Douglas-Rachford splitting approach to nonsmooth convex variational signal recovery[END_REF][START_REF] Fadili | Monotone operator splitting for fast sparse solutions of inverse problems[END_REF] is a first-order scheme that can be used to solve (ℓ 1 -constrained). A more comprehensive account can be found in [START_REF] Starck | Sparse Signal and Image Processing: Wavelets, Curvelets and Morphological Diversity[END_REF]Chapter 7].

Theoretical performance measures of the Lasso

These last years, we have witnessed a flurry of research activity where efforts have been made to investigate the theoretical guarantees of ℓ 1 minimization by solving the Lasso for sparse recovery from noisy measurements in the underdetermined case n < p. Overall, the derived conditions hinge on strong assumptions on the structure and interaction between the variables in A as indexed by x 0 . An overview of the literature pertaining to our work will be covered in Section 1.3 after notions are introduced so that the discussions are clearer.

Let x 0 be the original vector as defined in (1), f 0 = Ax 0 the noiseless measurements, x(γ) a minimizer of the Lasso problem and f (γ) = Ax(γ).

Consistency. ℓ q -consistency on the signal x means that the ℓ q -error x 0x(γ) q , for typically q = 1, 2 or ∞, between the unknown vector x 0 and a solution x(γ) of either (Lasso) or (ℓ 1 -constrained) comes within a factor of the noise level.

Sparsistency. Sparsity pattern recovery (also dubbed sparsistency for short or variable selection in the statistical language) requires that the indices and signs of the solutions x(γ) are equal to those of x 0 for a well chosen value of γ. Partial support recovery occurs when the recovered support is included (strictly) in that of x 0 with the correct sign pattern.

In general, it is not clear which of these performance measures is better to characterize the Lasso solution. Nevertheless, in the noisy case, consistency does not tell the whole story and there are many applications where bounds on the ℓ q -error are insufficient to characterize the accuracy of the Lasso estimate. In this case, exact or partial recovery of the support, hence of the correct model variables, is the desirable property to have. Among other advantages, this allows for instance to circumvent the bias of the Lasso and thus enhance the estimation of x 0 and Ax 0 using a debiasing procedure: recover the support I by solving the Lasso, followed by least-squares regression on the selected variables (a i ) i∈I ; see e.g. [START_REF] Candès | Rejoinder: the Dantzig selector: statistical estimation when p is much larger than n[END_REF][START_REF] Candès | Near-ideal model selection by ℓ 1 minimization[END_REF]. Our work falls within this scope and focuses on exact and partial support identification for both strictly sparse and compressible signals in the presence of noise on Gaussian random measurements.

Literature overview

The properties of the Lasso have been extensively studied, including consistency and distribution of its estimates. There is of course a huge literature on the subject, and covering it fairly is beyond the scope of this paper. In this section, we restrict our overview to those works pertaining to ours, i.e., sparsity pattern recovery in presence of noise.

Much recent work aims at understanding the Lasso estimates from the point of view of sparsistency. This body of work includes [START_REF] Candès | Near-ideal model selection by ℓ 1 minimization[END_REF][START_REF] Candès | Rejoinder: the Dantzig selector: statistical estimation when p is much larger than n[END_REF][START_REF] Donoho | Stable recovery of sparse overcomplete representations in the presence of noise[END_REF][START_REF] Meinshausen | High-dimensional graphs and variable selection with the lasso[END_REF][START_REF] Greenshtein | Best subset selection, persistence in high-dimensional statistical learning and optimization under ℓ 1 constraint[END_REF][START_REF] Tropp | Just relax: convex programming methods for identifying sparse signals in noise[END_REF][START_REF] Wainwright | Sharp thresholds for high-dimensional and noisy sparsity recovery using ℓ 1 -constrained quadratic programming (lasso)[END_REF][START_REF] Zhao | On model selection consistency of lasso[END_REF][START_REF] Zou | The adaptive lasso and its oracle properties[END_REF]. For the Lasso estimates to be close to the model selection estimates when the data dimensions (n, p) grow, all the aforementioned papers assumed a sparse model and used various conditions that require the irrelevant variables to be not too correlated with the relevant ones.

Mutual coherence-based conditions. Several researchers have studied independently the qualitative performance of the Lasso for either exact or partial sparsity pattern recovery of sufficiently sparse signals under a mutual coherence condition on the measurement matrix A; see for instance [START_REF] Donoho | Stable recovery of sparse overcomplete representations in the presence of noise[END_REF][START_REF] Fuchs | Recovery of exact sparse representations in the presence of bounded noise[END_REF][START_REF] Tropp | Just relax: convex programming methods for identifying sparse signals in noise[END_REF][START_REF] Bunea | Pushing the Limits of Contemporary Statistics: Contributions in Honor of Jayanta K. Ghosh[END_REF] when A is deterministic, and [START_REF] Zhou | Compressed and privacy-sensitive sparse regression[END_REF] when A is Gaussian. However, mutual coherence is known to lead to overly pessimistic sparsity bounds.

Support structure-based conditions. These sufficient recovery conditions were refined by considering not only the cardinality of the support but also its structure, including the signs of the non-zero elements of x 0 . Such criteria use the interactions between the relevant columns of A I = (a i ) i∈I and the irrelevant ones (a i ) i / ∈I . More precisely, we define the following condition developed in [START_REF] Fuchs | On sparse representations in arbitrary redundant bases[END_REF] to analyze the properties of the Lasso. This condition goes by the name of irrepresentable condition in the statistical literature; see e.g. [START_REF] Zhao | On model selection consistency of lasso[END_REF][START_REF] Candès | Near-ideal model selection by ℓ 1 minimization[END_REF][START_REF] Wainwright | Sharp thresholds for high-dimensional and noisy sparsity recovery using ℓ 1 -constrained quadratic programming (lasso)[END_REF][START_REF] Meinshausen | Lasso-type recovery of sparse representations for highdimensional data[END_REF] and [START_REF] Van De Geer | On the conditions used to prove oracle results for the lasso[END_REF] for a detailed review. Definition 1. Let I be the support of x 0 and I c its complement in {1, • • • , p}. The irrepresentable (or Fuchs) condition is fulfilled if

F (x 0 ) := A T I c A I (A T I A I ) -1 sign (x 0 ) ∞ = max i∈I c | a i , d(x 0 ) | < 1, (3)
where d(x 0 ) :

= A I (A T I A I ) -1 sign (x 0 ) . (4)
Condition (3) will also be the soul of our analysis in this paper.

The criterion (3) is closely related to the exact recovery coefficient (ERC) of Tropp [START_REF] Tropp | Just relax: convex programming methods for identifying sparse signals in noise[END_REF]:

ERC(x 0 ) := 1 -max i∈I c (A T I A I ) -1 A T I a i 1 . (5)
In [START_REF] Tropp | Just relax: convex programming methods for identifying sparse signals in noise[END_REF]Corollary 13], it is established that if ERC(x 0 ) > 0, then the support of the Lasso solution with a large enough parameter γ is included in the one of the subset selection (i.e., ℓ 0 -minimization) optimal solution. In [START_REF] Zhao | On model selection consistency of lasso[END_REF], an asymptotic result is reported showing that (3)2 is sufficient for the Lasso to guarantee exact support recovery and sign consistency. It is also shown that (3) is essentially necessary for variable selection. [START_REF] Meinshausen | High-dimensional graphs and variable selection with the lasso[END_REF] develop very similar results and use similar requirements. [START_REF] Bach | Consistency of the group lasso and multiple kernel learning[END_REF] and [START_REF] Nardi | On the asymptotic properties of the group lasso estimator for linear models[END_REF] derive asymptotic conditions for sparsistency of the block Lasso [START_REF] Yuan | Model selection and estimation in regression with grouped variables[END_REF] by extending (3) and (5) to the group setting.

Reference [START_REF] Candès | Near-ideal model selection by ℓ 1 minimization[END_REF] proposes a non-asymptotic analysis with a sufficient condition ensuring exact support and sign pattern recovery of most sufficiently sparse vectors for matrices satisfying a weak coherence condition (of the order (log p) -1 ). Their proof relies upon (3) and a bound on norms of random sub-matrices developed in [START_REF] Tropp | Norms of random submatrices and sparse approximation[END_REF]. The work in [START_REF] Wainwright | Sharp thresholds for high-dimensional and noisy sparsity recovery using ℓ 1 -constrained quadratic programming (lasso)[END_REF] considers a condition of the form (3) to ensure sparsity pattern recovery. The analysis in that paper was conducted for both deterministic and standard Gaussian A in a highdimensional setting where p and the sparsity level grow with the number of measurements n. That author also established that violation of (3) is sufficient for failure of the Lasso in recovering the support set. In [START_REF] Omidiran | High-dimensional subset recovery in noise: Sparsified measurements without loss of statistical efficiency[END_REF], the sufficient bound on the number of measurements established in [START_REF] Wainwright | Sharp thresholds for high-dimensional and noisy sparsity recovery using ℓ 1 -constrained quadratic programming (lasso)[END_REF] for the standard Gaussian dense ensemble was shown to hold for sparse measurement ensembles. The works of [START_REF] Candès | Near-ideal model selection by ℓ 1 minimization[END_REF] and [START_REF] Wainwright | Sharp thresholds for high-dimensional and noisy sparsity recovery using ℓ 1 -constrained quadratic programming (lasso)[END_REF] are certainly the most closely related to ours. We will elaborate more on these connections by highlighting the similarities and differences in Section 2.4.

Variations on the Lasso. Other variations of the Lasso, such as the adaptive Lasso3 [START_REF] Zou | The adaptive lasso and its oracle properties[END_REF][START_REF] Huang | Adaptive lasso for sparse high dimensional regression models[END_REF] or multi-stage variable selection methods [START_REF] Fan | A selective overview of variable selection in high dimensional feature space[END_REF][START_REF] Zhang | Some sharp performance bounds for least squares regression with ℓ l 1 regularization[END_REF][START_REF] Wasserman | High dimensional variable selection[END_REF][START_REF] Van De Geer | Prediction and variable selection with the adaptive lasso[END_REF][START_REF] Meinshausen | Lasso-type recovery of sparse representations for highdimensional data[END_REF]. For an overview of other penalized methods that have been proposed for the purpose of variable selection, see [START_REF] Fan | A selective overview of variable selection in high dimensional feature space[END_REF].

Information-theoretic bounds. A recent line of research has developed information-theoretic sufficient and necessary bounds to characterize fundamental limits on minimal signal-tonoise ratio (SNR), the number of measurements n, and tolerable sparsity level k required for exact or partial support pattern recovery of exactly sparse signals by any algorithm including the optimal exhaustive ℓ 0 decoder [START_REF] Wainwright | Information-theoretic limits on sparsity recovery in the highdimensional and noisy setting[END_REF][START_REF] Fletcher | Necessary and sufficient conditions on sparsity pattern recovery[END_REF][START_REF] Akçakaya | Shannon theoretic limits on noisy compressive sampling[END_REF][START_REF] Reeves | Sampling bounds for sparse support recovery in the presence of noise[END_REF][START_REF] Wang | Information-theoretic limits on sparse support recovery: Dense versus sparse measurements[END_REF][START_REF] Aeron | Information theoretic bounds for compressed sensing[END_REF][START_REF] Saligrama | Thresholded basis pursuit: An lp algorithm for achieving optimal support recovery for sparse and approximately sparse signals from noisy random measurements[END_REF][START_REF] Reeves | Approximate sparsity pattern recovery: Information-theoretic lower bounds[END_REF][START_REF] Hormati | An estimation theoretic approach for sparsity pattern recovery in the noisy setting[END_REF][START_REF] Tune | Number of measurements in sparse signal recovery[END_REF][START_REF] Rad | Sharp sufficient conditions on exact sparsity pattern recovery[END_REF]. In most of these works, the bounds are asymptotic, i.e., they provide asymptotic scaling and typically require that the sparsity level k varies at some rate (linearly or sub-linearly) with the signal dimension p when n grows to infinity. It is worth mentioning that a careful normalization is needed, for instance of the sampling matrix and noise, when comparing these results in the literature.

The paper [START_REF] Wainwright | Information-theoretic limits on sparsity recovery in the highdimensional and noisy setting[END_REF] was the first to consider the information-theoretic limits of exact sparsity recovery from the Gaussian measurement ensemble, explicitly identifying the minimal SNR (or equivalently T = min i∈I(x 0 ) |x 0 [i]|) as a key parameter. This analysis yielded necessary and sufficient conditions on the tuples (n, p, k, T ) for asymptotically reliable sparsity recovery. This complements the analysis of [START_REF] Wainwright | Sharp thresholds for high-dimensional and noisy sparsity recovery using ℓ 1 -constrained quadratic programming (lasso)[END_REF] by showing that in the sub-linear sparsity regime, i.e. k = o(p), the number of measurements required by the Lasso4 n k log(pk) achieves the information-theoretic necessary bound.

Subsequent work of [START_REF] Fletcher | Necessary and sufficient conditions on sparsity pattern recovery[END_REF][START_REF] Akçakaya | Shannon theoretic limits on noisy compressive sampling[END_REF][START_REF] Reeves | Sampling bounds for sparse support recovery in the presence of noise[END_REF][START_REF] Wang | Information-theoretic limits on sparse support recovery: Dense versus sparse measurements[END_REF][START_REF] Aeron | Information theoretic bounds for compressed sensing[END_REF][START_REF] Saligrama | Thresholded basis pursuit: An lp algorithm for achieving optimal support recovery for sparse and approximately sparse signals from noisy random measurements[END_REF][START_REF] Reeves | Approximate sparsity pattern recovery: Information-theoretic lower bounds[END_REF][START_REF] Hormati | An estimation theoretic approach for sparsity pattern recovery in the noisy setting[END_REF][START_REF] Tune | Number of measurements in sparse signal recovery[END_REF][START_REF] Rad | Sharp sufficient conditions on exact sparsity pattern recovery[END_REF] has extended or strengthened this type of analysis to other settings (e.g. partial support recovery, other matrix ensembles, other scaling regimes, compressible case).

Contributions

Most of the results developed in the literature on sparsistency of the Lasso estimate exhibit asymptotic scaling results in terms of the triple (n, p, k), but this does not tell the whole story. One often needs to know explicitly the exact numerical constants involved in the bounds, not only their dependence on key quantities such as the SNR and/or other parameters of the signal x 0 . As a consequence, the majority of sufficient conditions are more conservative than those suggested by empirical evidence.

In this paper, we investigate the theoretical properties of the Lasso estimate in terms of sparsity pattern recovery (support and sign consistency) from noisy measurements -the noise being not necessarily random-when the measurement matrix belongs to the Gaussian ensemble. We provide precise non-asymptotic bounds, including explicit sharp leading numerical constants, on the key quantities that come into play (sparsity level for a given measurement budget, minimal SNR, regularization parameter) to ensure exact or partial sparsity pattern recovery for both strictly sparse and compressible signals. Our results have several distinctive features compared to previous closely-connected works. This will be discussed in further details in Section 2.4. Numerical evidence are reported in Section 6 to confirm the theoretical findings.

Organization of the paper

The rest of the paper is organized as follows. We first state our main results and discuss the connections and novelties with respect to existing work. In Section 3 and 4, we detail the proofs for exact recovery with strictly sparse and compressible signals, before proving the partial support recovery result in Section 5. Numerical experiments are carried out in Section 6. Section 6 includes a final discussion and some concluding remarks.

Main results

Our first result Theorem 1 establishes conditions allowing exact sparsity pattern recovery when the signal is strictly sparse. Then, these conditions are extended to cover the compressible case in Theorem 2. In these two results, the role of the minimal SNR is crucial. Our third main result in Theorem 3 gets rid of this assumption in the strictly sparse case, but this time, the Lasso allows only partial recovery of the support. We also provide in this case a sharp ℓ 2 -consistency result on the Lasso estimate.

The three theorems are stated following the same structure: suppose that (x 0 , w) fulfill some requirements formalized by a set Y, then with overwhelming probability (w.o.p. for short) on the choice of A, the Lasso estimate obeys some property P. It should be noted that these theorems imply in particular that w.o.p. on the choice of A, for most vectors (x 0 , w) ∈ Y, the Lasso estimate satisfies property P, whatever the probability measure used on the set Y.

The proof of Theorem 1 is given in Section 3. We prove its extension to compressible signals as stated in Theorem 2 in Section 4. Both proofs capitalize on an implicit formula of the Lasso solution. The proof of Theorem 3 given in Section 5 is quite different, since no such implicit formula is used directly.

Exact Support Recovery with Strictly Sparse Signals

Theorem 1. Let A ∈ R n×p be a Gaussian matrix, i.e. its entries are i.i.d. β) . Suppose that x 0 ∈ R p obeys

N (0, 1/n), w ∈ R n is such that w 2 ≤ ε, 0 ≤ α, β < 1 and p > e 1 2(1- √
x 0 0 = k ≤ αβn 2 log p (6)
and

min i∈I |x 0 [i]| = T ≥ 5.5ε √ 1 -α 2 log p n . (7)
Solve the Lasso problem from the measurements y = Ax 0 + w. Then with probability P (n, p, α, β) converging to 1 as n goes to infinity, the Lasso solution x(γ) with

γ = ε √ 1 -α 2 log p n ( 8
)
is unique and satisfies supp (x(γ)) = supp (x 0 ) and sign x(γ) = sign (x 0 ) .

The proof (see Section 3) provides an explicit bound for P (n, p, α, β), showing in particular that P (n, p, α, β) is larger than

1 - 1 2 e -0.7 √ log n - 1 2 √ π log p -o 1 log p -o(e -0.7 √ log n ) ,
although this bound on the probability is far from optimal.

In plain words, Theorem 1 asserts that for (α, β) ∈ [0, 1) the support and the sign of most vectors obeying (6) can be recovered using the Lasso if the non-zero coefficients of x 0 are large enough compared to noise. This bound on the sparsity of x 0 turns out to be optimal, since for any c > 1, for most vectors x 0 such that x 0 0 ≥ cn 2 log p , the support cannot be recovered using the Lasso even with no noise. Indeed, [START_REF] Fuchs | On sparse representations in arbitrary redundant bases[END_REF] and [START_REF]A necessary and sufficient condition for exact recovery by ℓ 1 minimization[END_REF] proved that the Lasso solution for any γ shares the same sign and the same support as x 0 when y = Ax 0 if and only if max

j / ∈I | a j , A I (A T I A I ) -1 sign (x 0 ) | ≤ 1 .
Note in passing the difference with the strict inequality in (3). On the other hand, if x 0 0 ≥ cn 2 log p with c > 1, then w.o.p. A I (A T I A I ) -1 sign (x 0 ) 2 2 ≥ Cn 2 log p for some C > 1 and sufficiently large p. As a result,

max j / ∈I | a j , A I (A T I A I ) -1 sign (x 0 ) | ≥ √ C > 1.
This informal optimality discussion is consistent with the information-theoretic bounds of [START_REF] Wainwright | Information-theoretic limits on sparsity recovery in the highdimensional and noisy setting[END_REF], where it was proved that the number of measurements required by the Lasso achieves the (asymptotic) information-theoretic necessary bound that has the scaling (6) when the sparsity regime is sub-linear and T 2 ∼ 1/ x 0 0 .

An important feature of Theorem 1 is that all the constants are made explicit and are governed by the two numerical constants α and β. The role of α is very instructive since when lowering γ by decreasing α, the threshold on the minimal SNR is decreased to allow smaller coefficients to be recovered, but simultaneously the probability of success gets lower and the number of measurements required to recover the k-sparse signal increases. The converse applies when α is increased. On the other hand, increasing β (in an appropriate range; see Section 3.3 for details) allows a higher threshold on the sparsity level, but again at the price of a smaller probability of success.

Support Recovery with Compressible Signals

Theorem 1 can be easily extended to weakly sparse or compressible signals. We consider the best k-term approximation x k of x 0 obtained by keeping only the k largest entries from x 0 and setting the others to zero. Obviously, k = |I(x k )|. This is equivalently defined using a thresholding

x k [i] = x 0 [i] if |x 0 [i]| ≥ T, 0 otherwise. ( 9
)
A signal is generally considered as compressible if the residual x kx 0 is small. For sparsistency to make sense in this compressible case, additional assumptions are required, namely that the largest components x k of the signal are significantly larger than the residual x kx 0 . This is made formal in the following theorem.

Theorem 2. Let A, α, β and p as in Theorem 1. We measure y = Ax 0 + w, and let x k be the best k-term approximation of x 0 where k satisfies (6). We denote

∆ = 2 1 + 2 √ α -3α 2 log p n .
Suppose that

w 2 + 4 x 0 -x k 2 ≤ ε, (10)
T as defined in ( 9) is such that

T ≥ 5.5∆ε (11)
and x 0 -x k ∞ ≤ 4 5 (1 - √ α)∆ε. (12)
Then, with probability P 2 (n, p, α, β) converging to 1 as n goes to infinity, the solution x(γ) of the Lasso from measurements y with

γ = ∆ε (13)
is unique and satisfies supp (x(γ)) = supp x k and sign x(γ) = sign x k .

Again, all the leading constants are explicit. Conditions [START_REF] Figueiredo | An EM Algorithm for Wavelet-Based Image Restoration[END_REF] and [START_REF] Daubechies | An iterative thresholding algorithm for linear inverse problems with a sparsity constraint[END_REF] impose compressibility constraints on the signal, namely that the magnitude of the k largest components of x 0 are well above the average magnitude ε/ √ n of the residual, and that the latter is "flat", since the ratio of its ℓ ∞ and ℓ 2 norms should be small. The proof (see Section 4) provides an explicit bound for P 2 (n, p, α, β), showing that P 2 (n, p, α, β) is greater than

1 - 1 2 e -0.7 √ log n - 1 2 √ π log p -o 1 log p -o(e -0.7 √ log n ) ,
although once again this bound on the probability is far from optimal.

Theorem 2 encompasses the strictly sparse case, Theorem 1, which is easily recovered by letting x 0 = x k . The parameter α plays a similar role in both theorems. Furthermore, in Theorem 2, the Lasso solution becomes more tolerant to compressibility errors x 0 -x k as α decreases. This however comes at the price of a lower probability of success as indicated in our proof.

Partial Support Recovery with Strictly Sparse Signals

In both previous theorems, the assumption on T plays a pivotal role: if T is too small, there is no way to distinguish the small components of x 0 from the noise; see also the discussion and literature review in Section 1.3. Nevertheless, if no assumptions are made on T , one can nevertheless expect to partly recover the support of x 0 . This is formalized in the following result. Theorem 3. Let A, α and β as in Theorem 1. We measure y = Ax 0 + w, where x 0 fulfills (6). Then with probability P 3 (n, p, α, β) converging to 1 as n goes to infinity, the solution x(γ) of the Lasso form measurements y with

γ = ε √ 1 -α 2 log p n
is unique and satisfies supp (x(γ)) ⊂ supp (x 0 ) .

Moreover, the Lasso solution is ℓ 2 -consistent:

x 0 -x(γ) 2 ≤ 2 + α 1 -α ε . (14)
The proof in Section 5 provides an explicit lower bound for P 3 (n, p, α, β), and shows that P 3 (n, p, α, β) is larger than

1 -e - n 1- √ β- √ k n 2 2 - 1 2 √ π log p .
As before, this bound on the probability is not optimal.

If γ is large enough it is clear that supp (x(γ)) ⊂ supp (x 0 ) since for γ ≥ A T y ∞ , x(γ) = 0. Theorem 3 provides a parameter γ proportional to ε that ensures a partial support recovery without any assumption on T . It also gives a sharp upper bound on ℓ 2 -error of the Lasso solution. This result remains valid under the additional hypotheses of Theorem 1 or 2 allowing exact recovery of the support.

Connections to related works

Sparsistency. As we mentioned in Section 1.3, our work is closely related to [START_REF] Candès | Near-ideal model selection by ℓ 1 minimization[END_REF][START_REF] Wainwright | Sharp thresholds for high-dimensional and noisy sparsity recovery using ℓ 1 -constrained quadratic programming (lasso)[END_REF], but is different in many important ways that we summarize as follows.

• Deterministic vs random measurement matrices: the work of [START_REF] Candès | Near-ideal model selection by ℓ 1 minimization[END_REF] considers deterministic matrices satisfying a weak incoherence condition. Our work focuses on the classical Gaussian ensemble.

• Asymptotic vs non-asymptotic analysis: the analysis in [START_REF] Wainwright | Sharp thresholds for high-dimensional and noisy sparsity recovery using ℓ 1 -constrained quadratic programming (lasso)[END_REF] applies to high-dimensional setting where even the sparsity level k grows with the number of measurements n.

As a result, k appears in the statements of the probabilities, which thus requires that k → +∞. This is very different from our setting as well as that of [START_REF] Candès | Near-ideal model selection by ℓ 1 minimization[END_REF] where the probabilities depend solely on the dimensions of A. We believe that this is more natural in many applications.

• Random vs deterministic noise: in both previous works, the noise is stochastic (Gaussian in [START_REF] Candès | Near-ideal model selection by ℓ 1 minimization[END_REF] and sub-Gaussian in [START_REF] Wainwright | Sharp thresholds for high-dimensional and noisy sparsity recovery using ℓ 1 -constrained quadratic programming (lasso)[END_REF]). In our work, we handle any noise with a finite ℓ 2 -norm.

• Leading numerical constants: these are not always explicit and sharp in those works. The constant involved in the sparsity level upper-bound in [START_REF] Candès | Near-ideal model selection by ℓ 1 minimization[END_REF]Theorem 1.3] is not given, whereas [START_REF] Candès | Rejoinder: the Dantzig selector: statistical estimation when p is much larger than n[END_REF] gives an explicit and sharp bound. The bounds ( 7) and ( 8) on T and γ are similar to those given in [START_REF] Candès | Near-ideal model selection by ℓ 1 minimization[END_REF]Theorem 1.3] once specialized for α = 3/4.

In [START_REF] Wainwright | Sharp thresholds for high-dimensional and noisy sparsity recovery using ℓ 1 -constrained quadratic programming (lasso)[END_REF]Theorem 2], the constant appearing in the lower-bound on T is not given, whereas [START_REF] Bickel | Simultaneous analysis of lasso and Dantzig selector[END_REF] provides an explicit expression that is shown to be reasonably good in Section 6.

• Compressible signals: to the best of our knowledge, the compressible case has not been covered in the literature, and Theorem 2 appears then as a distinctively novel result of this paper.

• ℓ 2 -consistency: such a result is not given in those references. A bound on the ℓ 2prediction error on Ax 0 -Ax(γ) is proved in [START_REF] Candès | Near-ideal model selection by ℓ 1 minimization[END_REF]. An ℓ ∞ -consistency is established in [START_REF] Wainwright | Sharp thresholds for high-dimensional and noisy sparsity recovery using ℓ 1 -constrained quadratic programming (lasso)[END_REF], which is an immediate consequence of sparsistency. Our method of proof differs significantly from the one used in [START_REF] Wainwright | Sharp thresholds for high-dimensional and noisy sparsity recovery using ℓ 1 -constrained quadratic programming (lasso)[END_REF], and in particular it naturally leads to the ℓ 2 -consistency result.

• Exact and partial support recovery: in [START_REF] Candès | Near-ideal model selection by ℓ 1 minimization[END_REF] the partial recovery case was not considered. In [START_REF] Wainwright | Sharp thresholds for high-dimensional and noisy sparsity recovery using ℓ 1 -constrained quadratic programming (lasso)[END_REF], exact and partial recovery are somewhat handled simultaneously, while we give two distinct results for each case.

ℓ 2 -consistency. This property of the Lasso estimate has been widely studied by many authors under various sufficient conditions. Theorem 3 may then be compared to this literature, and we here focus on results based on the restricted isometry property (RIP) [START_REF] Candès | Decoding by linear programming[END_REF] and more or less similar variants in the literature; see the discussion in [START_REF] Meinshausen | Lasso-type recovery of sparse representations for highdimensional data[END_REF] and the review in [START_REF] Van De Geer | On the conditions used to prove oracle results for the lasso[END_REF].

The RIP results are uniform and ensure ℓ 2 -stability of the Lasso estimate for all sufficiently sparse vectors from noisy measurements, whereas Theorem 3 guarantees that the Lasso estimate is ℓ 2 -consistent for most sparse vectors and a given matrix. When A is Gaussian, the scaling of the sparsity bound is O(n/ log(p/n)) for RIP-based results which is better than O(n/ log p) in Theorem 3. Note that the scaling O(n) was derived in [START_REF] Donoho | For most large underdetermined systems of linear equations, the minimal ℓ 1 norm near-solution approximates the sparsest near-solution[END_REF] when A belongs to the uniform spherical ensemble to ensure ℓ 2 -stability of the Lasso estimate for most matrices A, although the leading constants are not given explicitly. However, the RIP is a worst-case analysis, and the price is that the leading constants in the sufficient sparsity bounds are overly small. In contrast, the leading numerical constants in our sparsity and ℓ 2 -consistency upper-bounds are explicit and solely controlled by (α, β) ∈ [0, 1) 2 . For instance, it can be verified from our proof that the value of the sparsity upper-bound we provide is actually larger than the bounds obtained from the RIP for p up to e 100 . Finally, the RIP is a deterministic property that turns out to be satisfied by many ensembles of random matrices other than the Gaussian. Our Theorem 3 could presumably be extended to sub-Gaussian matrices (e.g. using [61, Corollary V.2.1]), but this needs further investigation that we leave for a future work.

Proof of Support Identification of Exactly Sparse Signals

This section gives the proof of Theorem 1. Recall that x is the restriction of x to its support I(x), and A I the corresponding sub-matrix. We also denote the Moore-Penrose pseudo-inverse of A I as

A + I = (A T I A I ) -1 A T I .

Optimality Conditions for Penalized Minimization

From classical convex analysis, the first order optimality conditions show that a vector x ⋆ is a solution of the Lasso if and only if

A T I (y -Ax ⋆ ) = γsign x ⋆ ∀j / ∈ I, | a j , y -Ax ⋆ | ≤ γ, (15)
where

I = I(x ⋆ ).
Hence if the goal pursued is to ensure that I(x ⋆ ) = I(x 0 ) = I and sign (x ⋆ ) = sign (x 0 ), the only candidate solution of the Lasso is

x ⋆ = x 0 -γ(A T I A I ) -1 sign (x 0 ) + A + I w. (16)
Consequently, a vector x ⋆ is a solution of the Lasso if and only the two following conditions are met :

sign (x 0 ) = sign (x ⋆ ) (C 1 ) ∀j / ∈ I(x 0 ), | a j , γd(x 0 ) + P V I ⊥ (w) | ≤ γ (C 2 )
where V I = Span(A I ), P V I ⊥ is the orthogonal projection on the subspace orthogonal to V I , and d(x 0 ) is defined in (4). Sections 3.2 and 3.3 show that under the hypotheses of Theorem 1, conditions (C 1 ) and (C 2 ) are in force with probability converging to 1 as n goes to infinity. This will thus conclude the proof of Theorem 1.

Condition (C 1 )

To ensure that sign (x 0 ) = sign (x ⋆ ), it is sufficient that

γ(A T I A I ) -1 sign (x 0 ) + A + I w ∞ ≤ T . (17)
We prove that this is indeed the case w.o.p. .

Lemma 4, whose proof is given in Appendix

A.3, shows that γ = ε √ 1-α 2 log p n ≤ T 5.5 implies γ (A T I A I ) -1 sign (x 0 ) ∞ ≤ T (1 + 4 √ α) 5.5
with probability greater than 1kp -1.28 -2e

-nα(0.75 √ 2-1) 2 4 log p .
To prove (17), we will now bound A + I w ∞ . To this end, we split it as follows

A + I w ∞ = D 1 × D 2 × D 3 × w 2 ,
where

D 1 = A + I w ∞ A + I w 2 , D 2 = A + I w 2 A T I w 2 , D 3 = A T I w 2 w 2 .
Bounding D 1 . As A and w are independent, Lemma 5, proved in Appendix A.4, shows that the distribution of A + I w is invariant under orthogonal transforms on R k . Therefore the random variable A + I w A + I w 2 is uniformly distributed on the unit ℓ 2 sphere of R k .

Using the concentration Lemma 7, detailed in Appendix B, with ǫ = 8 log n log k k 2 1 4 , it follows that

P D 1 ≤ 2 k (2 log n log k) 1 4 ≥ 1 -4ke - √ 2 log n log k ≥ 1 -max 4n -1 3 , 8e - √ 2 log(2n) . ( 18
)
One can notice that D 1 ≤ 1 actually gives a better bound if k is small compared to n. Moreover the bound on the probability is 1 -4n -1 3 for k big.

Bounding D 2 . D 2 is bounded by the maximum of the eigenvalue of (A T I A I ) -1 . Indeed, owing to Lemma 3 with t = 1 -k n -2 -1 8 , we arrive at

P D 2 ≤ 2 1 4 ≥ 1 -e -n 2 1-2 -1 8 - 1 √ 2 log p 2 . ( 19
)
Bounding D 3 . Let's write

D 2 3 = 1 w 2 2 i∈I | a i , w | 2 .
Since each a i , w is a zero-mean Gaussian variable with variance

w 2 2
n , the variable

n A T I w 2 2 w 2 2 ,
follows a χ 2 distribution with k degrees of freedom. Therefore, in virtue of the concentration Lemma 8, stated in Appendix B, applied with

1 + δ = 2 log n log k
we obtain

P D 2 3 ≤ 2k √ log n n √ log k ≥ 1 - 1 √ 2πk e -k log n log k -1 2 -log 2 2 -1 4 log log n log k ≥ 1 - 1 2 e -0.7 √ log n
This last bound may be pessimistic; when k is large this probability is actually much bigger. This shows that w.o.p. ,

D 3 ≤ 2k n log n log k 1 4 . ( 20
)
Putting ( 18), ( 19) and ( 20), we conclude that

A + I w ∞ ≤ 2ε 2 log n n , (21)
with probability greater than

1- 1 2 e -0.7 √ log n -e -n 2 1-2 -1 8 - 1 √ 2 log p 2 -max 4n -1 3 , 8e - √ 2 log(2n) -kp -1.28 -2e
nα(0.75 √ 2-1) 2 4 log p which converges to 1 as n → +∞.

In turn, the bound ( 21) becomes, under assumption (7) on T , [START_REF] Tibshirani | Regression shrinkage and selection via the Lasso[END_REF] .

A + I w ∞ ≤ 2T √ 1 -α 5.
This shows that condition (C 1 ) is in force with probability converging to 1 as n → +∞.

Condition (C 2 )

Let's introduce the following vector

u = γd(x 0 ) + P V I ⊥ (w), (22)
which depends on both x 0 and w.

Clearly, to comply with (C 2 ), we need to bound ( a j , u ) j / ∈I w.o.p. . We will start by bounding u 2 .

Bounding u 2 . As d(x 0 ) ∈ V I , the Pythagorean theorem yields

u 2 2 = γ 2 d(x 0 ) 2 2 + P V I ⊥ (w) 2 2 . ( 23
)
Let S = sign (x 0 ). Then

nk d(x 0 ) 2 2 = n S 2 2 S T (A T I A I ) -1 S .
Since x 0 and A are independent, Lemma 6, stated in Appendix B, shows that nk d(x 0 ) 2 2 is χ 2 -distributed with nk + 1 degrees of freedom. Thanks to Lemma 9, see Appendix B, it follows that for all δ > 0,

P nk n -k + 1 < (1 -δ) d(x 0 ) 2 2 ≤ e (n-k+1) log(1-δ) 2
.

Since k n ≤ 1 2 log p , we obtain for p ≥ e 1 2δ ,

P k < d(x 0 ) 2 2 (1 -δ) 2 ≤ e n log(1-δ)(4-δ) 8
.

Choosing δ such that (1δ) > √ β, we have

P d(x 0 ) 2 2 ≤ k β ≥ 1 -e n(3- √ β) log β 16
.

This shows that d(x 0 ) 2 2 ≤ k β with probability converging to 1 as n → +∞.

It is worthy to mention that the condition p > e β) actually guarantees the existence of a suitable δ.

As P V I ⊥ is an orthogonal projector, we have

P V I ⊥ (w) 2 ≤ w 2 ≤ ε.
Together with [START_REF] Donoho | Stable recovery of sparse overcomplete representations in the presence of noise[END_REF], this shows that

P u 2 2 ≤ γ 2 k β + ε 2 ≥ 1 -e n(3- √ β) log β 16 . ( 24
)
Bounding max j / ∈I | u, a j |. For a fixed u, the random variables ( a j , u ) j / ∈I are zero-mean Gaussian variables with variance u 2 2 n . Using the bound [START_REF] Meinshausen | High-dimensional graphs and variable selection with the lasso[END_REF], traditional arguments from the concentration of the maximum of Gaussian variables tell us that

max j / ∈I | a j , u | ≤ 2 log p n γ 2 k β + ε 2 (25)
with a probability larger than

1 -e n(3- √ β) log β 16 - 1 2 √ π log p .
In turn, this implies that condition (C 2 ) is in force w.o.p. if

2 log p n γ 2 k β + ε 2 ≤ γ. This holds if ε √ 1 -α 2 log p n ≤ γ.
This concludes the proof of Theorem 1, and shows that overall

P (n, p, α, β) ≥ 1 - 1 2 e -0.7 √ log n -e -n 2 1-2 -1 8 - 1 √ 2 log p 2 -max 4n -1 3 , 8e - √ 2 log(2n) -kp -1.28 -2e -nα(0.75 √ 2-1) 2 4 log p -e n(3- √ β) log β 16 - 1 2 √ π log p .

Proof of Support Identification of Compressible Signals

To prove this theorem, we capitalize on the results of Section 3.1 by noting that y = Ax k + A(x 0x k ) + w := Ax k + Ah + w, and replacing x 0 by x k and w by w 2 = Ah + w. With these change of variables, it is then sufficient to check conditions (C 1 ) and (C 2 ) with the notable difference that the noise w 2 is not independent of A anymore. More precisely, w 2 is independent of (a i ) i∈I but not of (a j ) j / ∈I .

Condition (C 1 ). Since this condition only depends on A I , it is verified with probability converging to 1 as n → +∞, as in the proof of Theorem 1, provided that T ≥ 5.5γ and

w 2 2 ≤ T 5.5 (1-α)n
2 log p . The first condition is a direct consequence of assumptions ( 11) and ( 13). Moreover, w 2 2 ≤ w 2 + Ah 2 , where Ah is a zero-mean Gaussian vector, whose entries are independent with variance

h 2 2 n . Therefore n Ah 2 2 h 2 2
has a χ 2 distribution with n degrees of freedom. We then derive from the concentration Lemma 8 that

P ( Ah 2 ≤ 2 h 2 ) ≥ 1 - 1 3 √ 2πn e -0.8n .
Under assumptions ( 10)-( 11), the last inequality implies that

w 2 2 ≤ w 2 + 2 h 2 ≤ ε ≤ T 5.5∆ ≤ T 5.5 (1 -α)n 2 log p
with probability that tends to 1 as n → +∞. Condition (C 1 ) is thus satisfied with a probability larger than

1 - 1 2 e -0.7 √ log n -e -n 2 1-2 -1 8 - 1 √ 2 log p 2 -max 4n -1 3 , 8e - √ 2 log(2n) -kp -1.28 -2e -nα(0.75 √ 2-1) 2 4 log p - 1 3 √ 2πn e -0.8n .
Condition (C 2 ). For any j / ∈ I, define the vector v j = w 2h[j]a j . In particular, v j is independent of a j . Condition (C 2 ) now reads:

∀j / ∈ I, | a j , γd(x k ) + P V I ⊥ (v j ) + h[j]P V I ⊥ (a j ) | ≤ γ ,
where the vector d(x k ) is defined replacing x 0 by x k in (4).

Similarly to [START_REF] Meinshausen | High-dimensional graphs and variable selection with the lasso[END_REF], it can be shown that w.o.p.

γd(x k ) + P V I ⊥ (v j ) 2 2 ≤ γ 2 k β + v j 2 2 .
On the other hand, v j 2 ≤ w 2 2 + h ∞ a j 2 , and n a j 2 2 is χ 2 -distributed with n degrees of freedom. Applying Lemma 8 to bound a j 2 by 2 for all j and using similar arguments to those leading to [START_REF] Greenshtein | Best subset selection, persistence in high-dimensional statistical learning and optimization under ℓ 1 constraint[END_REF], we get

max j / ∈I | a j , γd(x k ) + P V I ⊥ (v j ) | ≤ 2 log p n γ 2 k β + ( w 2 + 4 h 2 ) 2
with probability larger than 1 -p+1 3 √ 2πn e -0.8n -1 2 √ π log p , converging to 1 as n → +∞. It then follows from assumptions [START_REF] Donoho | Fast solution of ℓ 1 -norm minimization problems when the solution may be sparse[END_REF] and (13) that w.o.p.

max j / ∈I | a j , γd(x k ) + P V I ⊥ (v j ) | ≤ γ 2 (1 + √ α) . (26)
As an orthogonal projector is a self-adjoint idempotent operator, we have for all j ≤ p,

|h[j] a j , P V I ⊥ (a j ) | ≤ h ∞ P V I ⊥ (a j ) 2 2
,

where

P V I ⊥ (a j ) 2 2
is the squared ℓ 2 -norm of the projection of a Gaussian vector on the sub-

space V I ⊥ whose dimension is n -k. As V I ⊥ is independent of a j , for j / ∈ I, n P V I ⊥ (a j ) 2 2
follows a χ 2 distribution with nk degrees of freedom. Using Lemma 8 together with assumptions ( 12)-( 13), the following bound holds w.o.p.

max j / ∈j |h[j] a j , P V I ⊥ (a j ) | ≤ 2.5 h ∞ ≤ γ 2 (1 - √ α) (27)
In summary, ( 26) and [START_REF] Wainwright | Sharp thresholds for high-dimensional and noisy sparsity recovery using ℓ 1 -constrained quadratic programming (lasso)[END_REF] show that (C 2 ) is fulfilled with probability larger than

1 -1 3 √ 2πn e -0.8n -1 3 √ 2πn e -0.3n - 1 √ 2π(n-k)
e -0.009n .

Proof of Partial Support Recovery

To prove the first part of Theorem 3, we need to show that with w.o.p. , the extension x 1 (γ) on R p of the solution of

min x∈R |I| 1 2 y 1 -A I x 2 2 + γ x 1 (28)
with y 1 = P A I (y), is the solution of the Lasso. By definition, the support J of this extension is included in I.

Proving this assertion amounts to showing that x 1 (γ) fulfills the necessary and sufficient optimality conditions

A T J (y -Ax 1 (γ)) = γsign x 1 (γ) , ∀l / ∈ J, | a l , y -Ax 1 (γ) | ≤ γ. (29)
Since

y 1 = P A I (y) and J ⊂ I, A T J (y -Ax 1 (γ)) = A T J (y 1 -Ax 1 (γ)
). In addition, as x 1 (γ) is the extension of the solution of ( 28), the optimality conditions associated to (28) yield

A T J (y -Ax 1 (γ)) = γsign x 1 (γ) , ∀l ∈ (I ∩ J c ), | a l , y -Ax 1 (γ) | ≤ γ.
To complete the proof, it remains now to show that w.o.p.

∀l / ∈ I, | a l , y -Ax 1 (γ) | ≤ γ. (30)
As in the proofs of Theorems 1 and 2, to bound these scalar products, the key argument is the independence between the vectors (a l ) l / ∈I and the residual vector y -Ax 1 (γ).

We first need the following intermediate lemma.

Lemma 1. Let A ∈ R n×k such that (A T A) is invertible. Take x(γ) as a solution of the Lasso from observations y ∈ R n . The mapping f : R

+ * → R + , γ → f (γ) = y-Ax(γ) 2 γ
is well-defined and non-increasing.

Proof: The authors in [START_REF] Osborne | On the lasso and its dual[END_REF] and [START_REF]A necessary and sufficient condition for exact recovery by ℓ 1 minimization[END_REF] independently proved that under the assumptions of the lemma:

• the solution x(γ) of the Lasso is unique;

• there is a finite increasing sequence (γ t ) t≤K with γ 0 = 0 and γ K = A T y ∞ such that for all t < K, the sign and the support of x(γ) are constant on each interval (γ t , γ t+1 ).

• x(γ) is a continuous function of γ.

Moreover x(γ) with support J satisfies

x(γ) = A + J y -γ(A T J A J ) -1 sign x(γ) , (31)
which implies that

r(γ) := y -Ax(γ) = P A ⊥ J (y) -γA J (A T J A J ) -1 sign x(γ) .
Therefore, on each interval (γ t , γ t+1 ), r(γ) is an affine function of γ which can be written

r(γ) = z -γv,
where z := P A ⊥ J (y) and v := A J (A T J A J ) -1 sign x(γ) . As v ∈ V J and z ∈ V ⊥ J , the Pythagorean theorem allows to write for γ ∈ (γ t , γ t+1 ) that

r(γ) 2 2 γ 2 = z 2 2 γ 2 + v 2 2 . (32)
We then deduce that f (γ) =

r(γ) 2 γ
is a non-increasing function of γ on each interval (γ t , γ t+1 ). By continuity of f , it follows that f is non-increasing on R + * .

Remark 1. If (A T

I A I ) is not invertible, the Lasso may have several solutions. Nevertheless r(γ) is always uniquely defined and the lemma should also apply.

From Lemma 1, we deduce that

y 1 -Ax 1 (γ) 2 γ
is a non-increasing function of γ. Because y 1 ∈ V I and A I has full column-rank, we also have

lim γ→0 x 1 (γ) = x 1 ,
where on I, the entries of x 1 are those of the unique vector of R |I| such that A I x = y 1 . Therefore,

x

1 [i] = x 0 [i] + (A + I w)[i], for i ∈ I . (33)
Since A I is Gaussian and independent from x 0 and w, the support of x 1 is almost surely equal to I. Hence there exists γ 1 > 0 such that if γ < γ 1 , the support and the sign of x 1 (γ) are equal to those of x 1 . More precisely, if γ < γ 1 , x 1 (γ) satisfies

x 1 (γ) = x 1γ(A T I A I ) -1 sign (x 1 ) and r(γ) := y 1 -Ax 1 (γ) = γA I (A T I A I ) -1 sign (x 1 ) .

It then follows that for γ ∈ (0, γ 1 ),

y 1 -Ax 1 (γ) 2 γ = A I (A T I A I ) -1 sign (x 1 ) 2 . Now, since A I (A T I A I ) -1 sign (x 1 ) 2 2 = (A T I A I ) -1 sign (x 1 )
, sign (x 1 ) , we deduce that for all γ > 0,

y 1 -Ax 1 (γ) 2 γ ≤ |I|ρ((A T I A I ) -1 ),
where ρ((A T I A I ) -1 ) is the spectral radius of (A T I A I ) -1 . Using Lemma 3 with β < 1 -k n 2 then leads to

P y 1 -Ax 1 (γ) 2 γ ≤ k β ≥ 1 -e - n 1- √ β- √ k n 2 2 . ( 34
)
By the Pythagorean theorem and the fact that

P V I ⊥ w 2 ≤ ε, we have y -Ax 1 (γ) 2 2 = y -y 1 2 2 + y 1 -Ax 1 (γ) 2 2 = P V I ⊥ w 2 + y 1 -Ax 1 (γ) 2 2 ≤ ε 2 + y 1 -Ax 1 (γ) 2 2 .
With similar arguments as those leading to [START_REF] Greenshtein | Best subset selection, persistence in high-dimensional statistical learning and optimization under ℓ 1 constraint[END_REF], it can then be deduced that

max l / ∈I | a l , y -Ax 1 (γ) | ≤ 2 log p n ε 2 + γ 2 k β . ( 35
)
with probability larger than 1e -

n 1- √ β- √ k n 2 2 - 1 2 √ π log p , If k ≤ αβn 2 log p and γ ≥ ε √ 1-α 2 log p n , then 2 log p ε 2 + γ 2 k β n
≤ γ, and therefore inequality (30) is satisfied w.o.p. . This ends the proof of the first part of the theorem.

Let's now turn to the proof of [START_REF] Combettes | Signal recovery by proximal forward-backward splitting[END_REF]. To prove this inequality we notice that for large γ, the Lasso solution x(γ) is also the extension of the solution of (28) w.o.p. and we use the Lipschitz property of the mapping γ → x 1 (γ).

Indeed, by the triangle inequality,

x 0 -x 1 (γ) 2 ≤ x 0 -x 1 2 + x 1 -x 1 (γ) 2 . (36)
Recalling from (33) that x 0x 1 = A + I w, it follows that

x 0 -x 1 2 ≤ ε ρ((A T I A I ) -1 ),
which, using again Lemma 3, leads to the bound

x 0 -x 1 2 ≤ 2ε
with probability larger than 1e

-n 2 0.5-k n 2 .
For all γ > 0, x 1 (γ) obeys [START_REF] Bunea | Pushing the Limits of Contemporary Statistics: Contributions in Honor of Jayanta K. Ghosh[END_REF], and since lim γ→0 x 1 (γ) = x 1 , we get that

x 1 -x 1 (γ) 2 ≤ γ max J⊂I,S∈{-1,1} |J | (A T J A J ) -1 S 2 . ( 37
)
For all J ⊂ I, the inclusion principe tells us that ρ((A T J A J ) -1 ) ≤ ρ((A T I A I ) -1 ). Furthermore, for all S ∈ {-1, 1} |J| , S 2 ≤ √ k. Using Lemma 3 once again implies that

P x 1 -x 1 (γ) 2 ≤ γ k β ≥ 1 -e -n 2 1- √ β-k n 2 . If γ = ε √ 1-α 2 log p n
and k ≤ αβn 2 log p , then w.o.p.

x 1 -x 1 (γ) 2 ≤ ε α 1 -α .
This concludes the proof.

Numerical Illustrations

This section aims at providing empirical support of the sharpness of our bounds by assessing experimentally the quality of the constants involved in Theorem 1. More specifically, we perform a probabilistic analysis of support and sign recovery, to show that the bounds ( 6), ( 8) and ( 7) are quite tight 5 .

In all the numerical tests, we use problems of size (n, p) = (8000, 32000) and (n, p) = (3000, 36000), corresponding to moderate and high redundancies. These are realistic highdimensional settings in agreement with signal and image processing applications. We perform a randomized analysis, where the probability of exact recovery of supports and signs (sparsistency) are computed by Monte-Carlo sampling with respect to a probability distribution on the measurement matrix, k-sparse signals and on the noise w. As detailed in Section 1.1, the matrix A is drawn from the Gaussian ensemble. We assume that the non-zero entries x[i] for i ∈ I(x) of a vector x ∈ R p are independent realizations of a Bernoulli variable taking equiprobable values {+T, -T }. We also assume that the noise w is drawn from the uniform distribution on the sphere {w ∈ R n \ w = ε}. Since only the SNR matters in the bounds, we fix ε = 1 and only vary the value of T . (n, p) = (8000, 32000) (n, p) = (3000, 36000) Challenging the sparsity bound (6). We first evaluate, for α = 0.8, and for a varying value of k, the probability of sparsistency given that

T = 5.5ε √ 1 -α 2 log p n and γ = T 5.5 (38)
which are values in accordance with the bounds ( 7) and [START_REF] Osborne | On the lasso and its dual[END_REF].

In order to compute numerically this probability, for each k, we generate 1000 sparse signals x 0 with x 0 0 = k, and check whether conditions (C 1 ) and (C 2 ) defined in Section 3.1 are satisfied. Figure 1 shows how this probability decays when k increases. The vertical lines correspond to the critical sparsity thresholds

k β = αβn 2 log p (39)
as identified by the bound [START_REF] Candès | Rejoinder: the Dantzig selector: statistical estimation when p is much larger than n[END_REF]. The estimated probability exhibits a typical phase transition that is located precisely around the critical value k β for β close to one. This shows that our bound is quite sharp. We also display the same probability curve for other, less conservative, values of γ ∈ {T /4, T /2}, which improves slightly the probability with respect to γ = T /5.5.

Challenging the regularization parameter value (8). We evaluate, for (α, β) = (0.8, 0.8), the probability of sparsistency using a value of γ different from

γ 0 = ε √ 1 -α 2 log p n (40)
given in ( 8), for which Theorem 1 is valid. We use the critical sparsity level k = k β defined in [START_REF] Tropp | Norms of random submatrices and sparse approximation[END_REF]. To study only the influence of γ, we use a SNR that is infinite, meaning that ε is negligible in comparison with T . This implies in particular that in this regime, only condition (C 1 ) has to be checked to estimate the probability of sparsistency.

Figure 2 shows the increase in this probability as the ratio γ/γ 0 increases. This makes sense because the signal is large with respect to the noise so that a large threshold should be preferred. One can see that at the critical value γ = γ 0 suggested by Theorem 1, this probability is close to 1. This again confirms that the value (8) of γ is quite sharp. Challenging the signal-to-noise ratio [START_REF] Bickel | Simultaneous analysis of lasso and Dantzig selector[END_REF]. Lastly, we estimate, for (α, β) = (0.8, 0.8), the minimal signal level T that is required to ensure the inclusion of the support, meaning that I(x(γ)) ⊂ I(x 0 ). We use the critical sparsity k = k β and γ = γ 0 , with k β and γ 0 as defined respetively in [START_REF] Tropp | Norms of random submatrices and sparse approximation[END_REF] and [START_REF] Omidiran | High-dimensional subset recovery in noise: Sparsified measurements without loss of statistical efficiency[END_REF]. Since we are only interested in support inclusion, it is only needed to check condition (C 2 ).

The bound in [START_REF] Bickel | Simultaneous analysis of lasso and Dantzig selector[END_REF] suggests that T ≥ 5.5γ 0 is enough. Figure 3 however shows that this bound is pessimistic, and that T ≥ 2γ 0 appears to be enough to guarantee the support inclusion with high probability. A few reasons may explain this sub-optimality.

• There is no guarantee that the concentration lemmas we use are optimal.

• The limit ratio T ε relies mainly on Lemma 4 and especially on the bound 1 + 4 √ b in it. This bound can be improved by at least three ways.

-Using the same proof, the bound can be slightly enhanced by decaying the probability of success.

-The result in the lemma is non-asymptotic. The bound and the probability were computed to be available for all α ≤ 1, β ≤ 1 and for all p ≥ 1212. With the values used in the numerical experiments, and decaying a bit the probability of success, the bound can turn into 1 + 2.7 √ b, yielding a better bound T ≥ 4.37γ 0 .

-In the proof of Lemma 4, the inequality B i 2 ≤ ρ(B), is used, where ρ(B) is the spectral radius of B. This bound is available for any matrix, but one might perhaps do better by exploiting Gaussiannity of the measurement matrix.

Conclusion

This paper has presented a novel analysis of the sparsistency of the Lasso from noisy Gaussian measurements. We derived sharp bounds on the sparsity of the signal to guarantee sparsistency with high probability. This result is extended to handle compressible signals and to establish sharp ℓ 2 -consistency. A distinctive feature of our analysis is that it provides explicit constants for the three key parameters of the problem: the sparsity of the signal, the minimal signal-to-noise ratio and the Lasso regularization parameter. Numerical results support the claim that these constants are either sharp or at least reasonably well behaved.

A. Properties of Wishart Matrices

A.1. Signs of non-diagonal entries of an inverse Wishart matrix Lemma 2. If B ∈ R k×k is the inverse of a Wishart matrix, then for all i ≤ k, the variables (sign (B i,j ) , j = i) form a Rademacher sequence, that is they are independent and uniformly distributed on {-1, 1}. Moreover this sequence is independent of B i,i , and of (|B i,j |) j =i .

Proof:

If B = (B i,j ) i≤k,j≤k ∈ R k×k is the inverse of a Wishart matrix, then B = (A T A) -1 where A ∈ M n,k (R) is a Gaussian matrix. Let E ∈ M k,k (R) be diagonal such that for all 1 ≤ i ≤ k, |E i,i | = 1. Then (AE) T AE = EA T AE, hence

Figure 1 :

 1 Figure 1: Probability of sparsistency as a function of k and α = 0.8. The vertical lines corresponds to our sparsistency bound k β , from left to right, for β = 0.7, 0.8, 0.9, 1.

  p) = (8000, 32000) (n, p) = (3000, 36000)

Figure 2 :

 2 Figure 2: Probability of support recovery for large T as a function of γ/γ0 for k = k β and (α, β) = (0.8, 0.8).

  p) = (8000, 32000) (n, p) = (3000, 36000)

Figure 3 :

 3 Figure 3: Probability of support inclusion as a function of T /γ0 for k = k β and (α, β) = (0.8, 0.8).

. 2 5 b.-.Remark 2 .Lemma 5 .

 2525 max ((C T C) -1 ) ≥ 1min ((C T C) -1 ) ≤ 1 + 0It finally follows that with probability larger than 1 -2e -nb(0.75 √2-1) 2 ) 4 log p , ρ(B) ≤ max (1 + 0.75 b log p ) -2 -1 , (1 -0.75 b log p ) -2 -1 .In particular, taking log(p) ≃ 7.07 leads to ρ(B) ≤ 2.log p with probability greater than 1 -2e -nb(0.75 √ 2-1) 2 4 log p . Using this bound in (41) with t = 1.6 log(p) yieldsP BS ∞ ≥ 4 √ b ≤ P BS ∞ ≥ t Bi 2 and ρ(B) ≤ 2.5 b log p + P ρ(B) ≥ 2.5 b log p ≤ kp -1.28 + 2e -nb(0.75 √ If we set log(p) b ≥ 7.08, the following holds,P (C T C) -1 S ∞ ≤ 1 + 4 √ b ≥ 1kp -1.28 -2e It is worth noting that if log p b ≥ 16.2 as in the numerical experiments (b = 0.64, p = 32000), one can adapt this proof and, by loosing a bit on the probability (i.e. applying the concentration lemmas with smaller values of t), one can get(C T C) -1 S ∞ ≤ 1 If C ∈ R n×kis a Gaussian matrix, and w ∈ R n is independent of C, the law of C + w is invariant under orthogonal transforms on R k .Proof: If C ∈ R n×k is a Gaussian matrix, then for any orthogonal matrix U ∈ R k×k , D = CU and C have the same distribution. The law of D + w and C + w are thus the same. Since for all w, one has D + w = U -1 C + w, the law of U -1 C + w is the same as that of C + w.

In a statistical linear regression setting, we would speak of a random Gaussian design.

In fact, a slightly stronger assumption requiring that all elements in (3) are uniformly bounded away from 1.

The adaptive Lasso as seen in the statistical literature turns out to be a two-step procedure, where the second step is to solve a reweighted ℓ1 norm problem, with weights given by the Lasso estimate in the first step. In fact, this is a special case of the iteratively reweighted ℓ1-minimization[START_REF] Candes | Enhancing sparsity by reweighted L1 minimization[END_REF].

The shorthand notation f g means that g = O(f ).

The Matlab code to reproduce the figures are freely available for download from http://www. ceremade.dauphine.fr/~peyre/codes/.

 [START_REF] Candès | Rejoinder: the Dantzig selector: statistical estimation when p is much larger than n[END_REF]This work is supported by ANR grant NatImages ANR-08-EMER-009.

((AE) T (AE)) -1 = E(A T A) -1 E. Therefore the entries of C = ((AE) T AE) -1 are C i,j = E i,i E j,j B i,j for 1 ≤ i, j ≤ k. But A and AE have the same law, hence B and C also have the same law. Hence for all (ǫ j ) j≤k,j =i ∈ {-1, 1} k-1 , the laws of (B i,1 , . . . , B i,k ) and (ǫ 1 B i,1 , . . . , B i,i , . . . , ǫ k B i,k ) are the same. This implies that the variables (sign (B i,j ) , j = i) form a Rademacher sequence, and this sequence is independent of B i,i , and of (|B i,j |) j =i .

A.2. Extreme eigenvalues of a Wishart matrix

The proof of the following lemma can be found in [62, page 42].

Lemma 3. If A ∈ R n×k is a Gaussian matrix whose coefficients are centered of variance 1 n , then the maximal and minimal eigenvalues of the Wishart matrix B = A T A satisfy for all t > 0

Proof: We use the following splitting

This shows that

One can then observe that (BS)[i] =

j≤k |B i,j |S[j]sign (B i,j ); one has B i,i > 0, and according to Lemma 2, for given i, the variables sign (B i,j ) j =i form a Rademacher sequence (this means that they are independent and uniformly distributed on {-1, 1}), and this sequence is independent of B i,i and of (|B i,j |) j =i . Hence one can apply Hoeffding's Lemma 10 (multiplying the line by an independent variable uniform on {-1, 1} to take care of the fact that sign (B i,i ) is not uniformly distributed), thus getting for any i ≤ k and any t > 0,

Now, for all i ≤ k, B

A.5. Distribution of a quadratic form

The following lemma is a consequence of [63, Theorem 3.2.12]. Lemma 6. If B is a Wishart matrix as described in Lemma 3, then for all X ∈ R k independent of B, the random variable

B. Concentration inequalities

The following lemma is well known; a proof can be found in [START_REF] Matousek | Lectures on discrete geometry[END_REF].

Lemma 7. Let µ k denote the uniform probability on the unit sphere S k-1 in R k , and let

The following lemma is due to Cai et Silverman, see [START_REF] Cai | Incorporating information on neighboring coefficients into wavelet estimation[END_REF].

Lemma 8. If X follows a χ 2 distribution with k degrees of freedom, then for all δ > 0,

The following lemma is due to Hoeffding, see [START_REF] Hoeffding | Probability inequalities for sums of bounded random variables[END_REF].

Lemma 9. If X follows a χ 2 distribution with k degrees of freedom, then for all δ > 0, P (X < (1δ)k) ≤ e k log(1-δ) 2

The following lemma can be obtained by applying the Chernoff-Hoeffding inequality.

Lemma 10. If (ε i ) i≤k is a Rademacher sequence, then for all a = (a i ) i≤k ∈ R k and for all t > 0,


R Wan

M Pouragha

F Nicot

A CRITICAL PLANE APPROACH TO ANISOTROPIC STRENGTH OF ROCKS

INTRODUCTION

Geomaterials such as soils and rocks exhibit anisotropic behavior (strength) as a result of their microstructure such as particle arrangement, micro cracks, and bedding (weakness) planes, among others. During the past several years, a plethora of approaches to derive yield or failure criteria have been proposed in order to address material strength anisotropy. For instance, [START_REF] Mehdi | The Mathematical Theory of Plasticity[END_REF] presented a failure criterion for metals based on a quadratic function of stresses expressed in axes of anisotropy, which was later extended to rocks by [START_REF] Pariseau | Plasticity theory for anisotropic rocks and soils[END_REF]. Other treatments are based on the critical plane concept whereby a potential failure plane is searched such that certain failure conditions based on anisotropy are met; see [START_REF] Jaeger | Shear failure of anisotropic rocks[END_REF][START_REF] Mclamore | The mechanical behavior of anisotropic sedimentary rocks[END_REF]. Unlike the latter, there are also other criteria that are purely empirical in nature such as in [START_REF] Ramamurthy | A strength criterion for anisotropic rocks in[END_REF] and Garagon (2010) with fitting parameters that often do not have any physical meaning.

In more modern incarnations of the critical plane approach, [START_REF] Pietruszczak | Formulation of failure criteria for anisotropic frictional materials[END_REF] apply directional strength variation with relative orientation of stress and anisotropy axes to work out an anisotropic failure criterion involving fabric tensors. In this paper, we follow the same above-mentioned approach except that we limit our study to a small amount of model

ABSTRACT:

The paper is concerned with the derivation of failure criteria for anisotropic materials through a simple extension of the Mohr Coulomb failure criterion and embracing the critical plane concept. We revisit the classic problem of determining the macroscopic strength of a rock specimen with an initial structural anisotropy in relation to the directions of externally applied principal stresses. Macroscopic friction angle and cohesion, as two main elements of material strength, are essentially made to be direction dependent following a distribution that depends on only 3 additional parameters describing: (1) the ratio of the maximum to minimum strength, (2) a shape parameter for the transition rate from maximum to minimum values, and (3) the non-coaxiality between principal stress and strength directions. The search for the critical plane is interpreted graphically showing the existence of multiple solutions and the switching of resulting modes for the same externally applied stress. One of the essential benefits of the proposed model is the capture of material characteristics such as failure plane orientation and macroscopic strength over a large range of stress conditions using only a few parameters that have physical meaning and which can be easily determined experimentally. This is demonstrated through various examples involving experimental results. Finally, a micromechanical model and the developed critical plane model are juxtaposed to show the same trend in results.

parameters through a simple extension of Mohr-Coulomb failure criterion with direction dependent strength. Attention is focused on the physical interpretation of failure modes in the anisotropic cases as to whether failure occurs near a plane of weakness (anisotropy) or elsewhere. Two sets of available experimental data have been used to verify the proposed model. The proposed failure criterion can be easily implemented into constitutive models to provide more accurate predictions on the behaviour of sedimentary rocks in stability problems.

Finally, the validity of strength distribution concept has been examined through a microscale model in which the strength in a particular orientation has been related to the density of contacts between particles along the same direction. It has been shown that if the density of contacts is made to vary with the same proposed macro-scale distribution function, the results will exhibit acceptable consistency.

BASICS OF THE MODEL

The present work considers the simple 2-D case where failure is governed by Mohr-Coulomb theory with both friction (ϕ ) and cohesion ( c ) as material strengths defined through a failure function (criterion), i.e. tan 0

f n F c τ σ ϕ = - -= (1)
in which τ and n σ are the shear stress and the normal stress acting on a given plane as a result of applied external principal stresses ( 1 σ and 3 σ ) such as in a biaxial test. In the anisotropic case, for every plane oriented at an angle θ with the direction 3 σ and corresponding strength parameters k θ and c θ , the failure function is

1 1 1 3 1 3 2 2 1 1 3 2 0 ( ) ( )cos2 = ( )sin 2 f n n F k c θ θ τ σ σ σ σ σ σ θ τ σ σ θ = - -= = + + - - (2)
Against the above backdrop, k θ and c θ are deemed to follow a certain distribution in space according to the following trigonometric functions:

2 0 sin 2( ) tan 1 cos 2( ) 1 cos 2( ) k k θ θ ωλ θ β ϕ ω θ β λ θ β ⎡ ⎤ - = = + -+ ⎢ ⎥ + - ⎣ ⎦ (3a) 2 0 sin 2( ) tan 1 cos 2( ) 1 cos 2( ) c c c c c c θ θ ω λ θ β ϕ ω θ β λ θ β ⎡ ⎤ - = = + -+ ⎢ ⎥ + - ⎣ ⎦ (3b)
in which β represents the angle between the major strength orientation and the direction of the minor principal stress, 3 σ ; ω and c ω are anisotropy ratios of maximum to minimum friction and cohesion respectively; λ and c λ are shape factors controlling the transition rate from maximum to minimum friction and cohesion respectively; and 0 k and 0 c refer to the mean friction and cohesion respectively. Such strength distribution could be experimentally determined in a direct shear box test in which the imposed failure plane is varied and the corresponding strength subsequently measured. . For λ equal to 0.999 approaching 1, the distribution here shows a sharp drop in strength for a particular orientation (here 120 θ = °), whereas for other directions the strength is essentially the same. Such a distribution mimics a plane of weakness which was first addressed by [START_REF] Jaeger | Shear failure of anisotropic rocks[END_REF], but in a more primitive manner. By contrast, for smaller values of λ, the spatial strength distribution becomes smoother and resembles the failure criterion proposed by [START_REF] Mclamore | The mechanical behavior of anisotropic sedimentary rocks[END_REF] where failure parameters were empirically related to the angle β , the principal strength direction, using experimental data from a biaxial test. It is worth mentioning that results of such tests require careful interpretation in order to construct the spatial strength distribution. The failure analysis of the prototype problem referring to a sample subjected to principal stresses 1 σ and 3 σ entails finding the orientation, f θ , of the critical (failure) plane for which the failure criterion f F (Eqs. 2&3) is satisfied with the smallest external stress ratio 1 3 ( / ). σ σ Since the failure criterion and local stresses ( , n τ σ ) are both direction dependent as described by ( ) f F θ and ( ) S θ respectively, the above-mentioned failure condition is met whenever ( )/ 0.

f d F S dθ - =
In other words, we find the plane θ for which the failure criterion is optimized under externally applied biaxial stresses, i.e. the conditional derivative ( | )/ 0

f d F S dθ = .
As such, failure is not necessarily interpreted as a tangency condition between the Mohr circle and the failure criterion in the traditional ( vs. ) τ σ space where the spatial direction θ does appear explicitly. Therefore, we propose a new graphical representation of the search for failure in the anisotropic case.

Polar representation of failure

Let us consider a non cohesive material ( 0 c = ) for simplicity to illustrate a polar representation of failure. Rearranging Eq. ( 2), we get ( )

1 3 1 1 sin 2 ; / cos 2 R n R k R θ θ τ θ σ σ σ θ + - ⎛ ⎞ = = = ⎜ ⎟ + ⎝ ⎠ (4)
such that the search for the critical failure plane simply reduces to finding when the stress ratio ( / ) n τ σ coincides with the strength k θ in a polar plot. ) where two mathematically possible solutions occur as plausible failure plane orientations. These are not conjugate solutions as in the isotropic case, given that they occur at distinct externally applied stress levels. Here, the solution with the smaller stress ratio is chosen, this being first encountered during loading history. It turns out that the chosen solution refers to a failure plane whose orientation f θ gives a negative shear stress whereby / 2 f π θ π < < . o . This kink corresponds to a sharp discontinuity in computed failure plane orientation, indicating a switching of failure mode from failure occurring near a plane of weakness to failure within the intact material. This is also immediately seen in Fig. 6d where two equally possible failure plane orientations occur as the stress ratio rosette tangents the strength envelope at two locations: one near the direction of minimum strength (weakness plane) and the other in a direction of much higher strength (intact material). In general, as β increases from zero, the direction of minimum strength tends toward the location of maximum stress ratio rosette (Figs. 6a,b), which accordingly causes the failure stress ratio to decrease until it reaches a minimum value at which the failure plane and the direction of minimum strength are coaxial. This is occurs at 34.4 Further exploration of the model indicates that the transition rate with respect to β from failure near the weakness plane to one in the intact material is controlled by λ which describes both the curvature and shape of the strength distribution. Indeed, experimental data (e.g. [START_REF] Liao | Triaxial residual strength of an anisotropric rock[END_REF] show that there may not always be a switching of failure modes as captured remarkably by the model for small values of λ , see Fig. 7. Also, note that as λ approaches 1, the switching of modes becomes evident as characterized by a 'shoulder' where the strength reverts to its intact value.

β = o in

NUMERICAL RESULTS

The proposed model has been calibrated for two sets of experimental results available for two different sedimentary rocks, i.e. Martinsburg slate [START_REF] Donath | Experimental study of shear failure in anisotropic rocks[END_REF] and argillite [START_REF] Liao | Triaxial residual strength of an anisotropric rock[END_REF]. The model parameters have been determined following a systematic procedure in which salient points in the experimental curves are examined. As previously discussed, the minimum macroscopic (sample) strength occurs at a characteristic β whereby failure occurs along the direction of lowest strength; hence the minimum friction angle can be deduced. The evolution of the above-mentioned minimum strength with confining stress in turn allows us to calculate the minimum cohesion.

Furthermore, if there is a 'shoulder' which refers to strength in the intact material, the maximum friction angle and cohesion can be easily determined. If there is no apparent 'shoulder', then the maximum friction and cohesion are found following an iterative process whereby deviations between experimental data and numerical simulations are minimized at 90

β °=
. Finally, λ is found by calibrating experimental data with simulations at 0 β = . It is interesting to note that the effect of λ on the macroscopic strength is quite pronounced at 0 β = as shown in Fig. 7. This value of λ then enters into a recursive calculation to reach a better estimation of maximum friction and cohesion in the case there is no 'shoulder'. Model parameters for chosen sets of data are presented in Table 1. The overall predictions as seen in Figure 8 for the two data sets are indeed very good considering that the calibration of the model was performed using only characteristics points of the experimental results. There are two aspects that need to be considered during the simulations: one refers to the capture of confining stress effect and the other is the characteristic trend of the variation of macroscopic strength as a function of β for a particular confining stress. Both aspects have been successfully fulfilled since different strength characteristics related to the type of rock have been correctly captured. However, in Fig. 8a, the model over-predicts the strength for a confining pressure of 200 MPa. This is because a linear Mohr-Coulomb failure criterion was used which is not able to capture the decrease in strength (friction) at such a high confining pressure.

DISCUSSION AND CONCLUSION

The modeling approach followed in this work hinges on the idea of introducing directionally dependent strength parameters (friction angle and cohesion) into Mohr-Coulomb failure criterion to capture the anisotropic strength of structured materials. While this approach is at the macroscopic level, the counterpart reasoning at the microscopic level is one which introduces the notion of particle contact density varying along directions in space with yet a unique strength parameter (friction) at the particle level. This has been worked out by Nicot [START_REF] Nicot | The H-microdirectional model: accounting for a mesoscopic scale[END_REF] in his micro-directional model which considers particle contact density at the meso-level to enrich the micro level kinematics. As such, it is the multiplicity of micro/meso interactions described by simple physics that gives way to complex macro properties such as anisotropy in macroscopic strength as those discussed in this paper.

The duality between the two approaches can be verified in Fig. 9 where the two models are juxtaposed for qualitative comparison only. In the micro-directional model, the same macroscopic distribution as that introduced to describe the friction angle (Eq. 3a) was used to describe the statistics of meso-scale particle contact density, while the inter-particle friction was kept constant. This is based on the assumption that particle contact density correlates directly with macroscopic friction angle. The trends of the two models are generally similar, except that in the micro-directional model, the strength (macroscopic friction) does not go through a minimum value as captured by the macro model and experiments. This discrepancy is due to the meso-structure (hexagons) used in the micro-directional model that cannot express distortion which would give rise to failure along a plane of weakness as shown in the macro-model earlier in the paper. The micro-directional model describes the material by a Supprimé : the same macroscopic friction angle distribution directional (not a spatial) distribution of hexagons, and cannot therefore give way to any geometric localization. This is by no means a shortcoming for the micro-directional model as the meso-structure can be further enriched to encompass other local failure mechanisms. In conclusion, the above discussion seems to validate (although not formally) the idea of enriching simple models like Mohr-Coulomb with directionally dependent strength parameters to capture experimentally observed anisotropic characteristics of structured materials. Although the work presented in this paper was limited to 2D stress states, the extension to 3D stress configuration can be readily carried out and thereafter integrated into elasto-plasticity framework to arrive at a tangential constitutive tensor with embedded anisotropy. It would be then of interest to explore under what anisotropic conditions would the constitutive tensor be prone to instability phenomena such as localization and diffuse failure.

Figure 1

 1 illustrates the 'peanut' shape of the proposed strength distribution such that the maximum and minimum values of strength occur at θ

Figure 1 .

 1 Figure 1. Schematic representation of strength distribution with respect to applied principal stresses Figure 2 further illustrates the effect of parameter λ on the shape of the strength distribution for 30 β

Figure 2 .

 2 Figure 2. Effect of λ on strength distribution shape

Figure 3

 3 Figure 3 illustrates an example of the search for failure conditions for a given strength distribution (with 0 /2 β π < <) where two mathematically possible solutions occur as plausible failure plane orientations. These are not conjugate solutions as in the isotropic case, given that they occur at distinct externally applied stress levels. Here, the solution with the smaller stress ratio is chosen, this being first encountered during loading history. It turns out that the chosen solution refers to a failure plane whose orientation f

Figure 3 .

 3 Figure 3. Polar representation of failure conditions for an anisotropic case (φ max =π/4,c=0, ω=0.5, λ=0.8, and β=6°)

Figure 4 .Figure 5 .Figure 6 .

 456 Figure 4. Deviatoric stress ratio at failure in negative and positive shear zone versus β for an anisotropic example (φ max =π/4, c=0, ω=0.5, λ=0.8, and β=6°)

Fig

  β there is a switch from failure near a plane of weakness to one in the intact material as marked by the sharp drop in failure plane orientation(Figs. 5 & 6d) and at the kink in Fig.4.

Figure 7 .

 7 Figure 7. Effect of λ on deviatoric stress at failure

Figure 8 .

 8 Figure 8. Comparisons between model prediction and experimental data from[START_REF] Donath | Experimental study of shear failure in anisotropic rocks[END_REF] and[START_REF] Liao | Triaxial residual strength of an anisotropric rock[END_REF]

Figure 9 .

 9 Figure 9. Comparison between (a) proposed macro model with (b) micro-directional model

Table 1 .

 1 Calibrated model parameters for experimental data sets

		K 0	ω	C 0`	ω c	λ=λ c
	Donath (1961)	0.61	0.316	24.26	0.796	0.90
	Liao and Hsieh (1999)	0.39	0.095	7.43	0.472	0.65

Second International Symposium on Computational Geomechanics (ComGeo II), 27/04/2011, Cavtat-Dubrovnik, HRV

ACKNOWLEDGEMENTS

The first two authors acknowledge the Natural Science and Engineering Research Council of Canada and the Computer Modelling Foundation for their financial support through a NSERC-CRD project. The third author is grateful for funding provided by the CEMAGREF in the form of a research visit fellowship to Calgary in the summer 2010.