# Recovery of High-Dimensional Sparse Signals viaℓ1-Minimization

Authors: Shiqing Wang; Limin Su
Journal: Journal of Applied Mathematics
 (2013)

---

## Abstract

We consider the recovery of high-dimensional sparse signals viaℓ1-minimization under mutual incoherence condition, which is shown to be sufficient for sparse signals recovery in the noiseless and noise cases. We study both ℓ1-minimization under the ℓ2 constraint and the Dantzig selector. Using the two ℓ1-minimization methods and a technical inequality, some results are obtained. They improve the results of the error bounds in the literature and are extended to the general case of reconstructing an arbitrary signal.


---

## Body

## 1. Introduction

The problem of recovering a high-dimensional sparse signal based on a small number of measurements, possibly corrupted by noise, has attracted much recent attention. In the existing literature on sparse signals recovery and compressed sensing (see [1–13] and references therein), the emphasis is on assessing sparse signal w∈Rn from an observationy∈Rm:
(1)y=Aw+z,
where the matrix A∈Rm×n with m≪n is given and z∈Rm is a vector of measurement errors. The goal is to reconstruct the unknown vector w∈Rn based on y and A. Throughout the paper, we will assume that the columns of A are standardized to have unit ℓ2-norm.When noise is present, there are two well-knownℓ1-minimization methods, which are well suited for recovering sparse signals. One is ℓ1-minimization under the ℓ2-constraint on the residuals:
(2)(P1)w^=arg minw{∥w∥1:∥Aw-y∥2≤ε}.Another method, called Dantzig selector, is proposed by Candes and Tao [4]. The Dantzig selector solves the sparse recovery problem through ℓ1-minimization with a constraint on the correlation between the residuals and the column vectors of A:
(3)(P2)w^=arg minw{∥w∥1:∥AT(Aw-y)∥∞≤ε}.It is clear that regularity conditions are needed in order for these problems to be well behaved. Over the last few years, many interesting results for recovering sparse signals have been obtained in the framework of the mutual incoherence property (MIP) introduced by Donoho and Huo [14]. The MIP requires the pairwise correlations among the column vectors of A to be small. Let
(4)μ=maxi≠j|〈Ai,Aj〉|.
See, for example, [8, 10, 14, 15].It was first shown by Donoho and Huo [14], in the noiseless case for the setting where A is a concatenation of two square orthogonal matrices, that
(5)k<12(1μ+1),
ensuring that the exact recovery of w when w has at most k nonzero entries (such a signal is called k-sparse). This result was then extended in the noiseless case in [11, 16] to a general dictionary A.Stronger MIP conditions have been used in the literature to guarantee stable recovery of sparse signals in the noisy case. When noise is assumed to be bounded inℓ2-norm, Donoho et al. [15] showed that sparse signals can be recovered approximately through ℓ1-minimization, with the error being at worst proportional to the input noise level, when
(6)k<14(1μ+1).The results in [17] imply that
(7)k<23+6(1μ+1)≈0.368(1μ+1)
is sufficient for stable recovery. And Tseng [18] used
(8)k<(12-O(μ))1μ+1.Cai et al. [19] have showed that the condition
(9)k<12(1μ+1)
is not only sufficient but in fact sharp for stable recovery with bounded noise as well as Gaussian noise.In this paper, we consider the problem of recovering a high-dimensional sparse signal via two wellℓ1-minimization methods under the condition k<(1/2)(1/μ+1). We study both ℓ1-minimization under the ℓ2 constraint (P1) and the Dantzig selector (P2). Using the two methods and a technical inequality, we give some results, which slightly improve those in [19]. Moreover, we obtain some results when unknown vector is not k-sparse in the noise case and noiseless case.The rest of the paper is organized as follows. In Section2, some basic notation and definitions are reviewed; an elementary inequality, which allow us to make finer analysis of the sparse recovery problem, is introduced. We begin the analysis of ℓ1-minimization methods for sparse signals recovery by considering the exact recovery in the noise case in Section 3; our results are similar to those in [19] and to some extent, we provide tighter error bounds than the existing results in the literature. In Section 4, we consider the case of unknown vector which is not k-sparse under the condition k<(1/2)(1/μ+1). We give some facts and the proofs of the theorems in Section 5.


## 2. Preliminaries

We begin by introducing basic notation and definitions and then develop an important inequality which will be used in proving our main results.For a vectorv=(vi)∈ℝn, we will denote by supp(v)={i:vi≠0} the support of a vector v. We use the standard notation ∥v∥q=(∑i=1p|vi|q)1/q to denote the ℓq-norm of the vector of v. Moreover, a vector v is said to be k-sparse if |supp(v)|≤k. We also treat a vector v=(vi)∈ℝn as a function v:{1,2,…,n}→ℝ by assigning v(i)=vi.We now introduce a useful elementary inequality, which is used in the proofs of the theorems.Proposition 1.
Letk<n be positive integers. For any descending chain of real numbers
(10)x1≥x2≥⋯≥xk≥xk+1≥⋯≥xn-1≥xn≥0,
One has
(11)xk+12+xk+22+⋯+xn2≤(xk+1+xk+2+⋯+xn)(x1+x2+⋯+xk)kProof.
Sincexi≥xj for i<j, we have
(12)xk+12+xk+22+⋯+xn2≤xkxk+1+xk+1xk+2+⋯+xn-1xn=k(xkxk+1+xk+1xk+2+⋯+xn-1xn)k≤(xk+1+xk+2+⋯+xn)(x1+x2+⋯+xk)k.


## 3. Recovery ofk-Sparse Signals

As previously above, the condition (5) has been proved to guarantee the recovery of k-sparse signal in noiseless case. Cai et al. [19] have shown that this condition is also sufficient for stable reconstruction of k-sparse signals in the noisy case when the error is in a bounded set. We will also give the results for reconstruction of k-sparse signals both in the noiseless and noisy cases with error bounded, which are proved using different methods from [19].Theorem 2.
Consider the model (1) with ∥z∥2≤ε. Suppose that w is k-sparse and w^ is the solution of ℓ1-minimization problem (P1). Then, under the condition k<(1/2)(1/μ+1),
(13)∥w^-w∥2≤22(1+(k-1)μ)1-(2k-1)με.We now consider sparse recovery ofk-sparse signals with error in a different bounded set. Candes and Tao [4] treated the sparse signal recovery in the Gaussian noise case by solving minimization
(14)min∥w∥1subject to∥AT(y-Aw)∥∞≤η,
with bounded set {z:∥ATz∥∞≤η} and referred the solution as the Dantzig Selector. The following result shows that the condition k<(1/2)(1/μ+1) is also sufficient when the error is in the bounded set {z:∥ATz∥∞≤ε}.Theorem 3.
Consider the model (1) with ∥ATz∥∞≤ε. Suppose that w is k-sparse and w^ is the solution of ℓ1-minimization problem (P2). Then, under the condition k<(1/2)(1/μ+1),
(15)∥w^-w∥2≤22k1-(2k-1)με.Remark 4.
We consider the stable recovery of sparse signals with error in theℓ2-ball; for example, B⊂ℝn is a bounded set. B is taken to be {0} in the noiseless case and can be Bℓ2={z:∥z∥2≤η} or BDS={z:∥ATz∥∞≤η} in the noisy case.
Note that2kμ<μ+1, under the condition k<(1/2)(1/μ+1), the result of Theorem 2 is equivalent to
(16)∥w^-w∥2≤3-μ1-(2k-1)μ(ε+η),
and Theorem 3 is equivalent to
(17)∥w^-w∥2≤2k1-(2k-1)μ(ε+η).To some extent, Theorem2 improves Theorem  2.1 in [19], while Theorem 3 is improved using different method from [19] and gets the same results as Theorem  2.2 in [19].


## 4. Recovery of Approximatelyk-Sparse Signals

In the previous section, the focus was on recoveringk-sparse signals. As discussed in [17, 19, 20], our results can also be stated in the general setting of reconstructing an arbitrary signal under the condition k<(1/2)(1/μ+1).We begin in this section by considering the problem of exact recovery of spares signals when no noise is present. This is an interesting problem in itself and has been considered in a number of papers; see, for example, [9, 11, 17, 21]. More importantly, the solutions to this “clean” problem shed light on the noisy case.Whenw is not k-sparse, ℓ1-minimization can also recover w with accuracy if w has good k-term approximation. For a general vector w∈Rn, denote by wmax(k) with all but the k-largest entries (in absolute value) set to zero and w-max(k) the vector w with the k-largest entries (in absolute value) set to zero.Theorem 5.
LetA∈Rm×n. Suppose that k≥1 satisfies k<(1/2)(1/μ+1) and w^ is the solution of the following ℓ1-minimization problem
(18)(P)min∥w∥1subjecttoy=Aw.
Then
(19)∥w^-w∥2≤2μ2k∥w-max(k)∥11-(2k-1)μ.We now turn to the noisy case. Suppose thatA∈Rm×n and y=Aw+z, where the noise z is bounded. We will specifically consider two cases: ∥z∥2≤ε and ∥ATz∥∞≤ε. We will first consider the case ∥z∥2≤ε.Theorem 6.
Consider the model (1) with z satisfying ∥z∥2≤ε. Suppose that k≥1 satisfies k<(1/2)(1/μ+1) and w^ is the solution of the ℓ1-minimization problem (P1). Then
(20)∥w^-w∥2≤2ε2(1+(k-1)μ)+2μ2k∥w-max(k)∥11-(2k-1)μ.We next turn to the case∥ATz∥∞≤ε, which is called Dantzig selector.Theorem 7.
Consider the model (1) with ∥ATz∥∞≤ε. Suppose that k≥1 satisfies k<(1/2)(1/μ+1) and w^ is the solution of ℓ1-minimization problem (P2). Then
(21)∥w^-w∥2≤2ε2k+2μ2k∥w-max(k)∥11-(2k-1)μ.We have so far focused on stable recovery with bounded error. The results can be extended directly to the Gaussian noise case. This is due to the fact that Gaussian noise is “essentially bounded.” See, for example, [17, 19, 20].


## 5. The Proofs of the Theorems

Before giving the proofs of the theorems, we introduce three widely used facts, which are useful for the proofs.(A)
The following fact is well known in the recovery of sparse signals. Letx∈ℝn be any k-sparse signal and A∈Rm×n; then
(22)(1-(k-1)μ)∥x∥22≤∥Ax∥22≤(1+(k-1)μ)∥x∥22,where μ is defined by (4); see, for example, [17, 18, 22, 23].Letw^ be a solution to the minimization problem; then by definition ∥w^∥1≤∥w∥1. Let δ=w^-w, and δS0=δIsupp(w). Here, IJ denotes the indicator function of a set J; that is, IJ(j)=1 if j∈J and 0 if j∉J.(B)
The following is a widely used fact (see, e.g., [4, 7, 14, 17]):
(23)∥δ-δS0∥1≤∥δS0∥1.This follows directly from the fact that(24)∥w∥1≥∥w^∥1=∥w+δ∥1∥w∥1=∥w+δS0∥1+∥δ-δS0∥1∥w∥1≥∥w∥1-∥δS0∥1+∥δ-δS0∥1.(C)
The following fact, which is based on the minimality ofw^, has been widely used; see for example, [14, 19, 20]:
(25)∥δT0∥1≥∥δT0c∥1,where T0 is the support of w. This follows directly from the fact that
(26)∥w∥1≥∥w^∥1=∥w+δ∥1∥w∥1=∥w+δT0∥1+∥δT0c∥1∥w∥1≥∥w∥1-∥δT0∥1+∥δT0c∥1.Proof of Theorem2.
The proof makes use of the ideas from [17, 19, 22].
Letδ=w^-w. Rearranging the indices if necessary, we assume that
(27)|δ(1)|≥|δ(2)|≥⋯≥|δ(k+1)|≥|δ(k+2)|≥⋯.
LetT1={1,2,…,k} and T2 be the support of w; then, from the fact (C),
(28)∥δT2∥1≥∥δT2c∥1.
Note thatT2c∩T1 and T2∩T1c both have k-|T1∩T2| elements, so we have
(29)∥δT2c∩T1∥1≥∥δT2∩T1c∥1.
We will show that this implies that(30)∥δT1∥1≥∥δT1c∥1.
In fact(31)∥δT1∥1=∥δT1∩T2∥1+∥δT1∩T2c∥1∥δT1∥1=∥δT2∥1-∥δT2∩T1c∥1+∥δT1∩T2c∥1∥δT1∥1≥∥δT2c∥1-∥δT2∩T1c∥1+∥δT1∩T2c∥1∥δT1∥1=∥δT1c∩T2c∥1-∥δT2∩T1c∥1+2∥δT1∩T2c∥1∥δT1∥1=∥δT1c∥1-2∥δT2∩T1c∥1+2∥δT1∩T2c∥1≥∥δT1c∥1.
For simplicity, partition{1,2,…,n} into the following sets:
(32)S0={1,2,…,k},S1={k+1,k+2,…,k+k1},S2={k+k1+1,k+k1+2,…,k+k1+k2},…,
where kj(j>0) is an positive integer.
Note thatk<(1/2)(1/μ+1) is equivalent to (2k-1)μ<1 or 1-(2k-1)μ>0. Now
(33)|〈Aδ,AδS0〉|=|〈AδS0,AδS0〉+〈A(δ-δS0),AδS0〉||〈Aδ,AδS0〉|≥(1-(k-1)μ)∥δS0∥22-μ∥δ-δS0∥1∥δS0∥1|〈Aδ,AδS0〉|≥(1-(k-1)μ)∥δS0∥22-μ∥δS0∥12|〈Aδ,AδS0〉|≥(1-(k-1)μ)∥δS0∥22-μk∥δS0∥22|〈Aδ,AδS0〉|≥(1-(2k-1)μ)∥δS0∥22,
where the second inequality applies the facts (A) and (B).
On the other hand, it follows from the fact (A) that(34)∥AδS0∥22≤(1+(k-1)μ)∥δS0∥22.
Note that(35)∥Aδ∥2=∥A(w^-w)∥2≤∥Aw^-y∥2+∥Aw-y∥2≤2ε.
From Proposition1 and the fact that |δ(1)|≥|δ(2)|≥⋯≥|δ(k+1)|≥|δ(k+2)|≥⋯, we get
(36)∥δS0c∥22≤∥δS0c∥1∥δS0∥1k≤∥δS0∥12k≤∥δS0∥22,
which implies
(37)∥δ∥22=∥δS0∥22+∥δS0c∥22≤2∥δS0∥22.
Putting them together, we get(38)∥δ∥2≤2∥δS0∥2≤2|〈Aδ,AδS0〉|(1-(2k-1)μ)∥δS0∥2∥δ∥2≤2∥δS0∥2≤2∥Aδ∥2∥AδS0∥2(1-(2k-1)μ)∥δS0∥2∥δ∥2≤2∥δS0∥2≤22(1+(k-1)μ)∥δS0∥2(1-(2k-1)μ)∥δS0∥2ε∥δ∥2≤2∥δS0∥2=22(1+(k-1)μ)1-(2k-1)με.Proof of Theorem3.
Note that from the fact (A) and the first part of the proof of Theorem2, we have
(39)|〈Aδ,AδS0〉|≥(1-(2k-1)μ)∥δS0∥22.
On the other hand, we also obtain the following relation:
(40)|〈Aδ,AδS0〉|=(AδS0)TAδ|〈Aδ,AδS0〉|≤∥ATAδ∥∞∥δS0∥1≤2εk∥δS0∥2,
We get, together with them, that(41)∥δS0∥2≤2εk1-(2k-1)μ.
Then
(42)∥δ∥2≤2∥δS0∥2≤22k1-(2k-1)με,
where the last second inequality uses (37).Proof of Theorem5.
Letδ=w^-w and T={1,2,…,k}⊂{1,2,…,n} be the support of wmax(k). Following the notation and the first part in the proof of Theorem 2, we first give the following relation:
(43)∥δ-δS0∥1≤∥δS0∥1+2∥w-max(k)∥1.
In fact, since∥w∥1≥∥w^∥1, we have
(44)∥w∥1≥∥w^∥1=∥w+δ∥1∥w∥1=∥wmax(k)+w-max(k)+δ-δS0+δS0∥1∥w∥1=∥wmax(k)+δS0∥1+∥w-max(k)+δ-δS0∥1∥w∥1≥∥wmax(k)∥1-∥δS0∥1∥w∥1+∥δ-δS0∥1-∥w-max(k)∥1.
Sincew=wmax(k)+w-max(k), this yields
(45)∥δ-δS0∥1≤∥δS0∥1+2∥w-max(k)∥1.
Note that(46)Aδ=Aw^-Aw=0.
So(47)0=|〈Aδ,AδS0〉|=|〈AδS0,AδS0〉+〈A(δ-δS0),AδS0〉|0≥(1-(k-1)μ)∥δS0∥22-μ∥δ-δS0∥1∥δS0∥10≥(1-(k-1)μ)∥δS0∥22-μ(∥δS0∥1+2∥w-max(k)∥1)∥δS0∥10≥(1-(2k-1)μ)∥δS0∥22-2μk∥w-max(k)∥1∥δS0∥2,
where the last second inequality holds from  (43).
Then(48)∥δ0∥2≤2μk∥w-max(k)∥11-(2k-1)μ.
From (37), we have that
(49)∥δ∥2≤2∥δ0∥2≤2μ2k∥w-max(k)∥11-(2k-1)μ.
The proof is completed.Proof of Theorem6.
From the proof of Theorem5, we have
(50)|〈Aδ,AδS0〉|≥(1-(2k-1)μ)|〈Aδ,AδS0〉|×∥δS0∥22-2μk∥w-max(k)∥1∥δS0∥2.
It follows from the fact (A) that(51)∥AδS0∥22≤(1+(k-1)μ)∥δS0∥22.
Note that(52)∥Aδ∥2=∥A(w^-w)∥2≤∥Aw^-y∥2+∥Aw-y∥2≤2ε.
Together with them, we get(53)∥δS0∥2≤|〈Aδ,AδS0〉|+2μk∥w-max(k)∥1∥δS0∥2(1-(2k-1)μ)∥δS0∥2∥δS0∥2≤∥Aδ∥2∥AδS0∥2+2μk∥w-max(k)∥1∥δS0∥2(1-(2k-1)μ)∥δS0∥2∥δS0∥2≤2ε1+(k-1)μ∥δS0∥2+2μk∥w-max(k)∥1∥δS0∥2(1-(2k-1)μ)∥δS0∥2∥δS0∥2≤2ε1+(k-1)μ+2μk∥w-max(k)∥11-(2k-1)μ.
Then, from (37),
(54)∥δ∥2≤2∥δ0∥2∥δ∥2≤2ε2(1+(k-1)μ)+2μ2k∥w-max(k)∥11-(2k-1)μ.Proof of Theorem7.
From the proof of Theorems3 and 5, we get
(55)∥δS0∥2≤|〈Aδ,AδS0〉|+2μk∥w-max(k)∥1∥δS0∥2(1-(2k-1)μ)∥δS0∥2∥δS0∥2≤2εk∥δS0∥2+2μk∥w-max(k)∥1∥δS0∥2(1-(2k-1)μ)∥δS0∥2∥δS0∥2=2εk+2μk∥w-max(k)∥11-(2k-1)μ.
Then
(56)∥δ∥2≤2∥δ0∥2≤2ε2k+2μ2k∥w-max(k)∥11-(2k-1)μ.



---

*Source: 636094-2013-07-31.xml*