Anatoli Juditsky
email: anatoli.juditsky@imag.fr

Accuracy guarantees for ℓ 1 -recovery *

Keywords: sparse recovery, linear estimation, oracle inequalities, nonparametric estimation by convex optimization AMS Subject Classification : 62G08, 90C25

Accuracy guarantees for L1-recovery

Anatoli B. Juditsky, Arkadii S.

Introduction

Recently several methods of estimation and selection which refer to the ℓ 1 -minimization received much attention in the statistical literature. For instance, Lasso estimator, which is the ℓ 1 -penalized least-squares method is probably the most studied (a theoretical analysis of the Lasso estimator is provided in, e.g., [START_REF] Bickel | Simultaneous analysis of Lasso and Dantzig selector[END_REF][START_REF] Bühlmann | On the conditions used to prove oracle results for the Lasso Electron[END_REF][START_REF] Bunea | Sparsity oracle inequalities for the Lasso[END_REF][START_REF] Van De Geer | The deterministic Lasso[END_REF][START_REF] Zhang | The sparsity and bias of the Lasso selection in highdimensional linear regression[END_REF][START_REF] Zhang | Some sharp performance bounds for least squares regression with L 1 regularization[END_REF][START_REF] Lounici | Sup-norm convergence rate and sign concentration property of Lasso and Dantzig estimators[END_REF][START_REF] Meinshausen | Lasso-type recovery of sparse representations for high-dimensional data[END_REF], see also the references cited therein). Another, closely related to the Lasso, statistical estimator is the Dantzig Selector [START_REF] Candès | 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][START_REF] Koltchinskii | The Dantzig selector and sparsity oracle inequalities[END_REF][START_REF] Lounici | Sup-norm convergence rate and sign concentration property of Lasso and Dantzig estimators[END_REF]. To be more precise, let us consider the estimation problem as follows. Assume that an observation

y = Ax + σξ ∈ R m (1)
is available, where x ∈ R n is an unknown signal and A ∈ R m×n is a known sensing matrix. We suppose that σξ is a Gaussian disturbance with ξ ∼ N (0, I m ) (i.e., ξ = (ξ 1 , ...., ξ n ) T , where ξ i are independent normal r.v.'s with zero mean and unit variance), and σ > 0 is a known deterministic noise level. Our focus is on the recovery of unknown signal x.

The Dantzig Selector estimator x DS of the signal x is defined as follows [START_REF] Candès | The Dantzig selector: statistical estimation when p is much larger than n[END_REF]:

x DS (y) ∈ Argmin

v∈R n { v 1 | A T (Av -y) ∞ ≤ ρ}
where ρ = O σ √ ln n is the algorithm's parameter. Since x DS is obtained as a solution of an linear program, it is very attractive by its low computational cost. Accuracy bounds for this estimator are readily available. For instance, a well known result about this estimator (cf. [START_REF] Candès | The Dantzig selector: statistical estimation when p is much larger than n[END_REF]Theorem 1.1]) is that if ρ = O σ ln(n/ǫ) then

x DS (y)x 2 ≤ Kσ s log(nǫ -1 )

with probability 1ǫ if a) the signal x is s-sparse, i.e. has at most s non-vanishing components, and b) the sensing matrix A with unit columns possesses the Restricted Isometry Property RIP(δ, k) with parameters 0 < δ < 1 1+ √ 2 and k ≥ 3s. 1 Further, in this case one has K = C(1δ) -1 , where C is a moderate absolute constant. This result is quite impressive, in part due to the fact (see, e.g. [START_REF] Candès | Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information[END_REF][START_REF] Candès | Stable signal recovery from incomplete and inaccurate measurements[END_REF]) that there exist m × n random matrices, with m < n, which possess the RIP with probability close to 1, δ close to zero and the value of k as large as O m ln -1 (n/m) . Similar performance guarantees are known for Lasso recovery

x lasso (y) ∈ Argmin

v∈R n v 1 + κ Av -y 2 2 ,
with properly chosen penalty parameter κ. The available accuracy bounds for Lasso and Dantzig Selector rely upon the Restricted Isometry Property or less restrictive assumptions about the sensing matrix, such as Restricted Eigenvalue [START_REF] Bickel | Simultaneous analysis of Lasso and Dantzig selector[END_REF] or Compatibility [START_REF] Bühlmann | On the conditions used to prove oracle results for the Lasso Electron[END_REF] conditions (a complete overview of those and several other assumptions with description of how they relate to each other is provided in [START_REF] Van De Geer | The deterministic Lasso[END_REF]). However, these assumptions cannot be verified efficiently. The latter implies that there is currently no way to provide any guaranties (e.g., confidence sets) of the performance of the proposed procedures. A notable exception from this rule is the Mutual Incoherence assumption (see, e.g. [START_REF] Donoho | Optimally sparse representation in general (non-orthogonal) dictionaries via ℓ 1 minimization[END_REF][START_REF] Elad | A generalized uncertainty principle and sparse representation in pairs of R n bases[END_REF][START_REF] Gribonval | Sparse representations in unions of bases[END_REF] and [START_REF] Zhang | Some sharp performance bounds for least squares regression with L 1 regularization[END_REF] for the case of, respectively, deterministic and random observation noise) which can be used to compute the accuracy bounds for recovery algorithms: a matrix A with columns of unit ℓ 2 -norm and mutual incoherence µ(A) possesses RIP(δ, k) with δ = (m -1)µ(A). 2 Unfortunately, the latter relation implies that µ(A) should be very small to certify the possibility of accurate ℓ 1 -recovery of non-trivial sparse signals, so that performance guarantees based on mutual incoherence are very conservative. This "theoretical observation" is supported by numerical experiments -the practical guarantees which may be obtained using the mutual incoherence are generally quite poor even for the problems with nice theoretical properties (cf. [START_REF] Juditsky | On verifiable sufficient conditions for sparse signal recovery via ℓ 1 minimization[END_REF][START_REF] Juditsky | Verifiable conditions of ℓ 1 -recovery of sparse signals with sign restrictions[END_REF]).

Recently the authors have proposed a new approach for efficient computing of upper and lower bounds on the "level of goodness" of a sensing matrix A, i.e. the maximal s such that the ℓ 1 -recovery of all signals with no more than s non-vanishing components is accurate in the case where the measurement noise vanishes (see [START_REF] Juditsky | On verifiable sufficient conditions for sparse signal recovery via ℓ 1 minimization[END_REF]). In the present paper we aim to use the related verifiable sufficient conditions of "goodness" of a sensing matrix A to provide efficiently computable bounds for the error of ℓ 1 recovery procedures in the case when the observations are affected by random noise.

The main body of the paper is organized as follows:

1 Recall that RIP(δ, k), called also uniform uncertainty principle, means that for any v ∈ R n with at most k nonzero entries,

(1 -δ) v 2 ≤ Av 2 2 ≤ (1 + δ) v 2
This property essentially requires that every set of columns of A with cardinality less than k approximately behaves like an orthonormal system. 2 The mutual incoherence µ(A) of a sensing matrix A = [A1, ..., An] is computed according to

µ(A) = max i =j |A T i Aj| A T i Ai .
Obviously, the mutual incoherence can be easily computed even for large matrices.

1. We start with Section 2.1 where we formulate the sparse recovery problem and introduce our core assumption -a verifiable condition H s,∞ (κ) linking matrix A ∈ R m×n and a contrast matrix H ∈ R m×n . In Sections 2.2, 2.3 we present two recovery routines with contrast matrices:

• regular recovery:

x reg (y) ∈ Argmin

v∈R n { v 1 : H T (Av -y) ∞ ≤ ρ},
• penalized recovery:

x pen (y) ∈ Argmin

v∈R n { v 1 + θs H T (Av -y) ∞ },
(s is our guess for the number of nonzero entries in the true signal, θ > 0 is the penalty parameter)

along with their performance guarantees under condition H s,∞ (κ) with κ < 1/2, that is, explicit upper bounds on the confidence levels of the recovery errors xx p . The novelty here is that our bounds are of the form Prob xx p ≤ O s 1/p σ ln(n/ǫ) for every s-sparse signal x and all 1 ≤ p ≤ ∞ ≥ 1ǫ (2)

(with hidden factors in O(•) independent of ǫ, σ), and are valid in the entire range 1 ≤ p ≤ ∞ of values of p. Note that similar error bounds for Dantzig Selector and Lasso are only known for 1 ≤ p ≤ 2, whatever be the assumptions on "essentially nonsquare" matrix A.

2. Our interest in condition H s,∞ (κ) stems from the fact that this condition, in contrast to the majority of the known sufficient conditions for the validity of ℓ 1 -based sparse recovery (e.g., Restricted Isometry/Eigenvalue/Compatibility), is efficiently verifiable. Moreover, it turns out that one can efficiently optimize the error bounds of the associated with this verifiable condition regular/penalized recovery routines over the contrast matrix H. The related issues are considered in Section 3. In Section 4 we provide some additional justification of the condition H, in particular, by linking it with the Mutual Incoherence and Restricted Isometry properties. This, in particular, implies that the condition H s,∞ (κ) with, say, κ = 1 3 associated with randomly selected m × n matrices A is feasible, with probability approaching 1 as m, n grow, for s as large as O( m/ ln(n)). We also establish limits of performance of the condition, specifically, show that unless A is nearly square, H s,∞ (κ) with κ < 1/2 can be feasible only when s ≤ O(1)

√ m, meaning that the tractability of the condition has a heavy price: when designing and validating ℓ 1 minimization based sparse recovery routines, this condition can be useful only in a severely restricted range of the sparsity parameter s.

3.

In Section 5 we show that the condition H s,∞ (κ) is the strongest (and seemingly the only verifiable one) in a natural family of conditions H s,q (κ) linking a sensing and a contrast matrix; here s is the number of nonzeros in the sparse signal to be recovered q ∈ [1, ∞]. We demonstrate that when a contrast matrix H satisfies H s,q (κ) with κ < 1/2, the associated regular and penalized ℓ 1 recoveries admit error bounds similar to [START_REF] Bickel | Simultaneous analysis of Lasso and Dantzig selector[END_REF], but now in the restricted range 1 ≤ p ≤ q of values of p. We demonstrate also that feasibility of H s,q (κ) with κ < 1/2 implies instructive (although slightly worse than those in (2)) error bounds for the Dantzig Selector and Lasso recovering routines.

4.

In Section 6, we present numerical results on comparison of regular/penalized ℓ 1 recovery with the Dantzig Selector and Lasso algorithms. The conclusion suggested by these preliminary numerical results is that when the former procedures are applicable (i.e., when the techniques of Section 3 allow to build a "not too large" contrast matrix satisfying the condition H s,∞ (κ) with, say, κ = 1/3), our procedures outperform significantly the Dantzig Selector and work exactly as well as the Lasso algorithm with "ideal" (unrealistic in actual applications) choice of the regularization parameter3 .

5.

In the concluding Section 7 we present a "Non-Euclidean Matching Pursuit algorithm" (similar to the one presented in [START_REF] Juditsky | Verifiable conditions of ℓ 1 -recovery of sparse signals with sign restrictions[END_REF]) with the same performance characteristics as those of regular/penalized ℓ 1 recoveries; this algorithm, however, does not require optimization and can be considered as a computationally cheap alternative to ℓ 1 recoveries, especially in the case when one needs to process a series of recovery problems with common sensing matrix.

All proofs are placed in the Appendix.

2 Accuracy bounds for ℓ 1 -Recovery Routines

Problem statement

Notation. For a vector x ∈ R n and 1 ≤ s ≤ n we denote x s the vector obtained from x by setting to 0 all but the s largest in magnitude entries of x. Ties, if any, could be resolved arbitrarily; for the sake of definiteness assume that among entries of equal magnitudes, those with smaller indexes have priority (e.g., with x = [1; 2; 2; 3] one has x 2 = [0; 2; 0; 3]). x s,p stands for the usual ℓ p -norm of x s (so that x s,∞ = x ∞ ). We say that a vector z is s-sparse if it has at most s nonzero entries. Finally, for a set I ⊂ {1, ..., n} we denote by J its complement {1, ..., n}\I; given x ∈ R n , we denote by x I the vector obtained from x by zeroing the entries with indices outside of I, so that x = x I + x J .

Given a norm ν(•) on R m and a matrix

H = [h 1 , ..., h N ] ∈ R m×N , we set ν(H) = max i≤N ν(h i ).
The problem. We consider an observation y ∈ R m

y = Ax + u + σξ, (3)
where x ∈ R n is an unknown signal and A ∈ R m×n is the sensing matrix. We suppose that σξ is a Gaussian disturbance, where ξ ∼ N (0, I m ) (i.e., ξ = (ξ 1 , ...., ξ n ) T with independent normal random variables ξ i with zero mean and unit variance), σ > 0 being known, and u is a nuisance parameter known to belong to a given uncertainty set U ⊂ R m which we will suppose to be convex, compact and symmetric w.r.t. the origin. Our goal is to recover x from y, provided that x is "nearly s-sparse." Specifically, we consider the sets

X(s, υ) = {x ∈ R n : x -x s 1 ≤ υ}
of signals which admit s-sparse approximation of • 1 -accuracy υ. Given p, 1 ≤ p ≤ ∞, and a confidence level 1ǫ, ǫ ∈ (0, 1), we quantify a recovery routine -a Borel function R m ∋ y → x(y) ∈ R n -by its worst-case, over x ∈ X(s, υ), confidence interval, taken w.r.t. • p -norm of the error. Specifically, we define the risks of a recovery routine as

Risk p ( x(•)|ǫ, σ, s, υ) = inf {δ : Prob{ξ : ∃x ∈ X(s, υ), u ∈ U : x(Ax + σξ + u) -x p > δ} ≤ ǫ} .
Equivalently: Risk p ( x(•)|ǫ, σ, s, υ) ≤ δ if and only if there exists a set Ξ of "good" realizations of ξ with Prob{ξ ∈ Ξ} ≥ 1ǫ such that whenever ξ ∈ Ξ, one has x(Ax + σξ + u)x p ≤ δ for all x ∈ X(s, υ) and all u ∈ U .

Norm ν(•). Given ǫ and σ > 0 let us denote

ν(v) = ν ǫ,σ,U (v) = sup u∈U u T v + σ 2 ln(n/ǫ) v 2 . ( 4
)
Since U is convex, closed and symmetric with respect to the origin, ν(•) is a norm. Let ν * be the norm on R n conjugate to ν:

ν * (u) = max v {v T u : ν(v) ≤ 1}. Conditions H(γ) and H s,∞ (κ). Let γ = (γ 1 , ..., γ n ) ∈ R n + . Given A ∈ R m×n , consider the following condition on a matrix H = [h 1 , ..., h n ] ∈ R m×n : H(γ): for all x ∈ R n and 1 ≤ i ≤ n one has |x i | ≤ |h T i Ax| + γ i x 1 . (5)
Now let s be a positive integer and κ > 0. Given A ∈ R m×n , we say that a matrix

H = [h 1 , ..., h n ] ∈ R m×n satisfies condition H s.∞ (κ) 4 , if ∀x ∈ R n : x ∞ ≤ H T Ax ∞ + s -1 κ x 1 . (6)
The conditions we have introduced are closely related to each other:

Lemma 1 If H satisfies H(γ), then H satisfies H s,∞ (s γ ∞ ),
and "nearly vice versa:" given H ∈ R m×n satisfying H s,∞ (κ), one can build efficiently a matrix H ′ ∈ R m×n satisfying H(γ) with γ = κ s [1; ...; 1] (i.e., κ = s γ ∞ ) and such that the columns of H ′ are convex combinations of the columns of H and -H, so that ν(H ′ ) ≤ ν(H) for every norm ν(•) on R m .

Regular ℓ 1 Recovery

In this section we discuss the properties of the regular ℓ 1 -recovery x reg given by:

x reg = x reg (y) ∈ Argmin v∈R n { v 1 : |h T i (Av -y)| ≤ ρ i , i = 1, ..., n}, (7)
where y is as in (3), h i , i = 1, ..., n, are some vectors in R m and ρ i > 0, i = 1, ..., n. We refer to the matrix H = [h 1 , ..., h n ] as to the contrast matrix underlying the recovering procedure. The starting point of our developments is the following Proposition 1 Given an m × n sensing matrix A, noise intensity σ, uncertainty set U and a tolerance ǫ ∈ (0, 1), let the matrix H = [h 1 , ..., h n ] from (7) satisfy the condition H(γ) for some γ ∈ R n + , and let ρ i in (7) satisfy the relation

ρ i ≥ ν i := ν(h i ), i = 1, ..., n (8)
where ν(•) is given by (4). Then there exists a set Ξ ⊂ R m , Prob{ξ ∈ Ξ} ≥ 1ǫ, of "good" realizations of ξ such that (i) Whenever ξ ∈ Ξ, for every x ∈ R n , every u ∈ U and every subset I ⊂ {1, ..., n} such that

γ I := i∈I γ i < 1 2 , (9)
the regular ℓ 1 -recovery x reg given by (7) satisfies:

(a) x reg (Ax + σξ + u) -x 1 ≤ 2 x J 1 + 2ρ I + 2ν I 1 -2γ I ; (b) | [ x reg (Ax + σξ + u) -x] i | ≤ ρ i + ν i + γ i x reg (y) -x 1 (10)
≤ ρ i + ν i + γ i 2 x J 1 + 2ρ I + 2ν I 1 -2γ I , i = 1, ..., n,
where ρ I = i∈I ρ i and ν I = i∈I ν i .

(ii) In particular, when setting

ρ s = [ρ 1 ; ...; ρ n ] s,1 , ν s = [ν(h 1 ); ...; ν(h n )] s,1 , γ s = [γ 1 ; ...; γ n ] s,1 , ρ = ρ 1 = max i ρ i , ν(H) = ν 1 = max i ν(h i ), γ = γ 1 = max i γ i , (11)
and assuming γ s < 1 2 , for every x ∈ R n , ξ ∈ Ξ and u ∈ U it holds

x reg (Ax + σξ + u) -x 1 ≤ 2 x -x s 1 + ρ s + ν s 1 -2 γ s ≤ 2 x -x s 1 1 -2 γ s + 2s ρ + ν(H) 1 -2 γ s ; x reg (Ax + σξ + u) -x ∞ ≤ 2 γ x -x s 1 1 -2 γ s + [1 + 2s γ -2 γ s ][ ρ + ν(H)] 1 -2 γ s
(iii) Finally, assuming s γ < 1/2, for every ξ ∈ Ξ, x ∈ R n and u ∈ U one has

x reg (Ax + σξ + u) -x 1 ≤ 2 x-x s 1 1-2s γ + 2s ρ+ν(H) 1-2s γ ; x reg (Ax + σξ + u) -x ∞ ≤ s -1 x-x s 1 1-2s γ + ρ+ν(H) 1-2s γ . (12)
The following result is an immediate corollary of Proposition 1:

Lemma 2 Under the premise of Proposition 1, assume that γ s < 1 2 . Then for all 1 ≤ p ≤ ∞ and υ ≥ 0:

Risk p ( x reg (•)|ǫ, σ, s, υ) ≤ 2 1 -2 γ s υ + ρ s + ν s 1 p γυ + [ 1 2 -γ s ][ ρ + ν(H)] + γ[ ν s + ρ s ] p-1 p (13)
(for notation, see [START_REF] Elad | A generalized uncertainty principle and sparse representation in pairs of R n bases[END_REF]). Further, if s γ < 1/2, we have also

1 ≤ p ≤ ∞ ⇒ Risk p ( x reg (•)|ǫ, σ, s, υ) ≤ (2s) 1 p 1 -2s γ (s -1 υ + ρ + ν(H)). (14)
The next statement is similar to the cases of κ := s γ < 1/2 in Proposition 1 and Lemma 2; the difference is that now we assume that H satisfies H s,∞ (κ), which, by Lemma 1, is a weaker requirement on H than to satisfy H(γ) with s γ ≡ s γ ∞ = κ.

Proposition 2 Given an m × n sensing matrix A, noise intensity σ, uncertainty set U and a tolerance ǫ ∈ (0, 1), let the matrix H = [h 1 , ..., h n ] from (7) satisfy the condition H s,∞ (κ) for some κ < 1/2, and let ρ i in [START_REF] Candès | The Dantzig selector: statistical estimation when p is much larger than n[END_REF] satisfy the relation [START_REF] Candès | The restricted isometry property and its implications for compressed sensing[END_REF]. Then there exists a set Ξ ⊂ R m , Prob{ξ ∈ Ξ} ≥ 1ǫ, of "good" realizations of ξ such that whenever ξ ∈ Ξ, for every x ∈ R n and every u ∈ U one has

x reg (Ax + σξ + u) -x 1 ≤ 2 x-x s 1 1-2κ + 2s ρ+ν(H) 1-2κ ; x reg (Ax + σξ + u) -x ∞ ≤ s -1 x-x s 1 1-2κ + ρ+ν(H) 1-2κ . (15)
In particular,

1 ≤ p ≤ ∞ ⇒ Risk p ( x reg (•)|ǫ, σ, s, υ) ≤ (2s) 1 p 1 -2κ (s -1 υ + ρ + ν(H)). ( 16
)

Penalized ℓ 1 Recovery

Now consider the penalized ℓ 1 -recovery x pen as follows:

x pen (y) ∈ Argmin

v∈R n { v 1 + θs H T (Av -y) ∞ }, ( 17
)
where y is as in [START_REF] Bühlmann | On the conditions used to prove oracle results for the Lasso Electron[END_REF], and an integer s ≤ n, a positive θ, and a matrix H are parameters of the construction.

Proposition 3 Given an m × n sensing matrix A, an integer s ≤ n, a matrix H = [h 1 , ..., h n ] ∈ R m×n and positive reals γ i , 1 ≤ i ≤ n, satisfying the condition H(γ), and a θ > 0, assume that

γ s := γ s,1 < 1 2 (18)
and

(1 -γ s ) -1 < θ < ( γ s ) -1 (19)
Further, let σ ≥ 0, ǫ ∈ (0, 1), and let

ν i = ν ǫ,σ,U (h i ), i = 1, ..., n, ν(H) = max i ν i . ( 20
)
Consider the penalized recovery x pen (•) associated with H, s, θ. There exists a set Ξ ⊂ R m , Prob{ξ ∈ Ξ} ≥ 1ǫ, of "good" realizations of ξ such that (i) Whenever ξ ∈ Ξ, for every signal x ∈ R n and every u ∈ U one has

(a) x pen (Ax + σξ + u) -x 1 ≤ 2 x-x s 1 +2sθν(H) min[θ(1-γs)-1,1-θ γs] (b) x pen (Ax + σξ + u)) -x ∞ ≤ 1 sθ + γ x pen (Ax + σξ + u) -x 1 + 2ν(H) ≤ 2 1 sθ + γ x-x s 1 min[θ(1-γs)-1,1-θ γs] + 2ν(H) 1+sθ γ min[θ(1-γs)-1,1-θ γs] + 1 , (21)
where, as in Lemma 2, γ = max i γ i .

(ii) When θ = 2 and γ < 1 2s , one has for every x ∈ R n , u ∈ U and ξ ∈ Ξ:

(a)

x pen (Ax + σξ + u) -x 1 ≤ 2 x-x s 1 1-2s γ + 4s ν(H) 1-2s γ (b) x pen (Ax + σξ + u)) -x ∞ ≤ 2s -1 x-x s 1 1-2s γ + 4 ν(H) 1-2s γ , (22)
whence for every υ ≥ 0 and 1 ≤ p ≤ ∞:

Risk p ( x pen (•)|ǫ, σ, s, υ) ≤ 2s 1 p 1 -2s γ (s -1 υ + 2ν(H)). ( 23
)
The next statement is in the same relation to Proposition 3 as Proposition 2 is to Proposition 1 and Lemma 2.

Proposition 4 Given an m × n sensing matrix A, noise intensity σ, uncertainty set U and a tolerance ǫ ∈ (0, 1), let the matrix H = [h 1 , ..., h n ] from (17) satisfy the condition H s,∞ (κ) for some κ < 1/2, and let θ = 2. Then there exists a set Ξ ⊂ R m , Prob{ξ ∈ Ξ} ≥ 1ǫ, of "good" realizations of ξ such that whenever ξ ∈ Ξ, for every x ∈ R n and every u ∈ U one has

x pen (Ax + σξ + u) -x 1 ≤ 2 x-x s 1 1-2κ + 4s ν(H) 1-2κ ; x pen (Ax + σξ + u) -x ∞ ≤ 2s -1 x-x s 1 1-2κ + 4 ν(H) 1-2κ . (24)
In particular,

1 ≤ p ≤ ∞ ⇒ Risk p ( x pen (•)|ǫ, σ, s, υ) ≤ 2s 1 p 1 -2κ (s -1 υ + 2ν(H)). ( 25
)
Note that under the premise of Proposition 2, the smallest possible values of ρ i are the quantities ν i , which results in ρ = ν(H); with this choice of ρ i , the risk bound for the regular recovery, as given by the right hand side in [START_REF] Koltchinskii | The Dantzig selector and sparsity oracle inequalities[END_REF], coincides within factor 2 with the risk bound for the penalized recovery with θ = 2 as given by (25); both bounds assume that H satisfies H s,∞ (κ) with κ < 1/2 and imply that

1 ≤ p ≤ ∞ ⇒ Risk p ( x(•)|ǫ, σ, s, υ) ≤ 2 s 1 p 1 -2κ (s -1 υ + 2ν(H)). ( 26
)
When υ = 0, the latter bound admits a quite transparent interpretation: everything is as if we were observing the sum of an unknown s-dimensional signal and an observation error of the uniform norm O(1)ν(H).

Efficient construction of the contrast matrix H

In what follows, we fix A, the "environment parameters" ǫ, σ, U and the "level of sparsity" s of signals x we intend to recover, and are interested in building the contrast matrix H = [h 1 , ..., h n ] resulting in as small as possible error bound (26). All we need to this end is to answer the following question (where we should specify the norm ϕ(•) as ν ǫ,σ,U (•)):

(?) Let ϕ(•) be a norm on R m , and s be a positive integer. What is the domain G s of pairs (ω, κ) ∈ R 2 + such that κ < 1/2 and there exists matrix H = [h 1 , ..., h n ] ∈ R m×n satisfying the condition H s,∞ (κ) and the relation ϕ(H) := max i ϕ(h i ) ≤ ω? How to find such an H, provided it exists?

Invoking Lemma 1, we can reformulate this question as follows:

(??) Let ϕ(•) and s be as in (?). Given (ω, κ) ∈ R 2 + , how to find vectors

h i ∈ R m , 1 ≤ i ≤ n, satisfying (a) : ϕ(h i ) ≤ ω; & (b) : |x i | ≤ |h T i Ax| + s -1 κ x 1 ∀x ∈ R n (P i )
for every i, or to detect correctly that no such collection of vectors exists? The answer to (??) is given by the following Lemma 3 Given κ > 0, ω ≥ 0, and a positive integer s, let γ = κ/s. For every i ≤ n, the following three properties are equivalent to each other:

Indeed,
(i) There exists h = h i satisfying (P i );

(ii) The optimal value in the optimization problem

Opt i (γ) = min h ϕ(h) : A T h -e i ∞ ≤ γ (P γ i )
where e i is i-th standard basic orth in R n , is ≤ ω;

(iii) One has ∀x ∈ R n : |x i | ≤ ωϕ * (Ax) + γ x 1 , (27)
where ϕ * (u) = max

ϕ(v)≤1 u T v is the norm on R m conjugate to ϕ(•).
Whenever one (and then -all) of these properties take place, problem (P γ i ) is solvable, and its optimal solution h i satisfies (P i ).

Optimal contrasts for regular and penalized recoveries

As an immediate consequence of Lemma 3, we get the following description of the domain G s associated with the norm ϕ(

•) = ν ǫ,σ,U (•): (a) G s = (ω, κ) ≥ 0 : s -1 κ ≥ γ * , ω ≥ ω * (s -1 κ) , where (b) γ * = max 1≤i≤n min h A T h -e i ∞ = max i max x {x i : x 1 ≤ 1, Ax = 0} , (c) ω * (γ) = max 1≤i≤n Opt i (γ) (28)
where φ(•) in (P γ i ) is specified as ν ǫ,σ,U (•). Note that the second equality in (b) is given by Linear Programming duality. Indeed, by (b), γ * is the smallest γ for which all problems (P γ i ), i = 1, ..., n, are feasible, and thus, by Lemma 3, (γ, κ) ∈ G s if and only if κ/s ≥ γ * and ω ≥ ω * (κ/s).

Note that the quantity γ * depends solely of A, while ω * (•) depends on ǫ, σ, U , as on parameters, but is independent of s.

The outlined results suggest the following scheme of building the contrast matrix H:

• we compute γ * by solving n Linear Programming problems in (28.b); if sγ * ≥ 1 2 , then G s does not contain points (ω, κ) with κ < 1/2, so that our recovery routines are not applicable (or, at least, we cannot justify them theoretically);

• when sγ * < 1 2 , the set G s is nonempty, and its Pareto frontier (the set of pairs (ω,

κ) ∈ R 2 + such that (ω, κ) ≥ (ω ′ , κ) ∈ G s is possible if and only if ω ′ = ω) is the curve (ω * (γ), sγ), γ * ≤ γ < 1 2s
. We choose a "working point" on this curve, that is, a point γ ∈ [γ * , 1 2s ] and compute ω * (γ) by solving the convex optimization programs (P γ i ), i = 1, ..., n, with φ(•) specified as ν ǫ,σ,U (•). ω * (γ) is nothing but the maximum, over i, of the optimal values of these problems, and the optimal solutions h i to the problems induce the matrix H = H(γ) = [h 1 , ..., h n ] which satisfies H s,∞ (sγ) and has ν(H) ≤ ω * (γ). By reasoning which led us to (??),

ν(H(γ)) = ω * (γ) = min H ′ ν(H ′ ) : H ′ satisfies H s,∞ (sγ) , that is, H = H(γ)
is the best for our purposes contrast matrices satisfying H s,∞ (sγ). With this contrast matrix, the error bound (26) for regular/penalized ℓ 1 recoveries (in the former,

ρ i = ν i (h i ), in the latter, θ = 2) read 1 ≤ p ≤ ∞ ⇒ Risk p ( x(•)|ǫ, σ, s, υ) ≤ 2 s 1 p 1 -2sγ (s -1 υ + 2ω * (γ)). ( 29
)
The outlined strategy does not explain how to choose γ. This issue could be resolved, e.g., as follows. We choose an upper bound on the sensitivity of the risk (29) to υ, i.e., to the • 1 -deviation of a signal to be recovered from the set of s-sparse signals. This sensitivity is proportional to 1 1-2sγ , so that an upper bound on the sensitivity translates into an upper bound γ + < 1 2s on γ. We can now choose γ by minimizing the remaining term in the risk bound over γ ∈ [γ * , γ + ], which amounts to solving the optimization problem

max τ : τ ω * (γ) ≤ 1 -2sγ, γ * ≤ γ ≤ γ + .
Observing that ω * (•) is, by its origin, a convex function, we can solve the resulting problem efficiently by bisection in τ . A step of this bisection requires solving a univariate convex feasibility problem with efficiently computable constraint and thus is easy, at least for moderate values of n.

Range of feasibility of condition H s,∞ (κ)

We address the crucial question of what can be said about the magnitude of the quantity ω * (•), see (28) and the risk bound (29). One way to answer it is just to compute the (efficiently computable!) quantity ω * (γ) for a desired value of γ. Yet it is natural to know theoretical upper bounds on ω * in some "reference" situations. Below, we provide three results of this type.

At this point, it makes sense to express in the notation that ω * (γ) depends, as on parameters, on the sensing matrix A and the "environment parameters" ǫ, σ, U , so that in this section we write ω * (γ|A, ǫ, σ, U ) instead of ω * (γ).

Bounding ω * (•) via mutual incoherence

Recall that for an m × n sensing matrix A = [A 1 , ..., A n ] with no zero columns, its mutual incoherence is defined as

µ(A) = max 1≤i =j≤n |A T i A j | A T i A i .
Compressed Sensing literature contains numerous mutual-incoherence-related results (see, e.g., [START_REF] Donoho | Optimally sparse representation in general (non-orthogonal) dictionaries via ℓ 1 minimization[END_REF][START_REF] Elad | A generalized uncertainty principle and sparse representation in pairs of R n bases[END_REF][START_REF] Gribonval | Sparse representations in unions of bases[END_REF] and references therein). To the best of our knowledge, all these results state that if s is a positive integer and A is a sensing matrix such that sµ(A) µ(A)+1 < 1 2 , then ℓ 1 -based sparse recovery is well suited for recovering s-sparse signals (e.g., recovers them exactly when there is no observation noise, admit explicit error bounds when there is noise and/or the signal is only nearly s-sparse, etc.). To the best of our knowledge, all these results, up to the values of absolute constant factors in error bounds, are covered by the risk bounds (29) combined with the following immediate observation:

Observation 1 Whenever A = [A 1 , ..., A n ]
is an m × n matrix with no zero columns and s is a positive integer, the matrix

H(A) = 1 µ(A)+1 [A 1 /A T 1 A 1 , A 2 /A T 2 A 2 , ..., A n /A T n A n ] satisfies the condition H s,∞ sµ(A) µ(A)+1 . Verification is immediate: the diagonal entries in the matrix Z = I -H T A are equal to γ := 1 -1 µ(A)+1 = µ(A) µ(A)+1
, while the magnitudes of the off-diagonal entries in Z do not exceed γ. Therefore

x ∈ R n ⇒ γ x 1 ≥ Zx ∞ = x -H T Ax ∞ ≥ x ∞ -H T Ax ∞ ⇔ x ∞ ≤ H T Ax ∞ + γ x 1 ⇔ H satisfies H s,∞ (sγ).
Observe that the Euclidean norms of the columns in H(A) do not exceed min

i A i 2 -1 , whence ν(H(A)) ≤ r(U ) + σ √ 2 ln(n/ǫ) min i A i 2 , where r(U ) = max u∈U u 2 .
In the notation from Section 3, our observations can be summarized as follows:

Corollary 1 For every m×n matrix A with no zero columns, one has γ * ≤ γ := µ(A) µ(A)+1 and ω * (γ|A, ǫ, σ,

U ) ≤ ν(H(A)) ≤ r(U ) + σ √ 2 ln(n/ǫ) min i A i 2 . In particular, s ≤ µ(A) + 1 3µ ⇒ ω * ( 1 3s |A, ǫ, σ, U ) ≤ r(U ) + σ 2 ln(n/ǫ) min i A i 2 .
It should be added that as m, n grow in such a way that ln(n) ≤ O(1) ln m, realizations A of "typical" random m × n matrices (e.g., those with independent N (0, 1/m) entries or with independent entries taking values ±1/ √ m) with overwhelming probability satisfy µ(A) ≤ O(1) ln(n)/m and A i 2 ≤ 0.9 for all i. By Corollary 1, it follows that for these A the condition H s,∞ (κ) with, say, κ = 1/3 can be satisfied for s as large as O(1) m/ ln(n) merely by the choice

H = H(A), which ensures that ν(H) ≤ O(1)[r(U ) + σ 2 ln(n/ǫ)]; in particular, in the indicated range of values of s one has ω * ( 1 3s ) ≤ O(1)[r(U ) + σ 2 ln(n/ǫ)].

The case of A satisfying the Restricted Isometry Property

Proposition 5 Let A satisfy RIP(δ, k) with some δ ∈ (0, 1) and with k > 1. Then there exists matrix H(A) which, for every positive integer s, satisfies the condition H s,∞ (sγ(δ, k)), with

γ(δ, k) = √ 2δ (1 -δ) √ k -1 , (30)
and is such that

ν(H(A)) ≤ r(U ) + σ 2 ln(n/ǫ) / √ 1 -δ. In particular, s ≤ 1 -δ 3 √ 2 √ k -1 ⇒ ω * ( 1 3s |A, ǫ, σ, U ) ≤ 1 √ 1 -δ r(U ) + σ 2 ln(n/ǫ) . ( 31
)

Oracle inequality

Here we assume that A ∈ R m×n possesses the following property (where S is a positive integer and ϕ > 0):

O(S, ω): For every i ∈ {1, ..., n} and every S-element subset I ∋ i of {1, ..., n} there exists a routine R i,I for recovering x i from a noisy observation

y = Ax + u + σe, [e ∼ N (0, I m ), u ∈ U ]
of unknown signal x ∈ R n , known to be supported on I such that for every such signal and every u ∈ U one has Prob{|R i,I (Ax + u + σe) -

x i | ≥ ω} ≤ ǫ.
We intend to demonstrate that in this situation for all s in certain range (which extends as S grows and ω decreases) the uniform error of the regular and the penalized recoveries associated with properly selected contrast matrix is, with probability ≥ 1ǫ, "close" to ω. The precise statement is as follows: Proposition 6 Given A and the "environment parameters" ǫ < 1/16, σ, U , assume that A satisfies the condition O(S, γ) with certain S, γ. Then for every integer s from the range

1 ≤ s ≤ σ 2S ln(1/ǫ) 4ω A (32)
(here • is the standard matrix norm, the largest singular value) there exists a contrast matrix H satisfying the condition H s,∞ ( 1 4 ) and such that ν(H) ≤ 2 1 + ln(n)/ ln(1/ǫ)ω, so that in the outlined range of values of H one has ω * ( 1 4s ) ≤ 2 1 + ln(n)/ ln(1/ǫ)ω, and the associated with H error bound (29) for regular/penalized ℓ 1 recovery is

Risk p ( x(•)|ǫ, σ, s, υ) ≤ 16s 1 p ω 1 + ln n ln(1/ǫ) + υ 4s . ( 33
)
Proposition 6 justifies to some extent, our approach; it says that if there exists a routine which recovers S-sparse signals with a priori known sparsity pattern within certain accuracy (measured component-wise), then our recovering routines exhibit "close" performance without any knowledge of the sparsity pattern, albeit in a smaller range of values of the sparsity parameter.

Condition H s,∞ (κ): limits of performance

Recall that when recovering s-sparse signals, the condition H s,∞ (κ) helps only when κ < 1/2. Unfortunately, with these κ, the condition is feasible in a severely restricted range of values of s. Specifically, from [15, Proposition 5.1] and Lemma 1 it immediately follows that

(*) If A ∈ R m×n is not "nearly square," that is, if n > 2(2 √ m + 1) 2 , then the condition H s,∞ (κ)
with κ < 1/2 cannot be satisfied when s is "large", namely, when s > 2 √ 2m + 1.

Note that from the discussion at the end of section 4.1 we know that the "O( √ m) limit of performance" of the condition H s,∞ (•) stated in (*) is "nearly sharp:" -when s ≤ O(1) √ m, the condition H s,∞ ( 1 3 ) associated with a typical randomly generated m × n sensing matrix A is feasible and can be satisfies with a contrast matrix H with quite moderate ν(H).

(*) says that unless A is nearly square, the condition H s,∞ (•) can validate ℓ 1 sparse recovery only in a severely restricted range s ≤ O( √ m) of values of the sparsity parameter. This is in sharp contrast with unverifiable sufficient conditions for "goodness" of ℓ 1 recovery, like RIP: it is well known that when m, n grow, realizations of "typical" random m × n matrices, like those mentioned at the end of Section 4.1, with overwhelming probability possess RIP(0.1, 2s) with s as large as O(m/ ln(2n/m)). As a result, "unverifiable" sufficient conditions, like RIP, can justify the validity of ℓ 1 recovery routines in a much wider (and in fact -the widest possible) range of values of the sparsity parameter s than the "fully computationally tractable" condition H s,∞ (•). This being said, note that this comparison is not completely fair. Indeed, aside of its tractability, the condition H s,∞ (κ) with κ < 1/2 ensures the error bounds (29) in the entire range 1 ≤ p ≤ ∞ of values of p, which perhaps is not the case with conditions like RIP. Specifically, consider the "no nuisance" case U = {0}, and let A satisfy RIP(0.1, 2S) for certain S. It is well known (see, e.g., the next section) that in this case the Dantzig Selector recovery ensures for every s ≤ S and every s-sparse signal x that

x DS -x p ≤ O(1)σ ln(n/ǫ)s 1/p , 1 ≤ p ≤ 2,
with probability ≥ 1ǫ. However, we are not aware of similar bounds (under whatever conditions) for "large" s and p > 2. For comparison: in the case in question, for "small" s, namely, s ≤ O(1) √ S, we have ω * ( 1 3s ) ≤ O(1)σ ln(n/ǫ) (by Proposition 5), whence for regular and penalized ℓ 1 recoveries with appropriately chosen contrast matrix (which can be built efficiently!) one has for all s-sparse x xx p ≤ O(1)σ ln(n/ǫ)s

1 p ∀p ∈ [1, ∞]
with probability ≥ 1ǫ (see ( 29)). We wonder whether a similar (perhaps, with extra logarithmic factors) bound can be obtained for large s (e.g., s ≥ m 1 2 +δ ) for a whatever ℓ 1 recovery routine and a whatever essentially nonsquare (say, m < n/2) m × n sensing matrix A with columns of Euclidean length ≤ O(1).

Extensions

We are about to demonstrate that the pivot element of the preceding sections -the condition H s,∞ (κ) -is the strongest (and seemingly the only verifiable one) in a natural parametric series of conditions on a contrast matrix H; every one of these conditions validates the regular and the penalized ℓ 1 recoveries associated with H in certain restricted range of values of p in the error bounds (29).

Conditions H s,q (κ)

Let us fix an m × n sensing matrix A. Given a positive integer s ≤ m, a q ∈ [1, ∞] and a real κ > 0, let us say that an m × n contrast matrix H satisfies condition H s,q (κ), if

∀x ∈ R n : x s,q ≤ s 1 q H T Ax ∞ + κs 1 q -1 x 1 , (34)
where x s,q = x s q and x s , as always, is the vector obtained from x by zeroing all but the s largest in magnitude entries. Observe that

• What used to be denoted H s,∞ (κ) before, is exactly what is called H s,∞ (κ) now;
• If H satisfies H s,q (κ), H satisfies H s,q ′ (κ) for all q ′ ∈ [1, q] (since for s-sparse vector x s we have

x s q ′ ≤ s 1 q ′ -1 q x s s,q ).
Less immediate observations are as follows:

• Let A be an m × n matrix and let s ≤ n be a positive integer. We say that A is s-good if for all

s-sparse x ∈ R n the ℓ 1 -recovery x ∈ Argmin v { v 1 : Av = y}
is exact in the case of noiseless observation y = Ax. It turns out that feasibility of H s,1 (κ) with κ < 1 2 is intimately related to s-goodness of A:

Lemma 4 A is s-good if and only if there exist κ < 1 2 and H ∈ R m×n satisfying H s,1 (κ). • The Restricted Isometry Property implies feasibility of H s,2 (κ) with small κ:

Lemma 5 Let A satisfy RIP(δ, 2s) with δ < 1 3 . Then the matrix H = 1 1-δ A satisfies the condition H s,2 (κ) with κ = δ 1-δ < 1 2 .
5.2 Regular and penalized ℓ 1 recoveries with contrast matrices satisfying H s,q (κ)

Our immediate goal is to obtain the following extension of the main results of Section 2, specifically, Propositions 2, 4:

Proposition 7 Assume we are given an m × n sensing matrix A = [a 1 , ..., a n ], an integer s ≤ m, κ < 1/2, a contrast matrix H = [h 1 , ..., h n ] ∈ R m×n , and q ∈ [1, ∞] such that H satisfies the condition H s,q (κ). Denote ν i = ν ǫ,σ,U (h i ), where the norm ν ǫ,σ,U (•) is defined in (4), and ν(H) = max i ν i . Let also noise intensity σ, uncertainty set U and tolerance ǫ ∈ (0, 1) be given.

(i) Consider the regular recovery [START_REF] Candès | The Dantzig selector: statistical estimation when p is much larger than n[END_REF] with the contrast matrix H and the parameters ρ i satisfying the relations

ρ i ≥ ν i , 1 ≤ i ≤ n,
and let ρ = max i ρ i . Then

1 ≤ p ≤ q ⇒ Risk p ( x reg (•)|ǫ, σ, s, υ) ≤ (3s) 1 p ρ + ν(H) + s -1 υ 1 -2κ . ( 35
)
(ii) Consider the penalized recovery [START_REF] Lounici | Sup-norm convergence rate and sign concentration property of Lasso and Dantzig estimators[END_REF] with the contrast matrix H and θ = 2. Then

1 ≤ p ≤ q ⇒ Risk p ( x pen (•)|ǫ, σ, s, υ) ≤ 3s 1 p 2ν(H) + s -1 υ 1 -2κ . ( 36
)
5.3 Error bounds for Lasso and Dantzig Selector under condition H s,q (κ)

We are about to demonstrate that the feasibility of condition H s,q (κ) with κ < 1 2 implies some consequences for the performance of Lasso and Dantzig Selector when recovering s-sparse signals in • p norms, 1 ≤ p ≤ q. This might look strange at the first glance, since neither Lasso nor Dantzig Selector use contrast matrices. The surprise, however, is eliminated by the following observation:

(!) Let H satisfy H s,q (κ) and let λ be the maximum of the Euclidean norms of columns in H.

Then ∀x ∈ R n : x s,q ≤ λs 1 q Ax 2 + κs 1 q -1 x 1 . (37)
The fact that a condition like (37) with κ < 1/2 plays a crucial role in the performance analysis of Lasso and Dantzig Selector is neither surprising nor too novel. For example, the standard error bounds for the latter algorithms under the RIP assumption are in fact based on the validity of (37) with λ = O(1) for q = 2 (see Lemma 5). Another example is given by the Restricted Eigenvalue [START_REF] Bickel | Simultaneous analysis of Lasso and Dantzig selector[END_REF] and the Compatibility conditions [START_REF] Bühlmann | On the conditions used to prove oracle results for the Lasso Electron[END_REF][START_REF] Van De Geer | The deterministic Lasso[END_REF]. Specifically, the Restricted Eigenvalue condition RE(s, ρ, κ) (s is positive integer, ρ > 1, κ > 0 states that

x s 2 ≤ 1 κ Ax 2 whenever ρ x s 1 ≥ x -x s 2 , whence x s 1 ≤ √ s κ Ax 2 whenever (ρ + 1) x s 1 ≥ x 1 , so that ∀x ∈ R n : x s,1 ≤ s 1/2 κ Ax 2 + 1 1 + ρ x 1 ;. (38)
Further, the Compatibility condition of [START_REF] Van De Geer | The deterministic Lasso[END_REF] is nothing but (38) with ρ = 3. We see that both Restricted Eigenvalue and Compatibility conditions imply (37) with q = 1, λ = (κ √ s) -1 and certain κ < 1/2.

We are about to present a simple result on the performance of Lasso and Dantzig Selector algorithms in the case when A satisfies the condition (37). The result is as follows:

Proposition 8 Let m × n matrix A = [a 1 , ..., a n ] satisfy (37) with κ < 1 2 and some q ∈ [1, ∞], and let β = max i a i 2 . Let also the "environment parameters" σ > 0, ǫ ∈ (0, 1) be given, and let there be no nuisance: U = {0}.

(i) Consider the Dantzig Selector recovery

x DS (y) ∈ Argmin v v 1 : A T (Av -y) ∞ ≤ ρ , where ρ ≥ ̺ := σβ 2 ln(n/ǫ). ( 39
)
Then

1 ≤ p ≤ q ⇒ Risk p ( x DS (•)|ǫ, σ, s, υ) ≤ 2(3s) 1 p 1 -2κ 2s λ 2 (ρ + ̺) 1 -2κ + s -1 υ . (40)
(ii) Consider the Lasso recovery

x lasso (y) ∈ Argmin v v 1 + κ Av -y 2 2 ,
and let κ satisfy the relation

2κ + 2̺κ < 1,
where ̺ is given by (39). Then

1 ≤ p ≤ q ⇒ Risk p ( x lasso (•)|ǫ, σ, s, υ) ≤ 4s 1 p 1 -2κ -2̺κ 2s λ 2 κ + s -1 υ . (41)
In particular, with

κ = 1 -2κ 4̺ , (42)
one has

1 ≤ p ≤ q ⇒ Risk p ( x lasso (•)|ǫ, σ, s, υ) ≤ 8s 1 p 1 -2κ 8s̺ λ 2 1 -2κ + s -1 υ . ( 43
)
Discussion. Let us compare the error bounds given by Propositions 7, 8. Assume that there is no nuisance (U = {0}) and A is such that the condition H s,q ( 1 4 ) is satisfied by certain matrix H, the maximum of Euclidean norms of the columns of H being λ. Assuming that the penalized recovery uses θ = 2, and the regular recovery uses ρ = ν(H) = λσ 2 ln(n/ǫ)), the associated risk bounds as given by Proposition 7 become Risk p ( x(•)|ǫ, σ, s, υ) ≤ O(1)s

1 p λσ 2 ln(n/ǫ) + s -1 υ 1 ≤ p ≤ q. ( 44
)
Note that these bounds admit a transparent interpretation: in the range 1 ≤ p ≤ q an s-sparse signal is recovered as if we were identifying correctly its support and estimating the entries with the uniform error O(1) λσ 2 ln(n/ǫ). Now, as we have already explained, the existence of a matrix H satisfying H s,q ( 1 4 ) with columns in H being of Euclidean lengths ≤ λ implies validity of (37) with κ = 1 4 . Assuming that in Dantzig Selector one uses ρ = ̺, and that κ in Lasso is chosen according to (42), the error bounds for Dantzig Selector and Lasso as given by Proposition 8 become

Risk p ( x(•)|ǫ, σ, s, υ) ≤ O(1)s 1 p [β λ]s λσ 2 ln(n/ǫ) + s -1 υ 1 ≤ p ≤ q. ( 45
)
Observe that β λ ≥ O(1) (look what happens with (37) when x is the i-th basic orth). We see that the bounds (45) are worse than the bounds (44), primarily due to the presence of the factor s in the first bracketed term in (45). At this point it is unclear whether this drawback is an artifact caused by poor analysis of the Dantzig Selector and Lasso algorithms or it indeed "reflects reality." Some related numerical results presented in Section 6.1 suggest that the latter option could be the actual one. Moreover, consider an example of the recovery problem with a 2 × 2 matrix A with unit columns and singular values 1 and ε. It can be easily seen that if x is aligned with the second right singular vector of A (corresponding to the singular value ε) the error of the Dantzig Selector may be as large as O(ε -2 σ), while the error of "H-conscious" recovery will be O(ε -1 σ) up to the logarithmic factor in ǫ (indeed, choosing H = A -1 results in λ = ε -1 ). This toy example suggests that the extra λ factor in the bound (45), at least for Dantzig Selector, is not only due to our clumsy analysis.

This being said, it should be stressed that the comparison of regularized/penalised ℓ 1 recoveries with Dantzig Selector and Lasso based solely on above the error bounds is somehow biased against Dantzig Selector and Lasso. Indeed, in order for regular/penalized ℓ 1 recoveries to enjoy their "good" error bounds, we should specify the required contrast matrix, which is not the case for Lasso and Dantzig Selector: the bounds (45) require only existence of such a matrix5 . Besides this, there is at least one case where error bounds for Dantzig Selector are as good as (44), specifically, the case when A possesses, say, RIP(0.1, 2s). Indeed, in this case, by Lemma 5, the matrix H = O(1)A satisfies H s,2 ( 1 4 ), meaning that Dantzig Selector with properly chosen ρ is nothing but the regular recovery with contrast matrix H and as such obeys the bounds (44) with q = 2.

It is time to point out that the above discussion is somehow scholastic: when q < ∞ and s is nontrivial, we do not know how to verify efficiently the fact that the condition H s,q (κ) is satisfied by a given H, not speaking about efficient synthesis of H satisfying this condition. One should not think that these tractability issues concern only our algorithms which need a good contrast matrix. In fact, all conditions which allow to validate Dantzig Selector and Lasso beyond the scope of the "fully tractable" condition H s,∞ (κ) are, to the best of our knowledge, unverifiable -they cannot be checked efficiently, and thus we never can be sure that Lasso and Dantzig Selector (or any other known computationally efficient technique for sparse recovery) indeed work well for a given sensing matrix. As we have seen in Section 3, the situation improves dramatically when passing from unverifiable conditions H s,q (κ), q < ∞, to the efficiently verifiable condition H s,∞ (κ), although in a severely restricted range of values of s.

Numerical examples

We present here a small simulation study.

Regular/penalized recovery vs. Lasso: no-nuisance case

To illustrate the discussion in Section 5.3, we compare numerical performance of Lasso and penalized recovery in the observation model (1) without nuisance:

y = Ax + σξ, ξ ∼ N (0, I m ),
where σ > 0 is known. The sensing matrix A is specified by selecting at random m = 120 rows of the 128 × 128 Hadamard matrix6 , and "suppressing" the first of the selected rows by multiplying it by 1.e-3. The resulting 120 × 128 sensing matrix has orthogonal rows; 119 of its 120 singular values are equal to 8 √ 2, and the remaining singular value is 0.008 √ 2. We have processed A as explained in Section 3 (a reader is referred to this section for the description of Table 1: . Lasso vs. penalized ℓ 1 recovery. Choice of κ: * -"ideal" choice; † -theoretical choice.

entities involved). 7 We started with computing γ * , which turned out to be 0.0287, meaning that the level of s-goodness of A is at least 17. In our experiment, we aimed at recovering signals with at most s = 10 nonzero entries and with no nuisance (U = {0}). The synthesis of the corresponding "optimal" contrast matrix H = H * as outlined in Section 3 results in γ = 0.294, ω * (γ) = 0.0899 2 ln(n/ǫ). Note that we are in the case of U = {0}, and in this case the optimal H is independent of the values of σ and ǫ.

We compare the penalized ℓ 1 -recovery with the contrast matrix H * and θ = 2 with the Lasso recovery on randomly generated signals x with 10 nonzero entries. We consider two choices of the penalty κ in Lasso: the "theoretically optimal" choice (42) and the "ideal" choice, where we scanned the "fine grid" (1.05) k , k = 0, ±1, ±2, ... of values of κ and selected the value for which the Lasso recovery was at the smallest • 1 -distance from the true signal. The confidence parameter ǫ in (42) was set to 0.01. The results of a typical experiment are presented in Table 1. We see that as compared to the penalized ℓ 1 recovery, the accuracy of Lasso with the theoretically optimal choice of the penalty is nearly 10 times worse. With the "ideal" (unrealistic!) choice of penalty, Lasso is never better than the penalized ℓ 1 recovery, and for the smallest value of σ is nearly 4 times worse than the latter routine.

The nuisance case

In the second experiment we study the behavior of recovery procedures in the situation when an "input nuisance" is present:

y = A(x + v) + σξ, where x ∈ R n is an unknown sparse signal, v ∈ V with known V ⊂ R n , σ is known and ξ ∈ R m is standard normal ξ ∼ N (0, I m )
; in terms of (3), u = Av and U = AV. We compare the performance of the regular and penalized recoveries to that of the Lasso and Dantzig Selector algorithms. To handle the nuisance, the latter methods were modified as follows: instead of the standard Lasso estimator we use the estimator

x lasso (y) ∈ Argmin x∈R n min v∈V x 1 + κ A(x + v) -y 2 2 ,
where the penalization coefficient κ is chosen according to [2, Theorem 4.1]; in turn, the Dantzig Selector is substituted by

x DS (y) ∈ Argmin x∈R m min v∈V x 1 : |[A T (A(x + v) -y)] i | ≤ ̺ i , i = 1, ..., m 7
It is worth to mention that when A is comprised of (perhaps, scaled) rows of an Hadamard matrix (and in fact, of scaled rows of any other Fourier transform matrix associated with a finite Abelian group) the synthesis described in Section 3 simplifies dramatically due to the fact that all problems (P γ i ) turn out to be equivalent to each other, and their optimal solutions are obtained from each other by simple linear transformations. As a result, we can work with a single problem (P γ 1 ) instead of working with n of them.

with ̺ i = σ 2 ln(n/ǫ) A i 2 , where A i are the columns of A and ǫ is given (in what follows ǫ = 0.01).

We present below the simulation results for two setups with n = 256:

1. Gaussian setup: a 161 × 256 sensing matrix A Gauss with independent N (0, 1) entries is generated, then its columns are normalized. The nuisance set V = V(L) ⊂ R 256 is as follows:

V(L) = {v ∈ R 256 , |v i+1 -2v i + v i-1 | ≤ L, for i = 2, ..., 255, v 2 = v 1 = 0},
where L is a known parameter; in other words, we observe the sum of a sparse signal and "smooth background."

2. Convolution setup: a 240 × 256 sensing matrix A conv is constructed as follows: consider a signal x "living" on Z 2 and supported on the 16 × 16 grid Γ = {(i, j) ∈ Z 2 : 0 ≤ i, j ≤ 15}. We subject such a signal to discrete time convolution with a kernel supported on the set {(i, j) ∈ Z 2 : -7 ≤ i, j ≤ 7}, and then restrict the result on the 16 × 15 grid Γ + = {(i, j) ∈ Γ : 1 ≤ j ≤ 15}. This way we obtain a linear mapping x → A conv x : R 256 → R 240 . The nuisance set

V = V(L) ⊂ R 256 is composed of zero-mean signals u on Γ which satisfy |[D 2 u] i,j | ≤ L,
where D is the discrete (periodic) homogeneous Laplace operator:

[Du] i,j = 1 4 u i,j-1 + u i-1,j + u i,j+1 + u i+1,j -4u i,j , i, j = 1, ..., 16, with i = i mod 16, j = j mod 16.

In the simulations we acted as follows: given the sensing matrix A, the nuisance set U = AV and the values of s and σ, we compute the contrast matrix H by choosing a "reasonable" value γ > γ * of γ and specifying H as the matrix satisfying H s,∞ (sγ) and such that ν(H) = ω * (γ), see Section 3. Then N samples of random signal x, random nuisance v ∈ V and random perturbation ξ were generated, and the corresponding observations were processed by every one of the algorithms we are comparing 8 . The plots below present the average, over these N = 100 experiments, ℓ ∞ and ℓ 1 recovery errors. All recovery procedures were using Mosek optimization software [START_REF] Andersen | The MOSEK optimization tools manual[END_REF].

We start with Gaussian setup in which the signal x has s = 2 non-vanishing components, randomly drawn, with x 1 = 10. For the penalized and the regular recovery algorithms the contrast matrix H was computed using γ = 0.1. On Figure 1 we plot the average recovery error as a function of the value of the parameter L of the nuisance set V, for fixed σ = 0.1, and on Figure 2 -as a function of σ for fixed L = 0.01.

In the next experiment we fix the "environmental parameters" σ, L and vary the number s of nonzero entries in the signal x (of norm x 1 = 5s). On Figure 3 we present the recovery error as a function of s.

We run the same simulations in the convolution setup. The contrast matrix H for the penalized and the regular recoveries is computed using γ = 0.2. On Figure 4 we plot the average recovery error as a function of the "size" L of the nuisance set V for fixed σ = 0.1, on Figure 5 -as a function of σ for fixed L = 0.01, and on Figure 6 -as a function of s.

We observe quite different behavior of the recovery procedures in our two setups. In the Gaussian setup the nuisance signal v ∈ V does not mask the true signal x, and the performance of the Lasso and Dantzig Selector is quite good in this case. The situation changes dramatically in the convolution setup, where the performance of the Lasso and Dantzig Selector degrades rapidly when the parameter L of the nuisance set increases. 9 The conclusion suggested by the outlined numerical results is that the penalized ℓ 1 recovery, while sometimes losing slightly to Lasso, in some of the experiments outperforms significantly all other algorithms we are comparing.

Non-Euclidean matching pursuit algorithm

The Matching Pursuit algorithm for sparse recovery is motivated by the desire to provide a reduced complexity alternative to the algorithms using ℓ 1 -minimization. Several implementations of Matching Pursuit has been proposed in the Compressive Sensing literature (see, e.g., [START_REF] Elad | A generalized uncertainty principle and sparse representation in pairs of R n bases[END_REF][START_REF] Donoho | Optimally sparse representation in general (non-orthogonal) dictionaries via ℓ 1 minimization[END_REF][START_REF] Gribonval | Sparse representations in unions of bases[END_REF]). They are based on successive Euclidean projections of the signal and the corresponding performance results rely upon the bounds on mutual incoherence parameter µ(A) of the sensing matrix. We are about to show how the construction of Section 3 can be used to design a specific version of the Matching Pursuit algorithm which we refer to as Non-Euclidean Matching Pursuit (NEMP) algorithm. The NEMP algorithm can be an interesting option if the ℓ 1 -recovery is to be used repeatedly on the observations obtained with the same sensing matrix A; the numerical complexity of the pursuit algorithm for a given matrix A may only be a fraction of that of the recovery, especially when used on high-dimensional data. Suppose that we have in our disposal γ ≥ 0 such that the condition H(γ[1; ..., 1]) is feasible; invoking

|[I -H T A] ij | ≤ γ, ν(H) = ω * (γ), (46)
where, as always, ν(H) = max i ν(h i ) with ν(h) = ν ǫ,σ,U (h) given by ( 4).

Consider a signal x ∈ R n such that xx s 1 ≤ υ, where, as usual, x s is the vector obtained from x by replacing all but the s largest in magnitude entries in x with zeros, and let y be an observation as in [START_REF] Bühlmann | On the conditions used to prove oracle results for the Lasso Electron[END_REF].

Suppose that sγ < 1, and let υ ≥ 0 be given. Consider the following iterative procedure: (a) u = H T (y -Av (k-1) ) and vector ∆ ∈ R n with the entries

Algorithm 1 1. Initialization: Set v (0) = 0, α 0 = H T y s,1 + sν(H) + υ 1 -sγ . 2. Step k, k = 1, 2, ...: Given v (k-1) ∈ R n and α k-1 ≥ 0, compute 0
∆ i = sign(u i )[|u i | -γα k-1 -ν(H)] + , 1 ≤ i ≤ n (here [a] + = max[0, a]). (b) Set v (k) = v (k-1) + ∆ and α k = 2sγα k-1 + 2sν(H) + υ. ( 47
)
and loop to step k + 1.

3. The approximate solution found after k iterations is v (k) .

Proposition 9 Assume that sγ < 1 and an υ ≥ 0 is given. Then there exists a set Ξ ⊂ R m , Prob{ξ ∈ Ξ} ≥ 1ǫ, of "good" realizations of ξ such that whenever ξ ∈ Ξ, for every x ∈ R n satisfying xx s 1 ≤ υ and every u ∈ U , the approximate solution v (k) and the value α k after the k-th step of Algorithm 1 satisfy Note that if 2sγ < 1 then also sγ < 1 and Proposition 9 holds true. Furthermore, by (47) the sequence α k converges exponentially fast to the limit α ∞ := 2sω * (γ)+υ 1-2sγ :

(a k ) for all i v (k) i ∈ Conv{0; x i } (b k ) x -v (k) 1 ≤ α k and x -v (k+1) ∞ ≤ 2γα k + 2ω * (γ).
v (k) -x 1 ≤ α k = (2sγ) k [α 0 -α ∞ ] + α ∞ .
Along with the second inequality of (b k ) this implies the bounds:

v (k) -x ∞ ≤ 2γα k-1 + 2ω * (γ) ≤ α k s ,
and, since x p ≤ x

1 p 1 x p-1 p ∞ for 1 ≤ p ≤ ∞, v (k) -x p ≤ s 1-p p (2sγ) k [α 0 -α ∞ ] + α ∞ .
The bottom line here is as follows:

Corollary 2 Let γ < 1/(2s) be such that the condition H(γ[1; ...; 1]) is feasible, so that we can find efficiently a contrast matrix H satisfying (46). With Algorithm 1 associated with H and some υ ≥ 0, one ensures that for every t = 1, 2, ..., the approximate solution v (t) found after t iterations satisfies

Risk p (v (t) |ǫ, σ, s, υ) ≤ s 1 p 2ω * (γ)+s -1 υ 1-2sγ + (2sγ) t ω * (γ)+s -1 ( H T y s,1 +υ) 1-sγ -2ω * (γ)+s -1 υ 1-2sγ , 1 ≤ p ≤ ∞.
(cf. ( 29)).

To put this result in proper perspective, note that the mutual incoherence based condition

µ(A) 1 + µ(A) < 1 2s
underlying typical convergence results for the Matching Pursuit algorithms as applied to recovery of s-sparse signals (see, e.g. [START_REF] Elad | A generalized uncertainty principle and sparse representation in pairs of R n bases[END_REF][START_REF] Donoho | Optimally sparse representation in general (non-orthogonal) dictionaries via ℓ 1 minimization[END_REF][START_REF] Gribonval | Sparse representations in unions of bases[END_REF]) definitely is sufficient for convergence of the NEMP algorithm with γ = µ(H) µ(H)+1 , see Section 4.1. It follows that the scope of NEMP is at least as wide as that of "theoretically valid" Matching Pursuit algorithms known from the literature; in the situation in question Corollary 2 recovers some results from [START_REF] Donoho | Optimally sparse representation in general (non-orthogonal) dictionaries via ℓ 1 minimization[END_REF][START_REF] Elad | A generalized uncertainty principle and sparse representation in pairs of R n bases[END_REF][START_REF] Gribonval | Sparse representations in unions of bases[END_REF].

A Proofs

A.1 Proofs for section 2

A.1.1 Proof or Lemma 1
The first claim is evident. Now let H = [h 1 , ..., h n ] satisfy H s,∞ (κ), and let h n+i = -h i , 1 ≤ i ≤ n. Then for every i ≤ n and every x ∈ R n with x 1 ≤ 1 we have

κ s H T Ax ∞ = κ s + max λ∈R 2n + : i λ i =1 2n i=1 λ i h i T Ax ≥ x i ,
or, which is the same,

min x: x 1 ≤1 max λ∈R 2n + : i λ i =1 κ s + 2n i=1 λ i h i T Ax -x i ≥ 0.
By von Neumann lemma, this is the same as max

λ∈R 2n + : i λ i =1 min x: x 1 ≤1 κ s + 2n i=1 λ i h i T Ax -x i ≥ 0,
and the outer max clearly is achieved, meaning that there exists λ i ≥ 0,

2n j=1 λ i j = 1, such that with h ′ i = 2n j=1 λ i j h j one has κ s + [h ′ i ] T Ax -x i ≥ 0 ∀x : x 1 ≤ 1,
so that for every x with

x 1 ≤ 1 one has κ s + |[h ′ i ] T Ax| -x i ≥ 0; applying the latter inequality to -x in the role of x, we get κ s + |[h ′ i ] T Ax| ≥ |x i | whenever x 1 ≤ 1, whence, of course, κ s x 1 + |[h ′ i ] T Ax| ≥ |x i | for all x.
We conclude that the matrix

H ′ = [h ′ 1 , ..., h ′ n ] satisfies H( κ s [1; ...; 1]
). It remains to note that by construction the columns of H ′ are convex combinations of the columns of H and -H, and that building H ′ reduces to solving n matrix games and thus can be carried out efficiently.

A.1.2 Proof of Proposition 1 Let Ξ = {ξ : |h T i y| ≤ 2 ln(n/ǫ) h i 2 1 ≤ i ≤ n}, so that Prob{ξ ∈ Ξ} ≥ 1 -ǫ.
Let us fix ξ ∈ Ξ, a set I = {1, ..., n}\J ⊂ {1, ..., n} satisfying (9), a signal x ∈ R n and a realization u ∈ U of the nuisance, and let x be the value of the estimate (7) at the observation y = Ax + u + σξ. We are about to verify that x satisfies [START_REF] Donoho | Optimally sparse representation in general (non-orthogonal) dictionaries via ℓ 1 minimization[END_REF], which, of course, will complete the proof.

Observe that because of ξ ∈ Ξ we have

|h T i (Ax -y)| = |h T i (u + σξ)| ≤ max u ′ ∈U |h T i u ′ | + σ 2 ln(n/ǫ) h i 2 = ν(h i ) = ν i , 1 ≤ i ≤ n.
Now, ρ i ≥ ν i by [START_REF] Candès | The restricted isometry property and its implications for compressed sensing[END_REF], whence |h T i (y -Ax)| ≤ ρ i for all i, and thus x is a feasible solution to the optimization problem in [START_REF] Candès | The Dantzig selector: statistical estimation when p is much larger than n[END_REF] and thus x 1 ≥ x 1 . Setting z = x-x, we now have

x J 1 = x 1 -x I 1 ≤ x 1 -x I 1 ≤ x 1 -x I 1 + z I 1 = x J 1 + z I 1 , whence z J 1 ≤ x J 1 + x J 1 ≤ 2 x J 1 + z I 1 . It follows that z 1 ≤ 2 z I 1 + 2 x J . (48)
Further,

|h T i A( x -x)| ≤ |h T i (A x -y)| + |h T i (Ax -y)|. Since x is feasible for the optimization problem in (7), we have |h T i (A x -y)| ≤ ρ i ,

and we have already seen that |h

T i (Ax -y)| ≤ ν i , hence |h T i Az| ≤ ρ i + ν i (49)
for all 1 ≤ i ≤ n. Applying (5) we now get

z I 1 = i∈I |z i | ≤ i∈I [|h T i Az| + γ i z 1 ] ≤ i∈I (ρ i + ν i ) + i∈I γ i [ z I 1 + z J 1 ] = ρ I + ν I + γ I [ z I 1 + z J 1 ] ≤ ρ I + ν I + 2γ I [ z I 1 + x J 1 ] ,
where the concluding ≤ is given by (48). Taking into account that γ I < 1 2 , we get

z I 1 ≤ ρ I + ν I + 2γ I x J 1 1 -2γ I .
Invoking (48) once again, we finally get

z 1 = z I 1 + z J 1 ≤ 2 z I 1 + 2 x J 1 ≤ 2 ρ I + ν I + 2γ I x J 1 1 -2γ I + 2 x J 1 ,
and we arrive at (10.a).

To prove (10.b), we apply (5) to z = xx, thus getting

|z i | ≤ |h T i Az| + γ i z 1 .
As we have already seen, |h T i Az| ≤ ρ i + ν i , and the first "≤" in (10.b) follows; the second "≤" in (10.b) is then readily given by (10.a). Now (ii) and (iii) are immediate consequences of [START_REF] Donoho | Optimally sparse representation in general (non-orthogonal) dictionaries via ℓ 1 minimization[END_REF] and the fact that γ s ≤ s γ.

A.1.3 Proof of Lemma 2

In what follows, we use the notation from Proposition 1. For x ∈ X(s, υ), denoting by I the support of x s , we have

x J 1 ≤ υ, ρ I ≤ ρ s ≤ s ρ, ν I ≤ ν s ≤ sν(H), γ I ≤ ν s ≤ s γ.
Assuming γ s < 1 2 , for ξ ∈ Ξ (which happens with probability ≥ 1ǫ), [START_REF] Gribonval | Sparse representations in unions of bases[END_REF] implies that for all u ∈ U it holds

x reg (y) -x 1 ≤ 2 1 -2 γ s [υ + ρ s + ν s ] P , and
x reg (y) -x ∞ ≤ ρ + ν(H) + 2 γ υ + ρ s + ν s 1 -2 γ s Q ,
which combines with the standard bound z p ≤ z

1 p 1 z p-1 p
∞ to imply [START_REF] Juditsky | Nonparametric estimation by convex programming[END_REF]. When s γ < 1 2 , we clearly have

P ≤ 2 1 -2s γ [υ + s( ρ + ν(H))], Q ≤ ρ + ν(H) + 2 γ 1 -2s γ [υ + s( ρ + ν(H))] = 2 1 -2s γ [ γυ + 1 2 [ ρ + ν(H)]],
and ( 14) follows due to x reg (y) -

x p = P 1 p Q p-1 p . A.1.4 Proof of Proposition 2
The proof is obtained by minor modifications from the one of Proposition 1. Same as in the latter proof, let Ξ = {ξ :

|h T i y| ≤ 2 ln(n/ǫ) h i 2 1 ≤ i ≤ n}, where h i are the columns of H, so that Prob{ξ ∈ Ξ} ≥ 1 -ǫ. Let us fix ξ ∈ Ξ, x ∈ R n , u ∈ U , let η = σξ + u, y = Ax + η, x = x reg (y), z = x -x. Finally, let I be the support of x s .
Due to ξ ∈ Ξ, we have

|h T i (Ax -y)| = |h T i (u + σξ)| ≤ max u ′ ∈U |h T i u ′ | + σ 2 ln(n/ǫ) h i 2 = ν(h i ) = ν i , 1 ≤ i ≤ n,
whence, by (8), x is a feasible solution to the optimization problem in [START_REF] Candès | The Dantzig selector: statistical estimation when p is much larger than n[END_REF] and thus x 1 ≥ x 1 . The latter, exactly as in the proof of Proposition (1), implies the validity of (48):

z 1 ≤ 2 z I 1 + 2 x J 1 . (50)
Besides this, the same reasoning as in the proof of Proposition 1 results in (49), whence

H T Az ∞ ≤ ρ + ν(H). (51)
Applying [START_REF] Candès | Stable signal recovery from incomplete and inaccurate measurements[END_REF] to z, we get

z I 1 ≤ s z ∞ ≤ s H T Az ∞ + κ z 1 ≤ s( ρ + ν(H)) + κ z 1 ,
which combines with (50) to imply that

z 1 ≤ 1 1 -2κ [2s( ρ + ν(H)) + 2 x J 1 ] , (52)
which is nothing but the first relation in [START_REF] Juditsky | Verifiable conditions of ℓ 1 -recovery of sparse signals with sign restrictions[END_REF]. Applying to z (6) once again, we get

z ∞ ≤ H T Az ∞ + s -1 κ z 1 ,
which combines with (52) to imply the second relation in [START_REF] Juditsky | Verifiable conditions of ℓ 1 -recovery of sparse signals with sign restrictions[END_REF]. Relation [START_REF] Juditsky | Verifiable conditions of ℓ 1 -recovery of sparse signals with sign restrictions[END_REF] combines with the Moment inequality to imply [START_REF] Koltchinskii | The Dantzig selector and sparsity oracle inequalities[END_REF].

A.1.5 Proof of Proposition 3 (i): Given σ, ǫ, let, same as in the proof of Proposition 1, Ξ = {ξ : |h T i ξ| ≤ 2 ln(n/ǫ) h i 2 , 1 ≤ i ≤ n}, so that Prob{ξ ∈ Ξ} ≥ 1ǫ. Let us fix ξ ∈ Ξ, u ∈ U and a signal x ∈ R n , and let us prove that for these data [START_REF] Zhang | Some sharp performance bounds for least squares regression with L 1 regularization[END_REF] takes place; this clearly will prove (i). Let us set y = Ax + σξ + u, x = x pen (y), z = xx, η = u + σξ. Let also I be the support of x s .

Observe that by the origin of x, we have

x 1 + sθ H T (A x -y) ∞ ≤ x 1 + sθ H T (Ax -y) ∞ = x 1 + sθ H T η ∞ , (53)
and

H T (A x -y) ∞ = H T (Az + Ax -y) ∞ ≥ H T Az ∞ -H T (Ax -y) ∞ = H T Az ∞ -H T η ∞ .
Combining the resulting inequality with (53), we get

x 1 + sθ H T Az ∞ ≤ x 1 + 2sθ H T η ∞ ≤ x 1 + 2sθν(H), (54)
where the concluding ≤ is due to ξ ∈ Ξ combined with [START_REF] Zhang | The sparsity and bias of the Lasso selection in highdimensional linear regression[END_REF]. Further,

x 1 = x + z 1 = x I + z I 1 + x J + z J 1 ≥ x I 1 -z I 1 + z J 1 -x J 1 ,
which combines with (54) to imply that

x I 1 -z I 1 + z J 1 -x J 1 + sθ H T Az ∞ ≤ x 1 + 2sθν(H),
or, which is the same,

z J 1 -z I 1 + sθ H T Az ∞ ≤ 2 x J 1 + 2sθν(H). (55)
By ( 5), we have ∀i :

|z i | ≤ H T Az ∞ + γ i z 1 , (56)
whence z I 1 ≤ s H T Az ∞ + γ s z 1 and therefore

(1 -γ s ) z I 1 -γ s z J 1 -s H T Az ∞ ≤ 0.
Multiplying the latter inequality by θ and summing up with (55), we get

[θ(1 -γ s ) -1] z I 1 + (1 -θ γ s ) z J 1 ≤ 2 x J 1 + 2sθν(H).
In view of condition [START_REF] Van De Geer | The deterministic Lasso[END_REF], the coefficients in the left hand side are positive, and (21.a) follows.

To prove (21.b), note that from (54) it follows that

H T Az ∞ ≤ 1 sθ [ x 1 -x 1 ] + 2ν(H) ≤ 1 sθ z 1 + 2ν(H),
which combines with (56) to imply that

z ∞ ≤ 1 sθ z 1 + 2ν(H) + γ z 1 .
Recalling that z = xx and invoking (21.a), (21.b) follows.

(ii)-(iii): ( 22) is an immediate consequence of ( 21) due to γ s ≤ s γ. Assuming that x ∈ X(s, υ) and θ = 2 and taking into account that γ s ≤ s γ, we obtain from ( 22) that uniformly on ξ ∈ Ξ and u ∈ U

xreg (y) -x 1 ≤ 2υ + 4sν(H) 1 -2s γ P , xreg (y) -x ∞ ≤ (s -1 + 2 γ)υ + 4ν(H) 1 -2s γ Q .
Using, as in the proof of Lemma 2, the standard bound

z p ≤ z 1 p 1 z p-1 p ∞ ≤ P 1 p Q p-1 p
we come to (23).

A.1.6 Proof of Proposition 4

The proof is obtained by minor modifications from the one of Proposition 1. Same as in the latter proof, let Ξ = {ξ : |h T i ξ| ≤ 2 ln(n/ǫ) h i 2 , 1 ≤ i ≤ n}, so that Prob{ξ ∈ Ξ} ≥ 1ǫ. Let us fix ξ ∈ Ξ, u ∈ U and a signal x ∈ R n . Let us set y = Ax + σξ + u, x = x pen (y), z = xx, η = u + σξ. Let also I be the support of x s .

Observe that by the origin of x and due to θ = 2 we have

x 1 + sθ H T (A x -y) ∞ ≤ x 1 + sθ H T (Ax -y) ∞ = x 1 + 2s H T η ∞ , (57)
and

H T (A x -y) ∞ = H T (Az + Ax -y) ∞ ≥ H T Az ∞ -H T (Ax -y) ∞ = H T Az ∞ -H T η ∞ .
Combining the resulting inequality with (57), we get

x 1 + 2s H T Az ∞ ≤ x 1 + 4s H T η ∞ ≤ x 1 + 4sν(H), (58)
where the concluding ≤ is due to ξ ∈ Ξ combined with the definition of ν(H). Further,

x 1 = x + z 1 = x I + z I 1 + x J + z J 1 ≥ x I 1 -z I 1 + z J 1 -x J 1 ,
which combines with (58) to imply that

x I 1 -z I 1 + z J 1 -x J 1 + 2s H T Az ∞ ≤ x 1 + 4sν(H),
or, which is the same,

z J 1 -z I 1 + 2s H T Az ∞ ≤ 2 x J 1 + 4sν(H). ( 59
)
By [START_REF] Candès | Stable signal recovery from incomplete and inaccurate measurements[END_REF] we have

z ∞ ≤ H T Az ∞ + κ s z 1 , (60)
whence z I 1 ≤ s H T Az ∞ + κ z 1 and therefore

(1 -κ) z I 1 -κ z J 1 -s H T Az ∞ ≤ 0.
Multiplying the latter inequality by 2 and summing up with (59), we get

(1 -2κ) z 1 ≤ 2 x J 1 + 4sν(H),
and the first relation in (24). The second relation in ( 24) is readily given by the first one combined with [START_REF] Candès | Stable signal recovery from incomplete and inaccurate measurements[END_REF]. We have proved that (24) holds true whenever ξ ∈ Ξ; since Prob{ξ ∈ Ξ} ≥ 1ǫ, (25) follows.

A.2 Proofs for sections 3, 4

A.2.1 Proof of Lemma 3

(i)⇒(iii): If h i satisfies (P i ), then for every x we have

|x i | ≤ |h T i Ax| + γ x 1 ≤ ωϕ * (Ax) + γ x 1 ,
where the first and the second inequalities are given by (P i .b) and (P i .a), respectively. (iii)⇒(ii): Assume that (iii) takes place; then, by homogeneity, ωϕ * (Ax) + γ ≥ x i for every x with x 1 ≤ 1, or, which is the same, the optimal value in the conic problem min

x {ωϕ * (Ax) -x i : x 1 ≤ 1} is ≥ -γ.
The problem clearly is strictly feasible and bounded, so that by Conic Duality Theorem the dual problem is solvable with the same optimal value. Now, the dual problem reads max g,h,s

{-s : ϕ(h) ≤ ω, g ∞ ≤ s, A T h + g = e i },
and the fact that it is solvable with the optimal value ≥ -γ means that there exist h, g such that ϕ(h) ≤ ω, g ∞ ≤ γ and A T h + g = e i , whence h is a feasible solution to (P γ i ) with the value of the objective ≤ ω. (ii)⇒(i): If (P γ i ) is feasible, it clearly is solvable; thus, in the case of (ii) there exists h with ϕ(h) ≤ ω and A T he i ∞ ≤ γ. From the latter inequality it follows that |e T i xh T Ax| ≤ γ x 1 for every x, so that |x i | -|h T Ax| ≤ γ x 1 for all x. We see that h satisfies (P i ), and thus (i) takes place. This reasoning shows also that whenever (P γ i ) is feasible with optimal value ≤ ω, it is solvable, and its optimal solution satisfies (P i ).

A.2.2 Proof of Proposition 5

Let γ = γ(δ, k), λ = r(U ) + σ 2 ln(n/ǫ), so that what we need to prove is that there exists a matrix H satisfying H s,∞ (γ) and such that ν(H) ≤ λ. Invoking Lemma 3, all we need to this end is to show that

∀x ∈ R n : x ∞ ≤ 1 √ 1 -δ λν * (Ax) + γ x 1 (61)
Now, we clearly have ν(h) ≤ max u∈U u T h + σ 2 ln(n/ǫ) h 2 ≤ λ h 2 for all h, whence φ * (η) ≥ λ -1 η 2 for all η. Therefore all we need in order to justify (61) is to prove that

∀s ∈ R n : x ∞ ≤ 1 √ 1 -δ Ax 2 + γ x 1 . (62)
Let x ∈ R n . Setting s = floor(k/2), let vectors x 1 , ..., x q be obtained from x by the procedure as follows: x 1 is obtained by zeroing all but the s largest in magnitude entries of x; x 2 is obtained by the same procedure from xx 1 , x 3 is obtained by the same procedure from xx 1x 2 , and so on, until the step q where we get x = x 1 + ... + x q . We clearly have x j ∞ ≤ s -1 x j-1 1 , 2 ≤ j ≤ q, whence also x j 2 ≤ s -1/2 x j-1 1 , 2 ≤ j ≤ q, since the vectors x j are s-sparse. Setting Ax 2 = α and Ax 1 2 = β, we have

αβ = Ax 2 Ax 1 2 ≥ (Ax) T Ax 1 = [x 1 ] T A T Ax 1 + q j=2 [x 1 ] T A T Ax j ≥ β 2 - q j=2 δ x 1 2 x j 2 ,
where the last ≥ is given by the following well-known fact: [START_REF] Candès | The restricted isometry property and its implications for compressed sensing[END_REF]: It follows that

(!) If A is RIP(δ,
αβ ≥ β 2 -δ x 1 2 q j=2 x j 2 ≥ β 2 -δs -1/2 x 1 2 q j=2 x j-1 1 ≥ β 2 -δs -1/2 x 1 2 x 1 . Hence β ≤ α + δ x 1 x 1 2 √ sβ ≤ α + δ x 1 s(1 -δ) ,
where the second inequality is due to the fact that x 1 2 /β ≤ 1/ √ 1δ by RIP. Thus,

x ∞ ≤ x 1 2 ≤ β √ 1 -δ ≤ α √ 1 -δ + δ x 1 (1 -δ) √ s ≤ α √ 1 -δ + γ x 1 ,
where the concluding inequality is due to s ≥ (k -1)/2 and γ = γ(δ, k). Recalling that α = Ax 2 , (62) follows.

A.2.3 Proof of Proposition 6

Proof. We start with analysis of O(S, ω). Let i ∈ {1, ..., n}, and let I ∋ i be a subset of {1, ..., n} of cardinality S. Let R (S) be the linear space of all vectors from R n supported on I, and let X R = {x ∈ R (S) :

x 2 ≤ R}. Assume that we are given a noisy observation y = Ax + u + σξ of a signal z = (x, u) ∈ (X R , U ), and that we want to recover from this observation the linear form x i of the signal. From O(S, ω) it follows that there exists a recovering routine such that for every x ∈ X R and u ∈ U the probability of recovering error to be ≥ ω is ≤ ǫ. Assuming ǫ ≤ 1/16 and applying the celebrated result of Donoho [START_REF] Donoho | Statistical estimation and optimal recovery[END_REF], there exists a linear estimate φ T R y such that for every x ∈ X R and u ∈ U the probability for the error of this estimate to be ≥ 1.22ω is ≤ ǫ. Moreover (cf. Proposition 4.2 of [START_REF] Juditsky | Nonparametric estimation by convex programming[END_REF]), one can pick φ R such that

∀x ∈ X R , u ∈ U , Prob{φ T R [u + σξ + A I x] -x i > 1.22ω} ≤ ǫ/2, (a) Prob{φ T R [u + σξ + A I x] -x i < -1.22ω} ≤ ǫ/2, (b)
where A I is the matrix obtained from A by zeroing columns with indexes not belonging to

I. Let p(R) = max u∈U |φ T R u| and r(R) = A T I φ R -e i 2
, where e i is the i-th basic orth (so that x i = e T i x). Specifying x as the vector from X R such that xT (A T I φ Re i ) = Rr(R), and ū as the vector from U such that φ T R ū = p(R) (the required x, ū clearly exist) and applying (a) to the pair (x, u) = (x, ū), and (b) to the pair (x, u) = (-x), -ū), we get Prob{σφ

T R ξ > 1.22ω -Rr(R) -p(R)} ≤ ǫ/2, Prob{σφ T R ξ < -1.22ω + Rr(R) + p(R)} ≤ ǫ/2.
Hence, denoting by erfinv(ǫ) the value of the inverse error function at ǫ, we obtain

erfinv ǫ 2 σ φ R 2 ≤ 1.22ω -Rr(R) -p(R).
It follows that as R → ∞, φ R remains bounded and r(R) = e i -A T I φ R 2 → 0. Thus, there exists a sequence R k → +∞, of values of R such that φ R k goes to a limit φ as k → ∞, and this limit satisfies the relations erfinv ǫ 2 σ φ 2 ≤ 1.22ω, and A T I φ = e i .

Taking into account that erfinv ǫ 2 ≥ 0.92 ln(1/ǫ) when ǫ ≤ 1/16, we arrive at the following result:

Lemma 6 Under assumption O(S, ω), for every i ≤ n and every S-element subset I ∋ i of {1, ..., n} there exists φ ∈ R m such that φ T a i = 1, φ T a j = 0 for all j ∈ I, j = i (here a 1 , ..., a n are the columns of A), and

max u∈U |u T φ| + σ ln(1/ǫ) φ 2 ≤ √ 2ω. ( 63
)
We claim that in this case for all x ∈ R n it holds:

x ∞ ≤ ων * (Ax) + γ ω A σ 2S ln(1/ǫ) x 1 . (64)
Taking this claim for granted, and invoking Lemma 3, we immediately arrive at the desired conclusion. Indeed, given s satisfying (32), we have It remains to prove (64). Let us fix x ∈ R n , and let I be set of indices of the S largest in magnitude entries in x. Denoting by J the complement of I in {1, ..., n}, we have x J ∞ ≤ S -1 x I 1 , whence

x J 2 ≤ x J 1/2 ∞ x J 1/2 1 ≤ S -1/2 x I 1/2 1 x J 1/2 1 ≤ 1 2 S -1/2 x 1 . (65)
Let i * ∈ I be the index of the largest in magnitude entry of x. By Lemma 6 there exists φ ∈ R m satisfying (63) and such that φ T a i * = sign(x i * ), φ T a i = 0 for i ∈ I\{i * }. We have

ν(φ) ≡ ν ǫ,σ,U (φ) = max u∈U u T φ + σ 2 ln(n/ǫ) φ 2 ≤ 2[1 + ln(n)/ ln(1/ǫ)] max u∈U u T φ + σ ln(1/ǫ) φ 2 ≤ 2 1 + ln(n)/ ln(1/ǫ)ω, (66)
where the concluding ≤ is given by (63). Now,

ν(φ)ν * (Ax) ≥ φ T Ax = φ T Ax I + φ T Ax J = |x i * | + φ T Ax J = x ∞ + φ T Ax J ≥ x ∞ -φ 2 Ax J 2 ≥ x ∞ -φ 2 A x J 2 ≥ x ∞ - 1 2 A S -1/2 φ 2 x 1 ,
with the concluding ≤ given by (65). The resulting inequality, in view of (66) and the bound

φ 2 ≤ √ 2ω σ √ ln(1/ǫ)
given by (63) implies (64).

A.3 Proofs for section 5

A.3.1 Proof of Lemma 4

Recall (cf., e.g., Theorem 2.1 in [START_REF] Juditsky | On verifiable sufficient conditions for sparse signal recovery via ℓ 1 minimization[END_REF]) that a necessary and sufficient condition for an m × n matrix A to be s-good is the nullspace property as follows: there exists κ < 1/2 such that

x s,1 ≤ κ x 1 ∀(x ∈ R n , Ax = 0). ( 67
)
Assume that this condition is satisfied, and let u ∈ R n be a vector with s nonzero coordinates, equal to ±1.

(67) says that the optimal value in the Linear Programming problem max x u T x : Ax = 0, x 1 ≤ 1 is at most κ; passing to the dual problem, we conclude that there exist h u and g u such that A T h u + g u = u and g u ∞ ≤ κ, whence for every x ∈ R n it holds

u T x = x T A T h u + g T u x ≤ h u 1 Ax ∞ + κ x 1 .
Since the set U of the outlined vectors u is finite, the quantity L = max u∈U h u 1 is finite, and

x s,1 = max u∈U u T x ≤ L Ax ∞ + κ x 1 ∀x, meaning that the condition H s,1 (κ) holds true for H = [LI m , 0 m×n-m ].
Vice versa, the existence of κ < 1/2 and H satisfying H s,q (κ) clearly implies the validity of (67) with the same κ and this implies the s-goodness of A.

A.3.2 Proof of Lemma 5

Let A satisfy RIP(δ, 2s) with δ < 1; we want to prove that then the matrix 1 1-δ A satisfies the condition H s,2 ( δ 1-δ ). Indeed, let x ∈ R n . Let vectors x 1 , x 2 , ..., x q be obtained from x as follows: x 1 is obtained by zeroing all but the s largest in magnitude entries of x and keeping the latter entries intact, then x 2 is obtained by applying the same procedure to xx 1 , and so on. We stop at step q where we get x = x 1 + ... + x q . Observe that x j ∞ ≤ 1 s x j-1 1 , whence also x j 2 ≤ x j-1 1 s -1/2 (since x j is s-sparse). We now have

√ s x 1 2 A T Ax ∞ ≥ x 1 1 A T Ax ∞ ≥ [x 1 ] T A T Ax = [x 1 ] T A T Ax 1 + q j=2 [x 1 ] T A T Ax j ≥ (1 -δ) x 1 2 2 -δ q j=2 x 1 2 x j 2 ( * ) ≥ (1 -δ) x 2 2 2 -δs -1/2 q j=2 x 1 2 x j-1 1 ≥ (1 -δ) x 2 2 2 -δs -1/2 x 1 2 x 1 ⇒ x s,2 = x 1 2 ≤ 1 1 -δ A T Ax ∞ + δ 1 -δ x 1 (in the above chain, step ( * ) is valid due to [x 1 ] T A T Ax 1 ≥ (1 -δ) x 1 2 (since A is RIP(δ, 2s
)) and the statement (!), see the proof of Proposition 5). The concluding inequality in the chain says that 1 1-δ A satisfies H s,2 ( δ 1-δ ).

A.3.3 Proof of Proposition 7

We present here the proof of (i), which is a straightforward modification of the proof of Proposition 2. The proof of (ii) can be obtained by equally straightforward modification of the proof of Proposition 4. Thus, suppose we are under the premise of (i), and let Ξ be defined exactly as in the proof of Proposition 1, so that Prob{ξ ∈ Ξ} ≥ 1ǫ and |(σξ + u) T h i | ≤ ν ǫ,σ,U (h i ) ≤ ν(H) for all ξ ∈ Ξ, u ∈ U and all i. Let us fix x ∈ R n , ξ ∈ Ξ and u ∈ U , let I be the set of indices of the s largest in magnitude entries in x, and let η = σξ + u, y = Ax + η, x = x reg (y), and z = xx.

Since ξ ∈ Ξ and u ∈ U , we have |h T i (Axy)| ≤ ν i ≤ ρ i for all i, whence x is a feasible solution to the optimization problem defining x, whence, exactly as in the proof of Proposition 1, (a)

z 1 ≤ 2 z I 1 + 2 x J 1 , (b) |h T i Az| ≤ ρ i + ν i , 1 ≤ i ≤ n ⇒ H T Az ∞ ≤ ρ + ω. (68)
Now, H satisfies the condition H s,q (κ) and thus satisfies the condition H s,1 (κ). Applying the latter condition, we get z I 1 ≤ s H T Az ∞ + κ z 1 .

Invoking (68), we conclude that

z 1 ≤ 2s H T Az ∞ + 2κ z 1 + 2 x J 1 ≤ 2s[ ρ + ω + s -1 x J 1 ] + 2κ z 1 , (69)
thus

z 1 ≤ 2s 1 -2κ [ ρ + ω + s -1 x J 1 ]. (70)
Next, H satisfies H s,q (κ), whence z s,q ≤ H T Az ∞ + κ z 1 . Therefore, we get from (68):

z s,q ≤ s 1 q H T Az ∞ + κs 1 q -1 z 1 ≤ s 1 q [ ρ + ω] + 2κs 1 q ρ + ω + s -1 x J 1 1 -2κ (71)
≤ s

1 q ρ + ω + 2κs -1 x J 1 1 -2κ ≤ s 1 q ρ + ω + s -1 x J 1 1 -2κ . ( 72
)
All we need in order to extract (i) from ( 69) and ( 72) is to verify that 1 ≤ p ≤ q ⇒ z p ≤ (3s) 1/p θ, θ = ρ + ω + s -1 x J 1 1 -2κ .

The desired inequality holds true when p = 1 (see (69)), thus, invoking the Hölder inequality, all we need is to verify that z q ≤ (3s) 1/q θ. (73)

When q = ∞, (73) is implied by (72), so let us assume that q < ∞. Let λ be the (s + 1)-st largest of the magnitudes of entries in z. By (72) we have λ q s ≤ z q s,q ≤ sθ q , and λ ≤ θ. Hence, setting z ′ = zz s , we get z ′ q q ≤ λ q-1 z ′ 1 ≤ θ q-1 z 1 ≤ θ q-1 2sθ, where the concluding inequality is given by (69). Thus, z ′ q q ≤ 2sθ q , while z s q q ≤ sθ q by (72). We see that z q q ≤ z s q q + z ′ q q ≤ 3sθ q , as required in (73). x ∈ R n , and let y = Ax + σξ, x = x DS (y). We have A T (Axy) ∞ = A T σξ ∞ ≤ ̺ ≤ ρ, so that x is a feasible solution to the optimization problem specifying x DS (y) and therefore x 1 ≤ x 1 . Denoting by I the support of x s , setting z = xz and acting exactly as when deriving (48), we arrive at

z 1 ≤ 2 z I 1 + 2 x J 1 . (74)
Further,

A T Az ∞ = A T (A x -y + σξ) ∞ ≤ A T σξ ∞ + A T (A x -y) ∞ ≤ ρ + ̺,
and therefore

Az 2 2 = z T A T Az ≤ z 1 A T Az ∞ ≤ (ρ + ̺) z 1 . (75)
On the other hand, by (37) we have

z I 1 ≤ z s,1 ≤ s 1-1 q z s,q ≤ s λ Az 2 + κ z 1 ≤ s λ(ρ + ̺) 1/2 z 1/2 1 + κ z 1 .
Substituting the above bound into (74), we get

z 1 ≤ 2κ z 1 + 2s λ(ρ + ̺) 1/2 z 1/2 1 + 2 x J 1 ,
whence by elementary calculations

τ := z 1/2 1 ≤ a + b 1/2 , where a = 2s λ √ ρ + ̺ 1 -2κ , b = 2 x J 1 1 -2κ . (76)
Invoking ( 37) and (75), we have z s,q ≤ s 1 q λ Az 2 + κs

1 q -1 z 1 ≤ s 1 q -1 s λ √ ρ + ̺ z 1/2 1 + κ z 1 = s 1 q -1 (1 -2κ) 2 aτ + κτ 2 ≤ s 1 q -1 1 -2κ 2 a 2 + 1 -2κ 2 ab 1/2 + κ[a + b 1/2 ] 2 ≤ s 1 q -1 a 2 2 + 1 + 2κ 2 ab 1/2 + κb ≤ s 1 q -1 2 [a + b 1/2 ] 2 , (77)
where the last inequality of the chain is due to κ < 1 2 . Assuming for a moment that 1 < q < ∞ and denoting by µ the (s + 1)-st largest magnitude of entries in z, we conclude from the latter inequality that µ ≤ 1 2s [a+b 1/2 ] 2 . Hence, when setting z ′ = z -z s we obtain (cf. the verification of (73)) z ′ q q ≤ µ q-1 z ′ 1 ≤ (2s) 1-q [a + b 1/2 ] 2q . Invoking (77) one more time we get z q q ≤ z s q q + z ′ q q ≤ 3 2 (2s) 1-q [a + b 1/2 ] 2q .

The resulting inequality combines with (76) and the Hölder inequality to imply that

z p ≤ 3 1 p s 1 p -1 2 [a + b 1/2 ] 2 ≤ 3 1 p s 1 p -1 [a 2 + b], 1 ≤ p ≤ q. ( 78
)
Note that the derivation of (78) was carried out under the additional assumption that 1 < q < ∞. This assumption can now be removed: when q = 1, (78) is readily given by (76). When q = ∞, A satisfies (37) for q = ∞ and thus -for every value of q from [1, ∞], meaning that (78) holds true for every q < ∞, whence (78) holds true for q = ∞ as well.

Recalling that relation (78) is valid whenever ξ ∈ Ξ and x ∈ R n and plugging in the values of a and b, we arrive at (40). (i) is proved.

(ii): Same as above, let Ξ = {ξ : |a T i ξ| ≤ 2 ln(n/ǫ) a i 2 , 1 ≤ i ≤ n}, so that Prob{ξ ∈ Ξ} ≤ ǫ. Let us fix x ∈ R n , ξ ∈ Ξ, and let I be the support of x s . Let also y = Ax + σξ, x = x lasso (y), z = xx. We have

x 1 + κ A x -y 2 2 ≤ x 1 + κ Ax -y 2 2 ≤ x 1 + σ 2 κξ T ξ,
or, which is the same due to A xy = Azσξ,

x 1 + κ Az 2 2 -2σκξ T Az ≤ x 1 .
It follows that 0 ≥ x 1x 1 + κ( Az 2 2 -2σξ T Az) = ( x I + z I 1x I 1 ) + ( x J + z J 1x J 1 ) + κ( Az 2 2 -2σξ T Az)

≥ -z I 1 + z J 1 -2 x J 1 + κ( Az 2 2 -2σξ T Az) ≥ -z I 1 + z J 1 -2 x J 1 -2κ̺ z 1 + κ Az 2 2 ,
where the last ≥ is readily given by the fact that A T σξ ∞ ≤ ̺ for ξ ∈ Ξ. We conclude that

z J 1 ≤ z I 1 + 2κ̺ z 1 -κ Az 2 2 + 2 x J 1 ,
and therefore

z 1 ≤ 2 z I 1 + 2κ̺ z 1 -κ Az 2 2 + 2 x J 1 . (79)
Now, we have z I 1 ≤ s 1-1 q z s,q ≤ s λ Az 2 + κ z 1 ,

where the concluding inequality is given by (37). Combining the resulting inequality with (79), we get

z 1 (1 -2κ -2κ̺) ≤ 2s λ Az 2 -κ Az 2 2 + 2 x J 1 .
Combining this inequality with (79), we get the first inequality in the following chain:

z 1 ≤ 2(κ + κ̺) z 1 + 2 x J 1 + κ 2 Az 2 s λ κ -Az 2 2 (80)
≤ 2(κ + κ̺) z 1 + 2 x J 1 + s 2 λ 2 κ and since 2κ + 2κ̺ < 1, we arrive at

z 1 ≤ a := 1 1 -2(κ + κ̺) s 2 λ 2 κ + 2 x J 1 . (81)
Since 2(κ + ̺κ) < 1, the first inequality in (80) is possible only if

Az 2 2 - 2s λ κ Az 2 - 2 x J 1 κ ≤ 0, whence Az 2 ≤ 2s λ κ + x J 1 s λ . (82)
Invoking (37), we get z s,q ≤ s 1 q -1 s λ Az 2 + κ z 1 , which combines with (82) and (81) to imply that z s,q ≤ 2s 1 q -1 a.

(83) and (a k ) holds. Further, let I be the support of x s . Relation (a k ) clearly implies that |z

Figure 1 :Figure 2 :

 12 Figure 1: Mean recovery error as a function of the nuisance magnitude L. Gaussian setup parameters: σ = 0.1, s = 2, µ = 0.1, x 1 = 10.

Figure 5 :

 5 Figure 5: Mean recovery error as a function of the noise StD σ. Convolution setup parameters: L = 0.01, s = 2, γ = 0.2, x 1 = 10.

Figure 6 :

 6 Figure 6: Mean recovery error as a function of the number s of nonzero entries in the signal. Convolution setup parameters: L = 0.01, σ = 0.1, γ = 0.2, x 1 = 5s.

Figure 7 :

 7 Figure 7: A typical signal/worst Lasso nuisance. Gaussian setup with parameters: L = 0.05, σ = 0.1, s = 2, x 1 = 10, γ = 0.1.

Figure 8 :

 8 Figure 8: A typical signal/recovery in Convolution setup. Parameters: L = 0.025, σ = 0.1, s = 2, x 1 = 10, γ = 0.2.

  k) and u, v are supported on a common set of indices I of cardinality k and are orthogonal, then |u T A T Av| ≤ δ u 2 v 2 .

A. 3 . 4

 34 Proof of Proposition 8 (i): Let Ξ = {ξ ∈ R m : |ξ T a i | ≤ ̺, 1 ≤ i ≤ n}, so that Prob{ξ ∈ Ξ} ≥ 1ǫ. Let us fix ξ ∈ Ξ and

-

  |x i |, and we can write due to (87.b): ∆i | + i ∈I |x i | ≤ sℓ + υ = α k .Since by (87.b)xv (k) ∞ = xv (k-1) -∆ ∞ ≤ ℓ = 2γα k-1 + 2ω * (γ),we conclude that (b k ) holds true. The induction step is justified. It remains to show that (a 0 , b 0 ) holds true. Since (a 0 ) is evident, all we need is to justify (b 0 ). Letα * = x 1 ,and let u = H T y. Same as above (cf. (86)), we have for all i:|x iu i | ≤ γα * + ω * (γ).Thenα * = i∈I |x i | + i ∈I |x i | ≤ i∈I [|u i | + γα * + ω * (γ)] + υ ≤ u s,1 + sγα * + sω * (γ) + υ. Hence α * ≤ α 0 = u s,1 + sω * (γ) + υ 1sγ ,which implies (b 0 ).

  by Lemma 1, if H ′ satisfies H s,∞ (κ) and ϕ(H ′ ) ≤ ω, then there exists H = [h 1 , ..., h n ] such that h i satisfy (P i .b) for all i and ϕ(H) ≤ ϕ(H ′ ) ≤ ω, so that h i satisfy (P i .a) for all i as well. Vice versa, if h i satisfy (P i ), 1 ≤ i ≤ n, then the matrix H = [h 1 , ..., h n ] clearly satisfies H s,∞ (κ), and ϕ(H) ≤ ω.

  Mean recovery error as a function of the number s of nonzero entries in the signal. Gaussian setup parameters: L = 0.01, σ = 0.1, γ = 0.1, x 1 = 5s.

	2									12
	1.8											Lasso
										10		Dantzig Selector
	1.6											Penalized Recovery Regular Recovery
	1.4		Dantzig Selector Lasso					8		sρ-bound
			Penalized Recovery
	1.2		Regular Recovery					6
			ρ-bound
	1
										4
	0.8
										2
	0.6
	0.4	1	2	3	4	5	6	7	8	0	1	2	3	4	5	6	7	8
					ℓ ∞ -error								ℓ 1 -error
	0 1 2 3 4 5 7 8 Figure 3: 0 6	0.02	0.04	0.06	0.08	0.1 Regular Recovery 0.12 ρ-bound Lasso Penalized Recovery Dantzig Selector	0.14	1 2 3 4 5 6 7 10 11 9 8	0	0.02	0.04	0.06	0.08	0.1 Lasso Dantzig Selector 0.12 Penalized Recovery 0.14 Regular Recovery sρ-bound

ℓ ∞ -error ℓ 1 -error Figure 4: Mean recovery error as a function of the nuisance magnitude L. Convolution setup parameters: σ = 0.1, s = 2, γ = 0.2, x 1 = 10. Lemma 3, in this case we can find efficiently a contrast matrix H = [h 1 , ..., h n ] such that

With "theoretically optimal," rather than "ideal," choice of the regularization parameter in Lasso, this algorithm is essentially worse than our algorithms utilizing the contrast matrix.

The reason for this cumbersome, at the first glance, notation will become clear later, in Section

And even less than that, since feasibility of Hs,q(κ) is just a sufficient condition for the validity of (37), the condition which indeed underlies Proposition 8.

The k-th Hadamard matrix H k is given by the recurrenceH 0 = 1, H p+1 = [H p ; H p ; H p , -H p ]. It is a 2 k × 2 kmatrix with orthogonal rows and all entries equal to ±1.

Randomness of the sparse signal x important. Using the techniques of[START_REF] Juditsky | On verifiable sufficient conditions for sparse signal recovery via ℓ 1 minimization[END_REF], one can verify that in the convolution setup there are signals with only 3 non-vanishing components which cannot be recovered by ℓ1 minimization even in the noiseless case V = {0}, σ = 0. In other words, the s-goodness characteristic of the corresponding matrix A is equal to 2.

The error plot for these estimators on Figure4flatters for higher values of L simply because they always underestimate the signal, and the error of recovery is always less than the corresponding norm of the signal.

* Research of the second author was supported by the Office of Naval Research grant # N000140811104 and the NSF grant DMS-0914785.

Denoting by µ the (s + 1)-st largest of the magnitudes of entries in z, we conclude from (83) that µ ≤ 2s -1 a, whence, denoting z ′ = zz s ,

(we have used (81)), which combines with (83) to imply that

Combining ( 84), (81) and the Hölder inequality, we get

Plugging in the value of a (see (81)) and recalling that (85) takes place whenever ξ ∈ Ξ with Prob{ξ ∈ Ξ} ≥ 1ǫ, we arrive at (41).

A.4 Proof of Proposition 9

The proof below follows the lines of the proof of Proposition 7 of [START_REF] Juditsky | Verifiable conditions of ℓ 1 -recovery of sparse signals with sign restrictions[END_REF]. Given ǫ ∈ (0, 1), let Ξ = {ξ :

We intend to prove the relations (a k ), (b k ) by induction in k. First, let us show that ( 1) . By (a k-1 ), z (k-1) is supported on the support of x. Note that

Then by (46) for any 1

so that the segment

, and the closest to zero point of this interval is

that is, ∆ i = ∆ i for all i. Since the segment S i covers z (k-1) i and ∆ i is the closest to 0 point in S i , while the width of S i is at most ℓ, we clearly have

Since (a k-1 ) is valid, (87.a) implies that