# Weaker Regularity Conditions and Sparse Recovery in High-Dimensional Regression

Authors: Shiqing Wang; Yan Shi; Limin Su
Journal: Journal of Applied Mathematics
 (2014)

---

## Abstract

Regularity conditions play a pivotal role for sparse recovery in high-dimensional regression. In this paper, we present a weaker regularity condition and further discuss the relationships with other regularity conditions, such as restricted eigenvalue condition. We study the behavior of our new condition for design matrices with independent random columns uniformly drawn on the unit sphere. Moreover, the present paper shows that, under a sparsity scenario, the Lasso estimator and Dantzig selector exhibit similar behavior. Based on both methods, we derive, in parallel, more precise bounds for the estimation loss and the
prediction risk in the linear regression model when the number of variables can be much larger than the sample size.


---

## Body

## 1. Introduction

In the recent years, the problems of statistical inference in high-dimensional setting, in which the dimension of the datap exceeds the sample size n, have attracted a great deal of attention. One concrete instance of a high-dimensional inference problem concerns the standard linear regression model:
(1)y=Xβ+W,
where X∈Rn×p is called the design matrix, β∈Rp is an unknown target vector, and W∈Rn is a stochastic error term, in which the goal is to estimate a vector β∈Rp based on response y and the vector of covariates X=(X1,…,Xp). In the setting p≫n, the classical linear regression model is unidentifiable, so that it is not meaningful to estimate the parameter vector β∈Rp.However, many high-dimensional regression problems exhibit special structure that can lead to an identifiable model. In particular, sparsity in the regression vectorβ is an archetypal example of such structure; that is, only a few components of β are different from zero, say s-sparsity; β is then said to be s-sparsity, and there has been a great interest in the study of this problem recently. The use of the l1-norm penalty to enforce sparsity has been very successful and there have been several methods, such as the Lasso [1] or basis pursuit [2], and the Dantzig selector [3]. Sparsity has also been exploited in a number of other questions, for instance, instrumental variable regression in the presence of endogeneity [4].There is now a well-developed theory on what conditions are required on the design matrixX∈Rn×p for such l1-based relaxations to reliably estimate β; for example, see [5–16]. The restricted eigenvalue (RE) condition due to Bickel et al. [10] is a weaker one of the conditions mentioned above. Wang and Su [7, 13] presented some equivalent conditions with them, respectively, and there is also a large body of work in the high-dimensional setting; for example, see [3, 6, 12, 17–19], which showed a uniform uncertainty principle (UUP, a condition that is stronger than the RE condition; see [10, 20]). In this paper, we consider a restricted eigenvalue condition that is weaker than the RE conditions in [7, 10, 13] under certain setting.Thus, in the setting of high-dimensional linear regression, the interesting question is accurately estimating the regression vectorβ and the response Xβ from few and corrupted observations. In the standard form, under assumptions on the matrix X and with high probability, the estimation bounds are of the form C∥β∥0(log⁡(p)/n)q/2 (e.g., see [7, 8, 13, 21]), and the prediction errors are bounded by Clog⁡(p)∥β∥0 (e.g., see [1, 7, 21]), where C is a positive constant.The main contribution of this paper is the following: we present a restricted eigenvalue assumption that is weaker than the RE conditions in previous paper under certain setting. Using thel1-norm penalty, our results are more precise than the existing ones. There is an open question that is finding a weaker assumption and obtaining better results no matter under what circumstances.The remainder of this paper is organized as follows. We begin in Section2 with some notations and definitions. In Section 3, we introduce some assumptions and discuss the relation between our assumptions and the existing ones. Section 4 contains our main results, and we also show the approximate equivalence between the Lasso and the Dantzig selector. We give three lemmas and the proofs of the theorems in Section 5.


## 2. Preliminaries

In this section, we introduce some notations and definitions.Let a vectorβ∈Rp. We denote by
(2)M(β)=∑j=1pI{βj≠0}=|J(β)|
the number of nonzero coordinates of β, where I{·} denotes the indicator function
(3)J(β)={j∈{1,…,p}:βj≠0}
and |J| the cardinality of J. We use the standard notation
(4)∥β∥q=(∑i=1p|βi|q)1/q
to stand for the lq-norm of the vector of β. Moreover, a vector β is said to be k-sparse if ∥β∥0≤k; that is, it has at most k nonzero entries. For a vector Δ∈Rp and a subset J⊂{1,…,p}, we denote by ΔJ the vector in Rp that has the same coordinates as Δ on J and zero coordinates on the complement Jc of J.For linear regression model (1), regularized estimation with the l1-norm penalty, also known as the Lasso [1] or the basis pursuit [2], refers to the following convex optimization problem:
(5)β^∈argmin⁡β∈Rp{1n∥Xβ-y∥22+λ∥β∥1},
where λ>0 is a penalization parameter. The Dantzig selector has been introduced by Candes and Tao [3] as
(6)β^∈argmin⁡β∈Rp∥β∥1subjectto∥XT(y-Xβ)∥∞≤λ,
where λ>0 is a tuning parameter. It is known that it can be recast as a linear program. Hence, it is also computationally tractable.For an integer1≤s≤p/2 and s-sparse vector β∈Rp, let βJ0∈R|J0| be a subvector of β∈Rp confined to J0. One of the common properties of the Lasso and the Dantzig selector is that, for an appropriately chosen λ and a vector δ=β^-β, where β^ is the solution from either the Lasso or the Dantzig selector, it holds with high probability (cf. Lemmas 11 and 12):
(7)∥δJ0c∥1≤c0∥δJ0∥1,
with c0=1 for the Dantzig selector by Candes and Tao [3] and with c0=3 for the Lasso by Bickel et al. [9], where c0>0 and
(8)J0=J(β)⊂{1,2,…,p}
is the set of nonzero coefficients of the true parameter β of the model.Finally, for anyn≥1, p≥2, we consider the Gram matrix:
(9)Ψn=1nXTX,
where X is the designed matrix in model (1) and XT∈Rp×n denotes the transpose matrix of X.


## 3. Discussion of the Assumption

Under the sparsity scenario, we are typically interested in the case wherep>n, and even p≫n. Here, sparsity specifies that the high-dimensional vector β has coefficients that are mostly 0. Clearly, the matrix Ψn is degenerate, and ordinary least squares does not work in this case, since it requires positive definiteness of Ψn. That is,
(10)min⁡δ∈Rp,δ≠0∥Xδ∥2n∥δ∥2>0.
It turns out that the Lasso and Dantzig selector require much weaker assumptions. The idea by Bickel et al. [10] is that the minimum in (10) be replaced by the minimum over a restricted set of vectors and the norm ∥δ∥2 in the denominator of the condition be replaced by the l2-norm of only a part of δ. Note that the role of (7) is to restrict set of vectors {δ∈Rp:δ≠0} to
(11){δ∈Rp:δ≠0,∥δJ0c∥1≤c0∥δJ0∥1}.Assumption 1 (RE(s,c0) (Bickel et al. [10])).
For some integers such that 1≤s≤p and a positive number c0, the following condition holds:
(12)κ(s,c0)≜min⁡J0⊆{1,2,…,p},|J0|≤smin⁡δ≠0,∥δJ0c∥1≤c0∥δJ0∥1∥Xδ∥2n∥δJ0∥2>0.Bickel et al. [10] showed that the bounds of estimation error and prediction error are C∥β∥0(log⁡(p)/n)q/2 and Clog⁡(p)∥β∥0, respectively, for both the Lasso and Dantzig selector, where C is a positive constant and ∥β∥0 is the sparsity level. Next, we describe the REτ2(s,c0) assumption presented by Wang and Su [7], which is obtained by replacing ∥δ∥2 by its upper bound ∥δ∥1 in (10).Assumption 2 (REτ2(s,c0) (Wang and Su [7])).
For some integers such that 1≤s≤p and a positive number c0, the following condition holds:
(13)τ2(s,c0)≜min⁡J0⊆{1,2,…,p},|J0|≤smin⁡δ≠0,∥δJ0c∥1≤c0∥δJ0∥1∥Xδ∥2n∥δ∥1>0.The two conditions are very similar. The only difference is thel1- versus l2-norm of a part of δ in the denominator. The REτ2(s,c0) condition is equivalent to RE(s,c0); see [7, 13] for the discussion on equivalence. The results of [7, 13] are more precise for the bounds of estimation and prediction than those derived in Bickel et al. [10] and do not lie on the sparsity level ∥β∥0.In order to obtain our regularity condition in this paper, we decomposeδ into a set of vectors δS0,δS1,δS2,…,δSK, such that S0 corresponds to locations of the s largest coefficient of δ in absolute values, S1 corresponds to locations of the next s largest coefficient of δS0c in absolute values, and so on. Hence, we have S0c=⋃k=1KSk, where K≥1, |Sk|=s, for allk=1,…,K-1, and |SK|≤s.Now for eachj≥1, we have
(14)∥δSj∥2≤s∥δSj∥∞≤1s∥δSj-1∥1,
where vector ∥·∥∞ represents the largest entry in absolute value in the vector, and hence
(15)∥δS0c∥2≤∑k≥1∥δSk∥2≤s-1/2(∥δS0∥1+∥δS1∥1+∥δS2∥1+⋯)≤s-1/2(∥δS0∥1+∥δS0c∥1)=s-1/2∥δ∥1.Replacing∥δ∥1 by s∥δS0c∥2 in (13), we get the following assumption.Assumption 3 (LRφ1(s,c0)).
For some integers such that 1≤s≤p and a positive number c0, the following condition holds:
(16)φ1(s,c0)≜min⁡J0⊆{1,2,…,p},|J0|≤smin⁡δ≠0,∥δJ0c∥1≤c0∥δJ0∥1∥Xδ∥2ns∥δJ0c∥2>0.The inequalitys∥δS0c∥2≤∥δ∥1 immediately implies that the assumption LRφ1(s,c0) is weaker than the assumptions REτ2(s,c0) and RE(s,c0). Noting the norm ∥δJ0c∥2 in the denominator of (16), it makes the proof become more complicated. We need an equivalent condition of LRφ1(s,c0) for the sake of simplicity, as similarly discussed on equivalence (cf. [7, 13]).Assumption 4 (LRφ2(s,c0)).
For some integers such that 1≤s≤p and a positive number c0, the following condition holds:
(17)φ2(s,c0)≜min⁡J0⊆{1,2,…,p},|J0|≤smin⁡δ≠0,∥δJ0c∥1≤c0∥δJ0∥1∥Xδ∥2sn∥δJ0∥1>0.The two conditions above can be used to solve all the problems of sparse recovery in high-dimensional regression. Due to technical reasons, we only give the results when the LRφ2(s,c0) is satisfied.


## 4. Main Results of Sparse Recovery for Regression Model

In order to provide performance guarantees forl1-norm penalty applied to sparse linear models, it is sufficient to assume that the regularity conditions are satisfied. In this section, we show main results when the LRφ2(s,c0) is satisfied. In particular, for convenience, we assume that all the diagonal elements of the matrix XTX/n are equal to 1.We firstly prove a type of approximate equivalence between the Lasso and the Dantzig selector. Similar results on equivalence can be found in [7, 10, 13]. It is expressed as closeness of the prediction losses ∥Xβ-XβD∥22 and ∥Xβ-XβL∥22 when the number of nonzero components of the Lasso or the Dantzig selector is small as compared to the sample size.Theorem 5.
For linear model (1), let Wi~N(0,σ2) be independent random variables with σ2>0. Consider the Lasso estimator β^L and Dantzig estimator β^D defined by (5) and (6) with the same λ. If LRφ2(s,c0) is satisfied, where c0>0, then, with probability of at least 1-p1-A2/8, one has
(18)|1n∥Xβ-XβD∥22-1n∥Xβ-XβL∥22|≤16λ2sφ22.Next, we get the bounds on the rate of convergence of Lasso and Dantzig selector.Theorem 6.
For linear model (1), let Wi~N(0,σ2) be independent random variables with σ2>0. Consider the Lasso estimator β^L defined by (5) with λ>2λ0>0. If LRφ2(s,3) is satisfied, where c0>0, then, with probability of at least 1-pexp⁡(2λ2n/σ2), one has
(19)∥β^L-β∥1≤4λsφ22(s,c0),(20)∥β^L-β∥2≤4λsφ22(35+1s),(21)1n∥X(β^L-β)∥22≤144λ225sφ22(s,c0),
where φ2=φ2(s,3).Theorem 7.
For linear model (1), let Wi~N(0,σ2) be independent random variables with σ2>0. Consider the Dantzig selector β^D defined by (6) with λ>λ0>0. If LRφ2(s,1) is satisfied, where c0>0, then, with probability of at least 1-pexp⁡(λ2n/2σ2), one has
(22)∥β^D-β∥1≤8λsφ22,(23)∥β^D-β∥2≤4λsφ22(1+2s),(24)1n∥X(β^D-β)∥22≤16λ2sφ22,
where φ2=φ2(s,1).Remark 8.
We have no conditions on the parameterλ. As in [10], we can rewrite λ in terms of another parameter A in order to clarify the notation:
(25)λ=Aσlog⁡pn,A>2.
Then, the results of Theorems 5–7 are as follows:
(26)|1n∥Xβ-XβD∥22-1n∥Xβ-XβL∥22|≤16A2σ2log⁡pnφ22s,(9′)∥β^L-β∥1≤4Aσsφ22(s,3)log⁡pn,(10′)∥β^L-β∥2≤4Aσsφ22(35+1s)log⁡pn,(11′)1n∥X(β^L-β)∥22≤144A225φ22(s,3)σ2log⁡psn,(12′)∥β^D-β∥1≤8Aσsφ22(s,1)log⁡pn,(13′)∥β^D-β∥2≤4Aσsφ22(1+2s)log⁡pn,(14′)1n∥X(β^D-β)∥22≤16A2φ22(s,1)σ2log⁡psn.
The results of Theorems 7.1 and 7.2 in Bickel et al. [10] are
(27)∥β^L-β∥1≤4Aσsφ22(s,3)log⁡pn,1n∥X(β^L-β)∥22≤144A225φ22(s,3)σ2slog⁡pn,∥β^D-β∥1≤8Aσsφ22(s,1)log⁡pn,1n∥X(β^D-β)∥22≤16A2φ22(s,1)σ2slog⁡pn.
Comparing the results above, our results greatly improve those in Bickel et al. [10].
Additionally, the similar results for Lasso can be found in Wang and Su [7]. They are
(28)∥β^L-β∥1≤4Aτ12(s,1)σlog⁡pn,1n∥X(β^L-β)∥22≤144A225τ12(s,1)σ2log⁡pn.
It is clear that our results are more precise than those in the existing results, for example, [7, 10].Remark 9.
The assumptions LRφ1(s,c0) and LRφ2(s,c0) are weaker than assumptions REτ2(s,c0) and RE(s,c0), since s∥δS0c∥2≤∥δ∥1. Note that the inequality s∥δS0c∥2≤∥δ∥1 holds under the setting discussed in Section 3. That is, our weaker assumptions hold under certain condition, but they cannot be considered to be better than those in previous paper at any time.


## 5. Lemmas and the Proofs of the Results

In this section, we give three lemmas and the proofs of the theorems.Lemma 10.
LetWi~N(0,σ2) be independent random variables with σ2>0. Then, for any λ0>0,
(29)P(1n|XTW|∞≥λ0)≤pexp⁡(λ02n2σ2).Proof.
SinceWi~N(0,σ2), it immediately follows that
(30)P(1n|XTW|∞≥λ0)≤∑jP(1n|∑ixi,jwi|≥λ0)≤p∑jP(|n-1/2σ-1∑ixi,jwi|≥λ0n(σ))≤p∑jP(|η|≥λ0n(σ)),≤pexp⁡(λ02n2σ2),
where η~N(0,1).Lemma 11.
LetWi~N(0,σ2) be independent random variables with σ2>0. Let β^L be the Lasso estimator defined by (5). Then, with probability of at least 1-pexp⁡(2λ2n/σ2), one has, simultaneously for all β∈Rp and λ>2λ0,
(31)1n∥Xβ^L-Xβ∥22+λ∑j=1p|βj-β^L,j|≤4λ∑j∈J(β)|βj-β^L,j|,(32)∥1nXTX(β-β^L)∥∞≤3λ2.Proof.
By the definition ofβ^L,
(33)1n∥Y-Xβ^L∥22+2λ∥β^L∥1≤1n∥Y-Xβ∥22+2λ∥β∥1
for all β∈Rp, which is equivalent to
(34)1n∥Xβ^L-Xβ∥22+2λ∥β^L∥1≤2λ∥β∥1+2nWTX(β^L-β).
From Lemma 10, we have that
(35)1n∥Xβ^L-Xβ∥22≤2λ∑j=1p|βj|-2λ∑j=1p|β^L,j|+λ∑j=1p|βj-β^L,j|
holds with probability of at least 1-pexp⁡(2λ2n/σ2).
Adding the term∑j=1pλ|β^j,L-βj| to both sides of this inequality, it yields that
(36)1n∥Xβ^L-Xβ∥22+λ∑j=1p|βj-β^L,j|≤2λ∑j=1p|βj|-2λ∑j=1p|β^L,j|+2λ∑j=1p|βj-β^L,j|≤2∑j=1pλ(|βj-β^L,j|+|βj|-|β^L,j|).
Now, note that
(37)|β^j,L-βj|+|βj|-|β^j,L|=0
since j∉J(β). So, we get that
(38)1n∥Xβ^L-Xβ∥22+λ∑j=1p|βj-β^L,j|≤2λ∑j∈J(β)(|βj-β^L,j|+|βj|-|β^L,j|)≤4λ∑j∈J(β)|βj-β^L,j|.
To prove (32), it suffices to note that, from Lemma 10 and λ>2λ0, we have that
(39)∥1nXTW∥∞≤λ2.
Then
(40)∥1nXTX(β-β^L)∥∞=∥1nXT(Y-W-Xβ^L)∥∞≤∥1nXT(Y-Xβ^L)∥∞+∥1nXTW∥∞≤λ+λ2=3λ2.Lemma 12.
Letβ∈Rpsatisfy the Dantzig constraint
(41)∥1nXTX(β^D-β)∥∞≤2λ
and set δ=β^D-β, J0=J(β). Then
(42)∥δJ0c∥1≤∥δJ0∥1.
Further, let the assumptions of Lemma 11 be satisfied. Then, with probability of at least 1-pexp⁡(λ2n/2σ2), one has, for λ>λ0,
(43)∥1nXT(Xβ-Xβ^D)∥∞≤2λ.Proof.
Inequality (42) immediately follows from the definition of Dantzig selector.
Next, we prove (43). From Lemma 10 and analogously to (32), using the definition of Dantzig selector, we get that
(44)∥1nXTX(β-β^D)∥∞=∥1nXT(Y-W-Xβ^D)∥∞≤∥1nXT(Y-Xβ^D)∥∞+∥1nXTW∥∞≤λ+λ=2λ.Proof of Theorem5.
Setδ=β^L-β^D. We start the calculation by simple matrix equality:
(45)∥Xβ-Xβ^D∥22-∥Xβ-Xβ^L∥22=2(β^L-β^D)TXT(Xβ-Xβ^D)-∥X(β^L-β^D)∥22≤2∥δ∥1∥XT(Xβ-Xβ^D)∥∞-∥Xδ∥22≤4nλ∥δ∥1-∥Xδ∥22,
where the last inequality holds with probability of at least 1-pexp⁡(λ2n/2σ2) from (43).
By assumption LRφ2(s,1) and (42), we get that
(46)∥Xβ-Xβ^D∥22-∥Xβ-Xβ^L∥22≤8nλ∥δJ∥1-φ22s∥δJ∥12≤16n2λ2φ22s.
From (32), a nearly identical argument yields that
(47)∥Xβ-Xβ^L∥22-∥Xβ-Xβ^D∥22≤2∥δ∥1∥XTX(β-β^L)∥∞-∥X(β-β^L)∥22(48)≤3nλ∥δ∥1-∥Xδ∥22(49)≤9n2λ2φ22s.
This theorem follows from (46) and (49).Proof of Theorem6.
Setδ=β^L-β. Using (31) with probability of at least 1-pexp⁡(2λ2n/σ2),
(50)1n∥Xδ∥22≤4λ∥δJ0∥1-λ∥δ∥1.
From (48), we have
(51)2n∥Xδ∥22≤3λ∥δ∥1.
Then
(52)1n∥Xδ∥22≤125λ∥δJ0∥1.
By assumption LRφ2(s,3), we obtain that
(53)φ22s∥δJ0∥12≤1n∥Xδ∥22≤125λ∥δJ0∥1,
where φ2=φ2(s,3). Thus,
(54)∥δJ0∥1≤12λ5sφ22(s,c0),(55)1n∥Xδ∥22≤144λ25sφ22(s,c0).
From (50), we have that
(56)λ∥δ∥1≤4λ∥δJ0∥1-1n∥Xδ∥22≤4λ2sφ22(s,c0).
Thus,
(57)∥δ∥1≤4λsφ22(s,c0).
Inequalities (55) and (57) coincide with (19) and (21), respectively.
Finally, to prove (20) we decompose δ into a set of vectors δJ0,δJ1,δJ2,…,δJK, such that J0 corresponds to locations of the s largest coefficient of δ in absolute values, J1 corresponds to locations of the next s largest coefficient of δJ0c in absolute values, and so on. Hence we have that J0c=∪k=1KJk, where K≥1, |Jk|=s, for all k=1,…,K-1, and |JK|≤s.
It immediately follows that(58)∥δJ0c∥2≤1s∥δ∥1.
On the other hand, from (54), we have that
(59)∥δJ0∥2≤∥δJ0∥1≤12λ5sφ22(s,c0).
Therefore,
(60)∥δ∥2≤∥δJ0∥2+∥δJ0c∥2≤12λ5sφ22(s,c0)+1s∥δ∥1≤12λ5sφ22(s,c0)+4λssφ22(s,c0)≤4λsφ22(s,c0)(35+1s),
and the theorem follows.Proof of Theorem7.
Setδ=β^D-β. Using (42) and (43), with probability of at least 1-pexp⁡(λ2n/2σ2), we have that
(61)1n∥Xδ∥22=1nδTXTXδ≤1n∥XTXδ∥∞∥δ∥1≤2r(∥δJ0∥1+∥δJ0c∥1)≤4r∥δJ0∥1.
From assumption LRφ2(s,1), we get that
(62)1n∥Xδ∥22≥sφ22∥δJ0∥12,
where φ2=φ2(s,1). This and (61) yield that
(63)1n∥Xδ∥22≤16λ2sφ22,∥δJ0∥1≤4λsφ22.
The first inequality in (63) implies (24). Next, (22) is straightforward in view of the second inequality in (63) and of relation (42). The proof of (23) follows from (20) in Theorem 6. From (22) and (58), we get that
(64)∥δJ0c∥2≤1s8λsφ22.
Then
(65)∥δ∥2≤∥δJ0∥2+∥δJ0c∥2≤4λsφ22+1s8λsφ22≤4λsφ22(1+2s),
where the second inequality holds from the second inequality in (63) and the inequality ∥δJ0∥2≤∥δJ0∥1.



---

*Source: 946241-2014-07-17.xml*