# l 1- and l2-Norm Joint Regularization Based Sparse Signal Reconstruction Scheme

Authors: Chanzi Liu; Qingchun Chen; Bingpeng Zhou; Hengchao Li
Journal: Mathematical Problems in Engineering
 (2016)

---

## Abstract

Many problems in signal processing and statistical inference involve finding sparse solution to some underdetermined linear system of equations. This is also the application condition of compressive sensing (CS) which can find the sparse solution from the measurements far less than the original signal. In this paper, we proposel1- and l2-norm joint regularization based reconstruction framework to approach the original l0-norm based sparseness-inducing constrained sparse signal reconstruction problem. Firstly, it is shown that, by employing the simple conjugate gradient algorithm, the new formulation provides an effective framework to deduce the solution as the original sparse signal reconstruction problem with l0-norm regularization item. Secondly, the upper reconstruction error limit is presented for the proposed sparse signal reconstruction framework, and it is unveiled that a smaller reconstruction error than l1-norm relaxation approaches can be realized by using the proposed scheme in most cases. Finally, simulation results are presented to validate the proposed sparse signal reconstruction approach.


---

## Body

## 1. Introduction

Compressive sensing or compressive sampling (CS) [1–3] is a novel technique that enables efficient sampling below Nyquist rate, without (or with little) sacrificing reconstruction quality. CS converts the high-dimensional sparse signal into a significantly lower dimensional measurement signal. More precisely, let x∈RN be a sparse vector, let A∈RM×N (M<N) be a measurement matrix, and suppose the noisy observation vector y is given by(1)y=Ax+e,where e∈RM is the noise vector. Here sparsity means that x0=K and K≪N; l0-norm counts the number of nonzero items of a vector. The goal is to obtain an estimate of x given A and y.Determining the sparse signal inRN from M<N measurements is typically an underdetermined problem; obviously, there will be no unique solution without any prior knowledge or constraint imposed on the solution x. As the original signal x is sparse, the problem of finding the desired solution can be phrased as some optimization problem, where the objective is to minimize the noise between noisy observation vector and real measurement while satisfying the constraint of the sparsity of x. As the sparsity of x is reflected by the number of its nonzero entries, equivalently its so-called l0-norm, in the noise-free case of (1), we can seek to solve the following P0 problem:(2)P0:minxx0,s.t.y=Ax.P0 can recover x exactly if x is sufficiently sparse and the matrix A satisfies the requirement of Restricted Isometry Constant (RIC) δK, which can be defined as the smallest constant 0≤δK≤1 such that the matrix A satisfies the Restricted Isometry Property (RIP) of order K; namely,(3)1-δKx22≤Ax22≤1+δKx22,whenever x0≤K. However, the optimization problem in (2) is nondeterministic polynomial (NP) hard which is difficult to be solved in practice. A number of approaches are presented to solve (2). The related approaches can be briefly classified into the following three categories.(i) Greedy Pursuits. Greedy algorithms attempt to determine the nonzero entry indices, based on the relationship between the columns of the measurement matrix A and the signal (or the residual signal), and then to estimate the non-zero entry amplitudes by using the least square method. Its objective is to pursue the minimization of l0-norm directly. The typical greedy approaches include Orthogonal Matching Pursuit (OMP) [4], Stagewise OMP (StOMP) [5], and Subspace Pursuit (SP) [6]. Basically, the greedy algorithms can only seek an approximate solution to (2) and are sensitive to noise.(ii) Optimization. This kind of approach attempts to replace l0-norm minimization problem in (2) with l1- or lp-norm (p∈(0,1)), admitting tractable algorithms. These methods try to obtain the sparse solution by employing a newly reformulated problem as follows:(4)P1:minxx1,s.t.y=Ax.In the noise-free case, P1 can recover x exactly as soon as δ3K+3δ4K<2. In the noisy case, the above convex relaxation formulation leads to the following penalized least-square problem [7, 8]:(5)minxy-Ax22+λx1.Later, it is shown in [9] that the reformulated one like minxy-Ax22+λΣiwi|xi| can better approach the original l0-norm problem in (2), where wi denotes the nonnegative weighting coefficient. Iterative reweighting scheme was further investigated in [10]. l1-magic algorithm in [11], the gradient projection for sparse reconstruction algorithm (GPSR) in [8], and their variants also belong to the convex relaxation categories. lp-norm minimization problem can be recast as(6)Pp:minxxp,s.t.y=Ax,where xp=∑i=1N|xi|p1/p. Chartrand demonstrated that K-sparse vectors can be exactly recovered by solving Pp under the assumption that δaK+bδ(a+1)K<b-1 holds for some b>1 and a=bq/(2-q) [12]. This kind of algorithm is capable of achieving better reconstruction quality and less error; however, it takes more time to solve the optimization problems.(iii) Bayesian Framework. Given the unknown sparse coefficientsa priori probability distribution, the Maximum A Posteriori (MAP) estimation mechanism can be employed to derive the Bayesian framework based sparse signal recovery schemes [13, 14]. It is unveiled in [15] that this framework may lead to a new mixture penalty of l0- and l1-norm functions.l 0-norm sparsity inducing item is very useful in image processing, for example, image restoration, image denoising, and image superresolution. Since l0-norm is nonconvex, image processing pursues l1- and l2-norm or total variation (TV) norm to replace the original l0-norm and solves the problems. Reference [16] studies a minimization problem where the objective includes a usual l2-norm data-fidelity term and an overlapping group sparsity total variation regularizer, and a fast algorithm is proposed to solve this problem. This method can avoid staircase effect and allow edges preserving. Reference [17] proposes l1-norm fidelity term with a total variation regularizer to recover blurred and salt-and-pepper impulse noisy image for higher visual quality. Reference [18] proposes an optimization model for noise and blur removal involving the generalized variation regularization term, the MAP (maximum posterior probability) based data fitting term, and a quadratic penalty term based on the statistical property of the noise. This minimization problem can be solved by a primal-dual algorithm. Reference [19] studies TV regularization in deblurring and sparse unmixing of hyperspectral images. Reference [20] investigates the modified linearized Bregman algorithm (MLBA) for image deblurring problems with a proper treatment of the boundary artifacts and l1- plus l2-norm.Motivated by the utility of sparsity and the efforts in relaxingl0-norm function with tractable norm functions to get either convex or nonconvex relaxation problem, in this paper, we propose a novel l1- and l2-norm joint regularization based reconstruction framework to approach the original l0-norm sparseness-inducing constraint based reconstruction problem. Although [21] has shown that lp and l1-l2 measures are theoretically better than l1-norm to promote sparsity, our analysis shows that the proposed sparse signal reconstruction model can also solve the original P0 problem. Moreover, the upper error limit of the proposed sparse signal recovery model is derived. It is unveiled that the proposed signal reconstruction model can achieve the tradeoff between l1-norm relaxation and lp-norm relaxation techniques. Namely, it exhibits similar l0-norm approximation capability like lp-norm relaxation. At the same time, like l1-norm convex relaxation approaches, we can resort to a variety of feasible optimization algorithms to derive the solution.The remainder of this paper is organized as follows. The proposed sparse signal recovery model will be introduced in Section2. Nextly, we deduce the error bound of the sparse signal reconstruction in Section 3. The practical algorithm design and experimental results are demonstrated in Sections 4 and 5. Finally, we conclude this paper in Section 6.


## 2. The Proposed Sparse Signal Recovery Model

### 2.1. Problem Reformulation

The reconstruction algorithm plays a central role in the sparse signal reconstruction. We proposel1- and l2-norm joint regularization to approximate l0-norm and the sparse signal recovery problem can be reformulated as follows:(7)P1,2:minxλx1-τx2,s.t.y=Ax.We will try to explicate that the joint combination ofl1- and l2-norm regularization provides a reasonable approximation to l0-norm, which can bring surprising benefits. Let us show this from the geometry point of view at first. The linear constraint of y=Ax defines the feasible set of the problem. Geometrically, solving (4) (or (6)) is done by blowing l1- (or lp-) norm balloon centered around the origin and stopping its inflation once it touches the feasible set. Figure 1 illustrates some examples with different p values of 2, 1.5, 1, 0.5, and 0.1, respectively. One can see that the norms with p≤1 tend to touch the feasible set at the axes, which leads to the sparse solutions. On the other hand, l2- or l1.5-norm tends to derive the nonsparse solution. One can also observe from Figure 1 that, by using the joint l1- and l2-norm in (7) with the suitable ratio of λ/τ, the intersection will also take place at the axes, which leads to sparse solution as well. Namely, the proposed signal reconstruction model resembles l0-norm approximation capability like lp-norm relaxation scheme. The influences of different choices of λ and τ will be highlighted in the following discussions.Figure 1
The illustration of the sparse signal reconstruction in 3D space, where the intersection between the unit-length norm ball and the hyperplane defines the solution.lp-norm illustration in (a)–(e); the proposed joint l1- and l2-norm in (f)–(h). (a) p=2; (b) p=1.5; (c) p=1; (d) p=0.5; (e) p=0.1; (f) λ/τ=5; (g) λ/τ=2; (h) λ/τ=1.05. It can be noted that when p≤1, the intersection takes place on the axes, leading to a sparse solution. The intersection of the proposed joint l1- and l2-norm case will take place on the axes as well.
(a) (b) (c) (d) (e) (f) (g) (h)


### 2.2. Sparse Solution Derivation Analysis

In this subsection, the analysis will validate that we can derive the same sparse solution by using the jointl1- and l2-norm instead of l0-norm function theoretically; that is to say, the solution to (7) is exactly x, when the certain signal sparsity requirement can be satisfied. Fortunately, if the original problem actually has a sufficiently sparse solution, the success of the proposed model in addressing the original objective (2) can also be guaranteed. Some definitions are firstly introduced.Definition 1 (see [22]).
The mutual-coherence of a given matrixA is the largest absolute normalized inner product between different columns of A. Let Al denote the lth column in A,l=1,2,…,N; the mutual-coherence can be calculated as (8)μ=max1≤i,j≤N,i≠jAiTAjAi2Aj2.The mutual-coherence provides a metric to assess the dependence between columns of the matrix A.Conclusion 1.
For the linear system of equationsy=Ax(A∈RM×N and M<N), x is assumed to be K-sparse; namely, x0=K; if a solution x exists obeying (9)K≤τ24λ2+121+1μ-τ4λτ2λ2+41+1μ,x will be the unique solution to (2) and (7).Proof.
Assume that there are possible solutions{w} different from x, which have larger support and can satisfy y=Aw. Define the following set of alternative solutions: (10)C=ww≠x,λw1-τw2≤λx1-τx2,w0≥x0,Aw-x=0..This set contains all the possible solutions {w} different from x, which have larger support and can satisfy y=Aw. Nonempty C implies that there is at least one alternative solution to (7), rather than the desired x.
Theorem2.5 in [22] tells us that if x0≤0.51+1/μ, x is necessarily the unique sparsest solution; any other alternative solutions w≠x must be denser; that is to say, w has more nonzero items. Our requirement on sparsity is τ2/4λ2+1/21+1/μ-τ/4λτ2/λ2+41+1/μ, which is less than 0.51+1/μ, no matter how to select the nonnegative parameters of λ and τ. It implies that x is also the unique sparsest possible solution, so w0≥x0 can be removed from C. Let us define v=w-x; we can rewrite C as the following shifted version around x:(11)Cs=vv≠0,Av=0,λv+x1-τv+x2-λx1+τx2≤0.The strategy of the proof we are going to present is to enlarge this set and show that the enlarged set is empty. This will prove that (7) indeed succeeds in recovering x. We start with the requirement λv+x1-τv+x2-λx1+τx2≤0. Without loss of generality, the K nonzeros in x are moved to the first K positions through a simple column permutation, which will not change the aforementioned inequality; we may have (12)λv+x1-λx1=λ∑i=1Kvi+xi-xi+λ∑i>Kvi.Here we use · to denote the element-wise absolute operation for every element of the matrix (vector), and the result of the matrix (vector) is still a matrix (vector); only the elements of the matrix (vector) are now all positive. By using the common inequality a+b-b≥-a, we can relax the above condition as follows: (13)-λ∑i=1Kvi+λ∑i>Kvi≤λ∑i=1Kvi+xi-xi+λ∑i>Kvi.
As forτx2-τv+x2, because of the triangle inequality property of vector norm, we have v+x2≤v2+x2. Then (14)-τv2≤τx2-τv+x2.We use 1KT·v to denote the sum of the first K entries of the vector v, where IK denotes the column vector with K ones followed byN-K zeros; namely, ∑i=1Kvi. So we may have(15)λv1-21KT·v-τv2≤0. Thus we have (16)Cs⊆vv≠0,Av=0,λv1-21KT·v-τv2≤0=Cs1.As stated before, the relaxation of the new alternative Cs1 will effectively enlarge the initial set Cs. We now turn to handle the requirement Av=0 by replacing it with a relaxed requirement that expands the set Cs1 further. We can normalize the matrix A such that each column Al is of unit l2-norm (this operation will preserve the mutual-coherence, as shown in [22]). Then the multiplication by AT yields the condition ATAv=0, which does not change the set Cs1. By letting G=ATA, this condition can be further rewritten as(17)-v=ATA-Iv.Taking an element-wise absolute value on both sides, we can relax the requirement on v to obtain (18)v=ATA-Iv≤ATA-I·v,where we have used the inequality of |Σiuivi|≤Σiuivi. Because every column of A has been normalized, one may readily derive the properties of the entries Gi,j=AiTAj of the resulting Gram matrix G=ATA as follows: (1)
Gi,i=1,1≤i≤N;(2)
Gi,j≤μ,1≤i,j≤N,i≠j.By letting I denote an identity matrix and P denote a rank-1 matrix filled with ones, we can have (19)v≤ATA-I·v≤1μ⋯μμ1⋯μ⋮⋮⋱⋮μμ⋯1-10⋯001⋯0⋮⋮⋱⋮00⋯1·v=0μ⋯μμ0⋯μ⋮⋮⋱⋮μμ⋯0·v=μP-I·v=μP·v-μv.Based on the above inequality, we can derive that 1+μv≤μP·v. Returning to the set Cs1, we have (20)Cs1⊆vv≠0,v≤μ1+μP·v,λv1-21KT·v-τv2≤0=Cs2.The resultant set Cs2 is unbounded since if v∈Cs2, av∈Cs2 for all a≠0. Thus we can restrict our quest for the normalized vector v1=1, because we have P|v|=1·1T|v|, where 1 denotes the all-ones column vector. Because 1T|v|=v1=1, this new set of Cr becomes (21)Cr⊆vv1=1,v≤μ1+μ1,λ1-21KT·v-τv2≤0.By substituting |v|=μ/1+μ1 into λ1-21KT·v-τv2≤0, we have (22)λ1-21KT·v-τv2=λ1-2Kμ1+μ-τ2Kμ1+μ≤0,where we have utilized the fact that v=w-x is at most 2K-sparse because it is assumed that both w and x are K-sparse solutions to y=Ax and w≠x. From the last inequality, we can obtain (23)λ1+μ-2λμK-τμ2K≤0.Let 2K=t; we get λ1+μ-λμt2-τμt≤0. Solving this inequality yields t≥-τ/λ+τ2/λ2+41+1/μ/2 and t≤-τ/λ-τ2/λ2+41+1/μ/2. Since t≥0, we have 2K≥-τ/λ+τ2/λ2+41+1/μ/2, leading to (24)K≥τ24λ2+121+1μ-τ4λτ2λ2+41+1μ.This implies if K is less than τ2/4λ2+1/21+1/μ-τ/4λτ2/λ2+41+1/μ, the set C will be necessarily empty, which also implies that we can not find such w with larger l0-norm but smaller difference between l1- and l2-norm. So our model can find the desired solution.For BP algorithm, it is known that if a solutionx exists obeying x0≤1/21+1/μ, the solution will be the unique solution to (2) and (4) as well. In our proposed model, when τ=0, the requirement will be reduced to 1/21+1/μ as well. Otherwise, the proposed model in (7) can derive the same solution when K≤τ2/4λ2+1/21+1/μ-τ/4λτ2/λ2+41+1/μ, which is more stringent sparsity requirement. And this is the paid cost of the proposed l1- and l2-norm joint regularization based sparse signal reconstruction approach.


## 2.1. Problem Reformulation

The reconstruction algorithm plays a central role in the sparse signal reconstruction. We proposel1- and l2-norm joint regularization to approximate l0-norm and the sparse signal recovery problem can be reformulated as follows:(7)P1,2:minxλx1-τx2,s.t.y=Ax.We will try to explicate that the joint combination ofl1- and l2-norm regularization provides a reasonable approximation to l0-norm, which can bring surprising benefits. Let us show this from the geometry point of view at first. The linear constraint of y=Ax defines the feasible set of the problem. Geometrically, solving (4) (or (6)) is done by blowing l1- (or lp-) norm balloon centered around the origin and stopping its inflation once it touches the feasible set. Figure 1 illustrates some examples with different p values of 2, 1.5, 1, 0.5, and 0.1, respectively. One can see that the norms with p≤1 tend to touch the feasible set at the axes, which leads to the sparse solutions. On the other hand, l2- or l1.5-norm tends to derive the nonsparse solution. One can also observe from Figure 1 that, by using the joint l1- and l2-norm in (7) with the suitable ratio of λ/τ, the intersection will also take place at the axes, which leads to sparse solution as well. Namely, the proposed signal reconstruction model resembles l0-norm approximation capability like lp-norm relaxation scheme. The influences of different choices of λ and τ will be highlighted in the following discussions.Figure 1
The illustration of the sparse signal reconstruction in 3D space, where the intersection between the unit-length norm ball and the hyperplane defines the solution.lp-norm illustration in (a)–(e); the proposed joint l1- and l2-norm in (f)–(h). (a) p=2; (b) p=1.5; (c) p=1; (d) p=0.5; (e) p=0.1; (f) λ/τ=5; (g) λ/τ=2; (h) λ/τ=1.05. It can be noted that when p≤1, the intersection takes place on the axes, leading to a sparse solution. The intersection of the proposed joint l1- and l2-norm case will take place on the axes as well.
(a) (b) (c) (d) (e) (f) (g) (h)


## 2.2. Sparse Solution Derivation Analysis

In this subsection, the analysis will validate that we can derive the same sparse solution by using the jointl1- and l2-norm instead of l0-norm function theoretically; that is to say, the solution to (7) is exactly x, when the certain signal sparsity requirement can be satisfied. Fortunately, if the original problem actually has a sufficiently sparse solution, the success of the proposed model in addressing the original objective (2) can also be guaranteed. Some definitions are firstly introduced.Definition 1 (see [22]).
The mutual-coherence of a given matrixA is the largest absolute normalized inner product between different columns of A. Let Al denote the lth column in A,l=1,2,…,N; the mutual-coherence can be calculated as (8)μ=max1≤i,j≤N,i≠jAiTAjAi2Aj2.The mutual-coherence provides a metric to assess the dependence between columns of the matrix A.Conclusion 1.
For the linear system of equationsy=Ax(A∈RM×N and M<N), x is assumed to be K-sparse; namely, x0=K; if a solution x exists obeying (9)K≤τ24λ2+121+1μ-τ4λτ2λ2+41+1μ,x will be the unique solution to (2) and (7).Proof.
Assume that there are possible solutions{w} different from x, which have larger support and can satisfy y=Aw. Define the following set of alternative solutions: (10)C=ww≠x,λw1-τw2≤λx1-τx2,w0≥x0,Aw-x=0..This set contains all the possible solutions {w} different from x, which have larger support and can satisfy y=Aw. Nonempty C implies that there is at least one alternative solution to (7), rather than the desired x.
Theorem2.5 in [22] tells us that if x0≤0.51+1/μ, x is necessarily the unique sparsest solution; any other alternative solutions w≠x must be denser; that is to say, w has more nonzero items. Our requirement on sparsity is τ2/4λ2+1/21+1/μ-τ/4λτ2/λ2+41+1/μ, which is less than 0.51+1/μ, no matter how to select the nonnegative parameters of λ and τ. It implies that x is also the unique sparsest possible solution, so w0≥x0 can be removed from C. Let us define v=w-x; we can rewrite C as the following shifted version around x:(11)Cs=vv≠0,Av=0,λv+x1-τv+x2-λx1+τx2≤0.The strategy of the proof we are going to present is to enlarge this set and show that the enlarged set is empty. This will prove that (7) indeed succeeds in recovering x. We start with the requirement λv+x1-τv+x2-λx1+τx2≤0. Without loss of generality, the K nonzeros in x are moved to the first K positions through a simple column permutation, which will not change the aforementioned inequality; we may have (12)λv+x1-λx1=λ∑i=1Kvi+xi-xi+λ∑i>Kvi.Here we use · to denote the element-wise absolute operation for every element of the matrix (vector), and the result of the matrix (vector) is still a matrix (vector); only the elements of the matrix (vector) are now all positive. By using the common inequality a+b-b≥-a, we can relax the above condition as follows: (13)-λ∑i=1Kvi+λ∑i>Kvi≤λ∑i=1Kvi+xi-xi+λ∑i>Kvi.
As forτx2-τv+x2, because of the triangle inequality property of vector norm, we have v+x2≤v2+x2. Then (14)-τv2≤τx2-τv+x2.We use 1KT·v to denote the sum of the first K entries of the vector v, where IK denotes the column vector with K ones followed byN-K zeros; namely, ∑i=1Kvi. So we may have(15)λv1-21KT·v-τv2≤0. Thus we have (16)Cs⊆vv≠0,Av=0,λv1-21KT·v-τv2≤0=Cs1.As stated before, the relaxation of the new alternative Cs1 will effectively enlarge the initial set Cs. We now turn to handle the requirement Av=0 by replacing it with a relaxed requirement that expands the set Cs1 further. We can normalize the matrix A such that each column Al is of unit l2-norm (this operation will preserve the mutual-coherence, as shown in [22]). Then the multiplication by AT yields the condition ATAv=0, which does not change the set Cs1. By letting G=ATA, this condition can be further rewritten as(17)-v=ATA-Iv.Taking an element-wise absolute value on both sides, we can relax the requirement on v to obtain (18)v=ATA-Iv≤ATA-I·v,where we have used the inequality of |Σiuivi|≤Σiuivi. Because every column of A has been normalized, one may readily derive the properties of the entries Gi,j=AiTAj of the resulting Gram matrix G=ATA as follows: (1)
Gi,i=1,1≤i≤N;(2)
Gi,j≤μ,1≤i,j≤N,i≠j.By letting I denote an identity matrix and P denote a rank-1 matrix filled with ones, we can have (19)v≤ATA-I·v≤1μ⋯μμ1⋯μ⋮⋮⋱⋮μμ⋯1-10⋯001⋯0⋮⋮⋱⋮00⋯1·v=0μ⋯μμ0⋯μ⋮⋮⋱⋮μμ⋯0·v=μP-I·v=μP·v-μv.Based on the above inequality, we can derive that 1+μv≤μP·v. Returning to the set Cs1, we have (20)Cs1⊆vv≠0,v≤μ1+μP·v,λv1-21KT·v-τv2≤0=Cs2.The resultant set Cs2 is unbounded since if v∈Cs2, av∈Cs2 for all a≠0. Thus we can restrict our quest for the normalized vector v1=1, because we have P|v|=1·1T|v|, where 1 denotes the all-ones column vector. Because 1T|v|=v1=1, this new set of Cr becomes (21)Cr⊆vv1=1,v≤μ1+μ1,λ1-21KT·v-τv2≤0.By substituting |v|=μ/1+μ1 into λ1-21KT·v-τv2≤0, we have (22)λ1-21KT·v-τv2=λ1-2Kμ1+μ-τ2Kμ1+μ≤0,where we have utilized the fact that v=w-x is at most 2K-sparse because it is assumed that both w and x are K-sparse solutions to y=Ax and w≠x. From the last inequality, we can obtain (23)λ1+μ-2λμK-τμ2K≤0.Let 2K=t; we get λ1+μ-λμt2-τμt≤0. Solving this inequality yields t≥-τ/λ+τ2/λ2+41+1/μ/2 and t≤-τ/λ-τ2/λ2+41+1/μ/2. Since t≥0, we have 2K≥-τ/λ+τ2/λ2+41+1/μ/2, leading to (24)K≥τ24λ2+121+1μ-τ4λτ2λ2+41+1μ.This implies if K is less than τ2/4λ2+1/21+1/μ-τ/4λτ2/λ2+41+1/μ, the set C will be necessarily empty, which also implies that we can not find such w with larger l0-norm but smaller difference between l1- and l2-norm. So our model can find the desired solution.For BP algorithm, it is known that if a solutionx exists obeying x0≤1/21+1/μ, the solution will be the unique solution to (2) and (4) as well. In our proposed model, when τ=0, the requirement will be reduced to 1/21+1/μ as well. Otherwise, the proposed model in (7) can derive the same solution when K≤τ2/4λ2+1/21+1/μ-τ/4λτ2/λ2+41+1/μ, which is more stringent sparsity requirement. And this is the paid cost of the proposed l1- and l2-norm joint regularization based sparse signal reconstruction approach.


## 3. Signal Recovery vial1- and l2-Norm Joint Minimization

### 3.1. Noise-Free Signal Recovery

There exist lots of approaches to recover a sparse signalx from a small number of linear measurements; we attempt to recover x by solving (7). We begin by considering noise-free case. Our main theorem is similar in flavor to many previous ones; in fact, its proof is inspired by those previous works. We start by illustrating Theorem 2 in the special case of K-sparse vectors that are measured with infinite precision, which means that the signal x is exactly K-sparse and the relative measurement error is equal to zero. For noise-free sparse signal recovery, we have the following conclusion about the signal recovery error upper limit.Theorem 2.
Givenλ and τ, if A satisfies theRIP of order 2K with δ2K<min⁡2-2/2,λK-τ/(2+2)(λK-τ)+2τ; then every K-sparse vector is exactly recovered by solving P1,2.Proof.
Firstly, we introduce Lemma 3.
Lemma  3.Suppose thatAsatisfies the RIP of order2Kwithδ2K<min⁡2-2/2,λK-(2+2)λδ2KK-τ/2τ; we obtain the measurementy=Ax. Letx and x^be given, and defineh=x^-x. LetΛ0denote the index set corresponding toKentries ofxwith the largest magnitude andΛ1the index set corresponding toKentries ofhΛ0Cwith the largestmagnitude, where Λ0C stands for the complement set of Λ0. SetΛ=Λ0∪Λ1. Ifλx^1-τx^2≤λx1-τx2, then(25)h2≤αAh2+βσx1,whereσ(x)1=xΛ0C1,α=2(1+2)1+δ2KλK/λK-(2+2)δ2KλK-(1+2δ2K)τ, andβ=(2+22δ2K)λ/λK-(2+2)δ2KλK-(1+2δ2K)τ.
Lemma 3 establishes an error bound for the proposed signal recovery modelP1,2 described by (7), when the measurement matrix A satisfies the RIP constraint. The detailed proof can be found in Appendix. In the case of noise-free measurement, that is, y=Ax, we can apply Lemma 3 to derive that, for x^=x+h, y=Ax=Ax^ yields Ah=A(x^-x)=y-y=0, then the term Ah vanishes, and x is K-sparse signal, leading to σ(x)1=0; we can obtain the following result: (26)x^-x2≤0. So every K-sparse vector can be exactly recovered by solving P1,2 problem.Theorem2 is an immediate consequence of Theorem 4 to be given in the next section. One may readily note that, in noise-free case, by setting appropriate parameter of λ and τ, we may achieve reasonable signal restoration performance, as will be illustrated by the numerical results in Section 4. Compared to the result of Theorem  1.8 in [23] with x^-x2≤C0σ(x)1/K, where C0=21-1-2δ2K/1-1+2δ2K, we can obtain the same result when σ(x)1=0. We will reveal how the different choices of λ and τ influence the upper error bound of the reconstructed signal in the following section.


### 3.2. Noisy Signal Recovery

In practical applications, the measurements are likely to be contaminated by various types of noise, such as quantization error and random noise. We suppose(27)P1,2,ϵ:minxλx1-τx2,s.t.y-Ax2≤ϵ.Note that ϵ represents a relative error between accurate and inaccurate measurements. In order to recover the original vector x∈RN from the measurement of y, we can solve the minimization of the above objective function.It is obvious that the minimization ofP1,2,ϵ is equivalent to (28)minxλx1-τx2,s.t.λx1-τx2≤ω,y-Ax2≤ϵ,where ω is the minimum of P1,2,ϵ. Because the set {x∈RN:λx1-τx2≤ω,y-Ax2≤ϵ} is compact and λx1-τx2 is a continuous function, we can conclude that the minimization of P1,2,ϵ must exist. So we have the following conclusion.Theorem 4.
Givenλ and τ, if A satisfies theRIP of order 2K with δ2K<min⁡2-2/2,λK-(2+2)λδ2KK-τ/2τ, then the solution x^ of P1,2,ϵ approximates the original vector x with error(29)x^-x2≤2αϵ+βσx1,where σ(x)1=xΛ0C1, α=2(1+2)1+δ2KλK/λK-(2+2)δ2KλK-(1+2δ2K)τ, and β=(2+22δ2K)λ/λK-(2+2)δ2KλK-(1+2δ2K)τ.Proof.
Sincee2≤ϵ, we have (30)Ah2=Ax^-x2=Ax^-y+y-Ax2≤Ax^-y2+y-Ax2≤2ϵ. So, with Lemma 3, (31)x^-x2≤2αϵ+βσx1.Theorem4 shows us that it is possible to stably recover sparse signals from the noisy measurements. Compared to the result of Theorem  1.9 in [23] with x^-x2≤C0σ(x)1/K+C2ϵ, where C0=21-(1-2)δ2K/1-(1+2)δ2K and C2=41+δ2K/1-1+2δ2K, we may achieve a smaller restoration error by using the proposed sparse signal recovery model when appropriate values of λ and τ are utilized.


## 3.1. Noise-Free Signal Recovery

There exist lots of approaches to recover a sparse signalx from a small number of linear measurements; we attempt to recover x by solving (7). We begin by considering noise-free case. Our main theorem is similar in flavor to many previous ones; in fact, its proof is inspired by those previous works. We start by illustrating Theorem 2 in the special case of K-sparse vectors that are measured with infinite precision, which means that the signal x is exactly K-sparse and the relative measurement error is equal to zero. For noise-free sparse signal recovery, we have the following conclusion about the signal recovery error upper limit.Theorem 2.
Givenλ and τ, if A satisfies theRIP of order 2K with δ2K<min⁡2-2/2,λK-τ/(2+2)(λK-τ)+2τ; then every K-sparse vector is exactly recovered by solving P1,2.Proof.
Firstly, we introduce Lemma 3.
Lemma  3.Suppose thatAsatisfies the RIP of order2Kwithδ2K<min⁡2-2/2,λK-(2+2)λδ2KK-τ/2τ; we obtain the measurementy=Ax. Letx and x^be given, and defineh=x^-x. LetΛ0denote the index set corresponding toKentries ofxwith the largest magnitude andΛ1the index set corresponding toKentries ofhΛ0Cwith the largestmagnitude, where Λ0C stands for the complement set of Λ0. SetΛ=Λ0∪Λ1. Ifλx^1-τx^2≤λx1-τx2, then(25)h2≤αAh2+βσx1,whereσ(x)1=xΛ0C1,α=2(1+2)1+δ2KλK/λK-(2+2)δ2KλK-(1+2δ2K)τ, andβ=(2+22δ2K)λ/λK-(2+2)δ2KλK-(1+2δ2K)τ.
Lemma 3 establishes an error bound for the proposed signal recovery modelP1,2 described by (7), when the measurement matrix A satisfies the RIP constraint. The detailed proof can be found in Appendix. In the case of noise-free measurement, that is, y=Ax, we can apply Lemma 3 to derive that, for x^=x+h, y=Ax=Ax^ yields Ah=A(x^-x)=y-y=0, then the term Ah vanishes, and x is K-sparse signal, leading to σ(x)1=0; we can obtain the following result: (26)x^-x2≤0. So every K-sparse vector can be exactly recovered by solving P1,2 problem.Theorem2 is an immediate consequence of Theorem 4 to be given in the next section. One may readily note that, in noise-free case, by setting appropriate parameter of λ and τ, we may achieve reasonable signal restoration performance, as will be illustrated by the numerical results in Section 4. Compared to the result of Theorem  1.8 in [23] with x^-x2≤C0σ(x)1/K, where C0=21-1-2δ2K/1-1+2δ2K, we can obtain the same result when σ(x)1=0. We will reveal how the different choices of λ and τ influence the upper error bound of the reconstructed signal in the following section.


## 3.2. Noisy Signal Recovery

In practical applications, the measurements are likely to be contaminated by various types of noise, such as quantization error and random noise. We suppose(27)P1,2,ϵ:minxλx1-τx2,s.t.y-Ax2≤ϵ.Note that ϵ represents a relative error between accurate and inaccurate measurements. In order to recover the original vector x∈RN from the measurement of y, we can solve the minimization of the above objective function.It is obvious that the minimization ofP1,2,ϵ is equivalent to (28)minxλx1-τx2,s.t.λx1-τx2≤ω,y-Ax2≤ϵ,where ω is the minimum of P1,2,ϵ. Because the set {x∈RN:λx1-τx2≤ω,y-Ax2≤ϵ} is compact and λx1-τx2 is a continuous function, we can conclude that the minimization of P1,2,ϵ must exist. So we have the following conclusion.Theorem 4.
Givenλ and τ, if A satisfies theRIP of order 2K with δ2K<min⁡2-2/2,λK-(2+2)λδ2KK-τ/2τ, then the solution x^ of P1,2,ϵ approximates the original vector x with error(29)x^-x2≤2αϵ+βσx1,where σ(x)1=xΛ0C1, α=2(1+2)1+δ2KλK/λK-(2+2)δ2KλK-(1+2δ2K)τ, and β=(2+22δ2K)λ/λK-(2+2)δ2KλK-(1+2δ2K)τ.Proof.
Sincee2≤ϵ, we have (30)Ah2=Ax^-x2=Ax^-y+y-Ax2≤Ax^-y2+y-Ax2≤2ϵ. So, with Lemma 3, (31)x^-x2≤2αϵ+βσx1.Theorem4 shows us that it is possible to stably recover sparse signals from the noisy measurements. Compared to the result of Theorem  1.9 in [23] with x^-x2≤C0σ(x)1/K+C2ϵ, where C0=21-(1-2)δ2K/1-(1+2)δ2K and C2=41+δ2K/1-1+2δ2K, we may achieve a smaller restoration error by using the proposed sparse signal recovery model when appropriate values of λ and τ are utilized.


## 4. Realization Algorithm

For simplicity, in this paper we resort to the simple computational approach of conjugate gradient (CG) algorithm for computing the local minimizer of problem (7). The CG algorithm is an effective approach to solve the linear system equation y=Ax from the measurements y for the given measurement matrix A. It is straightforward to generalize the proposed model with other advanced algorithms.Let us denote the initial guess ofx as x0 (without loss of generality, we assume x0=0 in this paper). The pseudocode of the CG algorithm is illustrated as follows.The Conjugate Gradient Algorithm (1)
Initialization: Initial pointλ, τ, xn,  gn=∇Fxn=ATy-Axn+λ·sign⁡xn-τ, iterations n=0, search direction dn=-gn; (2)
Loop until the specified accuracy or iteration numbers: (3)
Use the line search technique to determine the search step lengthηn; (4)
Update the signalxn+1=xn+ηndn; (5)
Update the gradientgn+1=AT(y-Axn+1)+λ·sign⁡xn+1-τ; (6)
Updateθn=gn+1T(gn+1-gn)/gnkgn; (7)
Update the search directiondn+1=-gn+1+θngn; (8)
Iteration number increases by 1 asn=n+1.Here sign⁡xn denotes the element-wise sign function of the vector xn, which is defined as follows: for every element xn1,…,xni,…,xnN,i=1,2,…,N, if xni>0,sign⁡xni=1; if xni=0,sign⁡xni=0; and if xni<0,sign⁡xni=-1.


## 5. Numerical Results

Simulations are performed to testify the applicability of the proposed signal reconstruction model in different settings. Some representative sparse signal restoration algorithms, such as (1) the greedy algorithm of the OMP [4], SP [6], and MP [24] for the P0 problem; (2) the l1-norm optimization of GPSR-Basic and GPSR-BB [8], LMS (Least Mean Square) [25], l1-ls [26], IRLS (Iteratively Reweighted Least Square) [27], and LARS (Least Angle Regression Stagewise) [28]; (3) the Bayesian framework of BCS (Bayesian Compressed Sensing) [14], are included in our simulations. For fair comparison, we considered the commonly assumed experimental setup in the literatures. All of our simulations are performed in MATLAB 2009 environment over Microsoft Window 7 operating system; the simulation platform is provisioned with Inter Core i5-480, ATI HD 5470 processor with 2 GB of memory. Gaussian measurement matrix A is assumed in all simulations for simplicity, which satisfies the RIP conditions with high probability. The entries of A are independently generated from normal distributed random variables with zero mean and variance of 1/M. In all experiments, we consider the fixed signal length of N=1000, while the number of measurements M and sparsity K may change in different experiment settings. The locations of K nonzero coefficients of sparse signal are assumed to be uniformly distributed within [1,N]. The corresponding nonzero coefficients are also generated from a Gaussian distributed random variable. Normalized reconstruction error x^-x2/x2 will be utilized as a metric to evaluate the reconstruction quality, where x^ and x represent the reconstructed and original signal vectors, respectively. For each experiment, 1000 simulations are conducted to calculate the normalized reconstruction error in different algorithms.


### 5.1. The Influence of Parameters ofλ and τ

The first problem we encounter is the choice ofλ and τ. In this experiment, we fix M=200 and the sparsity degree parameter K=10,20,30, and 40, respectively. We use the simple CG algorithm to solve our proposed model. Figure 2 shows the normalized reconstruction error as a logarithmic function of the ratio λ/τ; each point in the curve is the outcome of 100 iterations of the CG algorithm. Figure 2 can help us determine the appropriate λ/τ; we can find that when λ/τ≤1, the reconstruction results are terrible. A larger ratio leads to a more satisfying solution. And from the four curves, when λ/τ≥10, the reconstruction performance tends to be stable, so we select λ/τ=10 in the following experiments.Figure 2
The reconstruction error as a logarithmic function ofλ/τ.


### 5.2. Noise-Free Measurement Case

We start with the noise-free measurement case asy=Ax.Experiment 1 (effect of sparsity on the performance).
This experiment explores the answer to such a question on how the sparsity degree of the signal will affect the reconstruction quality with a given number of measurements. In this experiment, we fixM=200, while the sparsity degree parameter K will change from 5 to 40. We assume the simple CG algorithm to solve our proposed model. One may readily observe from Figure 3 that the proposed scheme (labeled with CG) far exceed GPSR-Basic, GPSR-BB, LMS, l1-ls, and IRLS. With the increase of sparsity, there will be larger reconstruction error for all algorithms; however, the proposed reconstruction scheme can still achieve a comparatively low reconstruction error, which complies with our previous analysis. It can be observed that BCS and LARS algorithms are always better than our proposed scheme. Our scheme is comparable to l1-norm relaxation techniques but is inferior to the inference method.Figure 3
The reconstruction error with different sparsity degrees,M=200,N=1000.Experiment 2 (effect of measurement number on the performance).
This experiment tries to answer the question on how different number of measurements will affect the achieved reconstruction performance. In the simulations, we fixK=20, while the number of measurements M changes from 140 to 210. The signal reconstruction errors are illustrated in Figure 4. We may observe similar results in the first experiment. BCS and LARS algorithms always achieve the best performance. The proposed method is comparable to the LMS algorithm, both of which are superior to other algorithms.Figure 4
The reconstruction error with different number of measurements,K=20,N=1000.


### 5.3. Noisy Measurement Case

Experiment 3 (robustness against noise).
In this experiment, we testify the noisy sparse signal reconstruction performance by fixingK=20,M=200. The noisy measurement model is given by y=Ax+e, where e is an additive white Gaussian noise with covariance matrix σ2IM (IM is M×M identity matrix). From Figure 5, we may observe that the proposed reconstruction algorithm can achieve superior restoration quality compared to greedy approaches, such as OMP and MP, in terms of the reconstruction errors. The performance of BCS and LARS algorithms is satisfactory in the first two experiments, but their antinoise performance is no match to our scheme. In addition, our scheme is slightly inferior to l1-ls. Obviously, with the increase of noise variance, our scheme has smaller reconstructed error than LMS which shows the good antinoise performance.Figure 5
The reconstruction error with different Gaussian noise variance,K=20,M=200,N=1000.Experiment 4 (robustness against noisy measurement matrixA).
In this experiment, we testify the stability of sparse signal reconstruction performance when the measurement matrixA is disturbed by Gaussian noise with fixed K=20,M=200. It is assumed that the measurement matrix A is contaminated by zero-mean Gaussian noise with different variances at the receiver. From Figure 6, we can observe that the proposed reconstruction model exhibits reasonable ability against the noisy measurement matrix except for LMS algorithm. With the increase of noise, our antinoise ability is worse compared to l1-ls and GPSR-Basic algorithms; however, when the noise is small, we can show competitive power. Our proposed scheme outperforms OMP, MP, BCS, LARS, and GPSR-BB.Figure 6
The reconstruction error with measurement matrixA disturbed by different Gaussian noise variance, K=20,M=200,N=1000.By comparing the simulations results in Figures3–6, we may observe that the proposed scheme outperforms the approaches of GPSR-BB, GPSR-Basic, and LRLS in terms of the achieved sparse signal reconstruction performance under different signal sparsity, different measurements, and robustness against background noise as well as the contamination of the measurement matrix. Although BCS and LARS algorithms exhibit better performance against different sparsity K and number of measurements M, it is sensitive to noise. LMS algorithm shows stable antinoise performance but is inferior to our proposed model with different sparsity K and number of measurements M. Greedy algorithms can achieve satisfactory performance given different signal sparsity and different measurements, but our proposed model exhibits better robustness against noise. Meanwhile, our proposed model outperforms most optimization based algorithms. In a word, the proposed reconstruction model provides an effective choice in the sparse signal reconstruction.


## 5.1. The Influence of Parameters ofλ and τ

The first problem we encounter is the choice ofλ and τ. In this experiment, we fix M=200 and the sparsity degree parameter K=10,20,30, and 40, respectively. We use the simple CG algorithm to solve our proposed model. Figure 2 shows the normalized reconstruction error as a logarithmic function of the ratio λ/τ; each point in the curve is the outcome of 100 iterations of the CG algorithm. Figure 2 can help us determine the appropriate λ/τ; we can find that when λ/τ≤1, the reconstruction results are terrible. A larger ratio leads to a more satisfying solution. And from the four curves, when λ/τ≥10, the reconstruction performance tends to be stable, so we select λ/τ=10 in the following experiments.Figure 2
The reconstruction error as a logarithmic function ofλ/τ.


## 5.2. Noise-Free Measurement Case

We start with the noise-free measurement case asy=Ax.Experiment 1 (effect of sparsity on the performance).
This experiment explores the answer to such a question on how the sparsity degree of the signal will affect the reconstruction quality with a given number of measurements. In this experiment, we fixM=200, while the sparsity degree parameter K will change from 5 to 40. We assume the simple CG algorithm to solve our proposed model. One may readily observe from Figure 3 that the proposed scheme (labeled with CG) far exceed GPSR-Basic, GPSR-BB, LMS, l1-ls, and IRLS. With the increase of sparsity, there will be larger reconstruction error for all algorithms; however, the proposed reconstruction scheme can still achieve a comparatively low reconstruction error, which complies with our previous analysis. It can be observed that BCS and LARS algorithms are always better than our proposed scheme. Our scheme is comparable to l1-norm relaxation techniques but is inferior to the inference method.Figure 3
The reconstruction error with different sparsity degrees,M=200,N=1000.Experiment 2 (effect of measurement number on the performance).
This experiment tries to answer the question on how different number of measurements will affect the achieved reconstruction performance. In the simulations, we fixK=20, while the number of measurements M changes from 140 to 210. The signal reconstruction errors are illustrated in Figure 4. We may observe similar results in the first experiment. BCS and LARS algorithms always achieve the best performance. The proposed method is comparable to the LMS algorithm, both of which are superior to other algorithms.Figure 4
The reconstruction error with different number of measurements,K=20,N=1000.


## 5.3. Noisy Measurement Case

Experiment 3 (robustness against noise).
In this experiment, we testify the noisy sparse signal reconstruction performance by fixingK=20,M=200. The noisy measurement model is given by y=Ax+e, where e is an additive white Gaussian noise with covariance matrix σ2IM (IM is M×M identity matrix). From Figure 5, we may observe that the proposed reconstruction algorithm can achieve superior restoration quality compared to greedy approaches, such as OMP and MP, in terms of the reconstruction errors. The performance of BCS and LARS algorithms is satisfactory in the first two experiments, but their antinoise performance is no match to our scheme. In addition, our scheme is slightly inferior to l1-ls. Obviously, with the increase of noise variance, our scheme has smaller reconstructed error than LMS which shows the good antinoise performance.Figure 5
The reconstruction error with different Gaussian noise variance,K=20,M=200,N=1000.Experiment 4 (robustness against noisy measurement matrixA).
In this experiment, we testify the stability of sparse signal reconstruction performance when the measurement matrixA is disturbed by Gaussian noise with fixed K=20,M=200. It is assumed that the measurement matrix A is contaminated by zero-mean Gaussian noise with different variances at the receiver. From Figure 6, we can observe that the proposed reconstruction model exhibits reasonable ability against the noisy measurement matrix except for LMS algorithm. With the increase of noise, our antinoise ability is worse compared to l1-ls and GPSR-Basic algorithms; however, when the noise is small, we can show competitive power. Our proposed scheme outperforms OMP, MP, BCS, LARS, and GPSR-BB.Figure 6
The reconstruction error with measurement matrixA disturbed by different Gaussian noise variance, K=20,M=200,N=1000.By comparing the simulations results in Figures3–6, we may observe that the proposed scheme outperforms the approaches of GPSR-BB, GPSR-Basic, and LRLS in terms of the achieved sparse signal reconstruction performance under different signal sparsity, different measurements, and robustness against background noise as well as the contamination of the measurement matrix. Although BCS and LARS algorithms exhibit better performance against different sparsity K and number of measurements M, it is sensitive to noise. LMS algorithm shows stable antinoise performance but is inferior to our proposed model with different sparsity K and number of measurements M. Greedy algorithms can achieve satisfactory performance given different signal sparsity and different measurements, but our proposed model exhibits better robustness against noise. Meanwhile, our proposed model outperforms most optimization based algorithms. In a word, the proposed reconstruction model provides an effective choice in the sparse signal reconstruction.


## 6. Concluding Remarks

In this paper, motivated by the efforts in relaxingl0-norm function with tractable norm functions to obtain either convex or nonconvex problem, we developed a new l1- and l2-norm joint regularization reconstruction framework to approach the original l0-norm sparseness-inducing constraint reconstruction problem. Our analysis shows that the proposed sparse signal reconstruction model can derive the same solution of the original sparse problem with l0-norm regularization. Moreover, the upper error bound of the proposed sparse signal recovery model is derived. It is shown that the proposed signal reconstruction model can achieve an interesting tradeoff between both l1-norm relaxation and lp-norm relaxation techniques. For instance, it exhibits the similar l0-norm approximation capability like lp-norm relaxation, while, on the other hand, straightforward and simple algorithms (such as the CG algorithm considered in this paper) can be utilized to derive the solution, just like l1-norm convex relaxation approaches. Numerical analysis is presented to validate that the proposed sparse signal reconstruction framework provides the exciting and satisfying method for the sparse signal reconstruction problem. Nextly, we will find other effective algorithm to solve this new model for better performance and popularize the proposed new norm model to image processing, such as image restoration in [16].



---

*Source: 3567095-2016-10-12.xml*