# An Adaptive Gradient Projection Algorithm for Piecewise Convex Optimization and Its Application in Compressed Spectrum Sensing

Authors: Tianjing Wang; Hang Shen; Xiaomei Zhu; Guoqing Liu; Hua Jiang
Journal: Mathematical Problems in Engineering
 (2018)

---

## Abstract

Signal sparse representation has attracted much attention in a wide range of application fields. A central aim of signal sparse representation is to find a sparse solution with the fewest nonzero entries from an underdetermined linear system, which leads to various optimization problems. In this paper, we propose an Adaptive Gradient Projection (AGP) algorithm to solve the piecewise convex optimization in signal sparse representation. To find a sparser solution, AGP provides an adaptive stepsize to move the iteration solution out of the attraction basin of a suboptimal sparse solution and enter the attraction basin of a sparser solution. Theoretical analyses are used to show its fast convergence property. The experimental results of real-world applications in compressed spectrum sensing show that AGP outperforms the traditional detection algorithms in low signal-to-noise-ratio environments.


---

## Body

## 1. Introduction

The marked advances in signal processing in recent years have been driven by the emergence of new signal models and their applications. Signal sparse representation is an effective model for solving real-world problems, such as brain signal processing [1], face recognition [2], compressed spectrum sensing [3], and singing voice separation [4].Given a signaly∈Rm, signal sparse representation aims to identify the sparsest solution x∈Rn from an underdetermined linear system y=Ax, where A∈Rm×n is a full row rank matrix. The sparsity of a solution can be measured by l0-norm, which leads to the following optimization problem(1)minxx0s.t.y=Ax.Unfortunately, problem (1) is NP-hard [5]. Many methods (e.g., the greedy algorithm [6], the l1-norm minimization [7], the lp-norm (0<p<1) minimization [8, 9], and the Bayesian method [10]) have been used to find sparse solutions. Because lp-norm is the most effective measurement of the sparsity, some researchers are interested in lp-norm minimization(2)minxxpps.t.y=Ax.The piecewise convex optimization (2) can be solved using the existing algorithms, including the Focal Underdetermined System Solver (FOCUSS) [11], the Affine Scaling Transformation (AST) method [12], the Iteratively Reweighted l1 minimization (IRL1) [13], and the Iteratively Thresholding Method (ITM) [14]. The solutions they obtain, however, may be suboptimal sparse solutions.In this paper, we propose a novel Adaptive Gradient Projection (AGP) algorithm for the piecewise convex optimization (2). This algorithm moves the iteration solution out of the attraction basin of a suboptimal sparse solution and finds a sparser solution in another attraction basin. The convergence analysis reveals that AGP performs better than AST when finding the global optimal sparse solution. The experimental results show that the detection performances of compressed spectrum sensing based on AGP are greatly improved compared to other algorithms.The remainder of the paper is organized as follows. In Section2, we derive an Adaptive Gradient Projection algorithm that can find a sparser solution than AST. Section 3 presents the application of AGP to compressed spectrum sensing. The detection performances based on AGP are compared to the traditional spectrum sensing method. Finally, conclusions are presented in Section 4.


## 2. Adaptive Gradient Projection Algorithm for Piecewise Convex Optimization

### 2.1. Description of Affine Scaling Transformation Method

For convenience, problem (2) can be rewritten as(3)minxEpx=∑i=1nxips.t.y=Ax.Note that the objective function is nondifferentiable with zero components. AST uses an affine scaling transformation to solve problem (3). For the (k+1)th iteration, it defines a symmetric scaling matrix Wk+1=diag⁡(xi1-p/2) and a scaled variable(4)q=Wk+1-1x,equivalentlyx=Wk+1q.Thus, problem (3) in x is transformed to the problem in q(5)minqEpWk+1qs.t.y=Ak+1q,where Ak+1=AWk+1.Given a search directionlk=p(I-Ak+1+Ak+1)qk, the new solution xk+1 is (6)xk+1=Wk+1qk+1=xk-μkWk+1lk,where I∈Rn×n is an identity matrix, Ak+1+=Ak+1T(Ak+1Ak+1T)-1 is a Moore-Penrose pseudoinverse matrix, and μk is a stepsize.Using a fixed stepsizeμk=1/p, AST is summarized as(7)Wk+1=diag⁡xki1-p/2,(8)qk+1=Ak+1+y,whereAk+1=AWk+1,(9)xk+1=Wk+1qk+1.The convergence theorem of AST is as follows.Theorem 1.
Starting from an initial pointx0, AST generates a sequence {xk}k=1∞ converging to a sparse solution x∗of problem (3).From (9), we see that some small entries of iteration solution converge to zero, because they are sequentially compressed by the scaling elements in Wk+1. Thus, a sequence of iteration solutions of AST will converge to a sparse solution x∗, which may be close to x0. However, this solution may be not the sparsest solution of problem (3). Making the iteration solution enter the attraction basin of other sparse solution is very important to reduce the effect of the initial point. Furthermore, Theorem 1 shows that AST obtains x∗ within an infinite number of iterations, which affects the convergence rate. How to enhance the convergence speed of AST is another problem to be solved.


### 2.2. Derivation of Adaptive Gradient Projection Algorithm

To solve the above two problems, we first consider the convergence process of AST if an iteration solution has some zero entries.Lemma 2.
Given a block matrixP=P1P2P3P4, we get (10)P-1=-U-1P4P2-1U-1P2-1+P2-1P1U-1P4P2-1-P2-1P1U-1,where U=P3-P4P2-1P1 is a Schur complement.Lemma 3.
Ifxk with S zero entries is a solution of problem (3), then these zero entries will not change in the remaining iterations.For simplicity, let the frontS entries of xk be zero (i.e., xk=(xk1,xk2)T=(0,xk2)T), where xk1=(xk(1),…,xk(S))T, xk2=(xk(S+1),…,xk(n))T. Then, xk+1can be computed as follows:(11)xk+1=Wk+1qk+1=Wk+1Ak+1+Axk=Wk+1AWk+1+Axk,where Wk+1=diag⁡Wk+11,Wk+12=diag⁡0,Wk+12. Partitioning A, we calculate AWk+1 in (11) to be(12)AWk+1=A11A12A21A22000Wk+12=0A12Wk+120A22Wk+12,and its Moore-Penrose pseudoinverse matrix is(13)AWk+1+=AWk+1TAWk+1AWk+1T-1,where(14)AWk+1AWk+1T-1=A12Wk+122A12TA12Wk+122A22TA22Wk+122A12TA22Wk+122A22T-1.BecauseAWk+1 is full row rank, AWk+1(AWk+1)T is also full rank, which has an invertible submatrix. For convenience, assume that A12(Wk+12)2A22T is an invertible submatrix. Otherwise, we partition (AWk+1(AWk+1)T)-1 to get an invertible submatrix according to Lemma 2. Defining P1=A12(Wk+12)2A12T, P2=A12(Wk+12)2A22T, P3=A22(Wk+12)2A12T, P4=A22(Wk+12)2A22T, we get(15)AWk+1AWk+1T-1=B11B12B21B22,where U=P3-P4P2-1P1, B11=-U-1P4P2-1, B22=-P2-1P1U-1, B12=U-1, B21=P2-1+P2-1P1U-1P4P2-1.Substituting (12) and (15) into (13), we have(16)AWk+1+=00A12Wk+12TA22Wk+12TB11B12B21B22=00C21C22,where C21=(A12Wk+12)TB11+(A22Wk+12)TB21, C22=(A12Wk+12)TB12+(A22Wk+12)TB22. Equation (11) then becomes(17)xk+1=Wk+1AWk+1+Axk=000Wk+1200C21C22A12xk2A22xk2=0Wk+12C21A12+C22A22xk2.The front S entries of xk+1 in (17) are still zero, and the reverse cannot occur in the remaining iterations.Lemma3 implies that an unknown sparse solution can be identified in smaller and smaller subspace. It motivates us to accelerate convergence by sequentially shrinking the solving range. Meanwhile, the choice of subspace cannot be limited by the initial point; that is, the iteration solution is able to enter the subspace that does not contain the initial point. AST chooses a fixed stepsize, so it cannot move the iteration solution from one octant to another distant octant. These solutions concentrate in the attraction basin of the suboptimal sparse solution. Moving the iteration solutions out of the current attraction basin is a goal of the Adaptive Gradient Projection algorithm.To find the search direction at an iteration solutionx, we define the gradient (18)g=∇xEpx=∂Epx∂x1,…,∂Epx∂xnT,where (19)∂Epx∂xi=pxip-2xi,ifxi≠0delete,ifxi=0,and delete represents that the partial derivative is not computed as x(i)=0, and the corresponding component is deleted from g. Definition (18) avoids the nondifferentiable problem of lp-norm minimization such that the gradient can be calculated in subspace. Then, we provide the algorithm derivation below.Initially, we reset an initial pointx0=A+y as(20)xD0j=x0i,ifx0i≠0delete,ifx0i=0,where the index set D0=(α1,…,αJ0) records the locations of entries as x0(i)≠0. For example, if x0=(0.2,-0.1,0.5,0, -0.2)T, then D0=(1,2,3,5) and xD0=(0.2,-0.1,0.5,-0.2)T.For the(k+1)th iteration, let W~k+1=diag⁡xDki1-p/2 and A~k+1=ADkW~k+1; the gradient g~k and the search direction l~k are(21)g~k=∂EpxDk∂xDk1,…,∂EpxDk∂xDkJkT,l~k=Ik-A~k+1+A~k+1g~k,where Dk=(α1,…,αJk) records the locations of entries as xDk(j)≠0(j=1,…,Jk), the column vectors of ADk are selected from A due to Dk, and Ik∈RJk×Jk is an identity matrix. In the span space of ADk, the new solution x~k+1 is defined due to (6):(22)x~k+1=xDk-μkW~k+1l~k,where μk is a stepsize.The major challenge in solving problem (3) is to identify the most appropriate subspace where the sparse solution locates. Equation (22) states that μk is important to find an appropriate subspace; thus, a function E(p)(x~k+1) with respect to μ is defined to investigate the property of the stepsize(23)Fμ=EpxDk-μW~k+1l~k.Figure 1(b) shows that the piecewise convex function F(μ) has nonunique minimum points that correspond to the zero entries of x~k+1. We can compute these extreme points.Figure 1
Function curves ofF(μ) with respect to μ. (a) Fixed stepsize selected by AST, marked as “+.” (b) Adaptive stepsize selected by AGP, marked as “∗.”
(a) (b)Without loss of generality, let every entry ofx~k+1 equal to zero (i.e., x~k+1(j)=0). Then, the extreme point μk,j is computed as (24)μk,j=xDkjV~k+1j,where j=1,…,Jk and V~k+1(j)=W~k+1l~k. An adaptive stepsize is chosen to find the minimal objective function value(25)μk∗=arg⁡minμk,j⁡EpxDk-μk,jW~k+1l~k+1,and the new solution x~k+1 is written as(26)x~k+1=xDk-μk∗W~k+1l~k.The minimum point (μk∗,E(p)(x~k+1)), marked as “∗” in Figure 1(b), is determined by comparing three extreme values. Using the adaptive stepsize to obtain an iteration solution is beneficial to accelerate convergence. However, AST cannot obtain a minimum point at the search direction Wk+1lk in (6), and the corresponding point (1/p,E(p)(xk+1)) is marked as “+” in Figure 1(a). Using the fixed stepsize makes the iteration solutions gather in the adjacent region of the initial point. On the other hand, we set x~k+1(j)=0 as x~k+1j<ε(j=1,…,Jk), where ε is a threshold. AGP then determines multiple zero entries at each iteration so that it can quickly identify subspace where the sparse solution locates.After some entries ofx~k+1 become zero, the set of their indices dk+1 is deleted from Dk (i.e., Dk+1=Dk∖dk+1). We define xDk+1←x~k+1(Dk+1) that represents the entries of x~k+1 located in Dk+1 that are assigned to xDk+1. Thus, (26) can be restated as (27)xDk+1⟵xDk-μk∗W~k+1l~k+1.For example, if x~k+1=(0.3,1×10-6,0,0,-0.1)T and ε=1×10-4, then Dk+1=(1,5) and xDk+1=(0.3,-0.1)T. The iterations are performed until the needed support set is determined.Returning the final solutionxDL to n-dimensional space is convenient to obtain the sparse solution x∗. By presetting x∗=0∈Rn, then x∗(DL)←xDL represents that the entries of xDL located in DL that are assigned to x∗. For example, if xDL=(0.3,-0.1)T and DL=(1,5), then x∗=(0.3,0,0,0,-0.1)T.As discussed above, AGP is summarized as follows.Algorithm 4 (Adaptive Gradient Projection Algorithm).
⁠
Step 1 (initialization). Given a threshold τ, compute an initial point x0=A+y and set an index set D0=(α1,…,αJ0) and the iteration index k=0.
Step 2 (iteration)while  Stopping criterion not met do
Computeg~k and l~k due to (21),Choose an adaptive stepsize by(28)μk∗=arg⁡minμk,j⁡EpxDk-μk,jW~k+1l~k,Compute a solutionx~k+1=xDk-μk∗W~k+1l~k,Update the solutionxDk+1←xDk-μk∗W~k+1l~k,Increase iteration indexk.end whileEpxDk+1-EpxDk<τ
Step 3 (solution). An optimal sparse solution x∗(Dk+1)←xDk+1.


### 2.3. Convergence Analysis

The convergence property of AGP is discussed as follows.Lemma 5.
AGP can determine at least one zero entry at each iteration.Due to (26), there are three cases that AGP determines zero entry at each iteration. The first case is that one entry of xDk is set to zero, if xDk moves from one octant to the coordinate surface of another distant octant. In the second case, more than one entry of xDk become zero when the new iteration solution x~k+1 exactly locates on the coordinate axis of another distant octant. In the third case, if x~k+1 locates on the side of the coordinate axis of another distant octant, we set x~k+1(j)=0 as x~k+1j<ε(j=1,…,Jk). Therefore, AGP can determine at least one zero entry at each iteration.Theorem 6.
Letx∗∈Rn with K nonzero entries be a sparse solution of problem (3). The number of iterations of AGP is no more than n-K.Ifx∗ has K nonzero entries, then the locations of n-K zero entries need to be determined. According to Lemma 5, AGP obtains multiple zero entries at each iteration, and these zero entries do not change in the remaining iterations based on the definition in (20). Therefore, the number of iterations of AGP is no more than n-K.Remark 7.
Theorem6 shows that AGP obtains a sparse solution within a finite number of iterations, while Theorem 1 shows that AST requires an infinite number of iterations to obtain a sparse solution. In theory, the number of iterations of AGP is less than AST.Figure2 gives an example to show the improved convergence performance of AGP compared to AST. There are three sparse solutions x1∗,x2∗,x3∗∈R3, where x3∗ is the global optimal sparse solution. To clearly display the iteration process of AGP, we return all xDk to three dimensional space, which form a sequence {xk}k=1L, where xk(Dk)←xDk represents that the entries of xDk located in Dk which are assigned to xk.Figure 2
Iteration processes of AST and AGP. (a) Sequence solved by AST converges tox1∗. (b) Sequence solved by AGP converges to x3∗. (c) Iteration process of AST. (d) Iteration process of AGP.
(a) (b) (c) (d)Starting fromx0, a sequence {xk}k=16solved by AST converges to x1∗ in Figure 2(a). Figure 2(c) shows that all iteration solutions concentrate in the attraction basin of x1∗ in the contour map. The second iteration solution of AGP in Figure 2(b), however, moves away from x1∗ and reaches x3∗. In Figure 2(d), the iteration solution moves out of the attraction basin of x1∗ and enters the attraction basin of x3∗, in which the adaptive stepsize plays an important role. This example verifies that AGP can find a sparser solution than AST by calculating the minimum point of the search direction at each iteration.


### 2.4. Comparison of Convergence Performance

To compare the convergence performance of AST and AGP, we give an experiment by the followinglp-norm problem(29)minE0.5x=∑i=18xi0.5s.t.x1+9x2+x3+9x4+2x5+x6+6x7+7x8=11.511x1+9x2+4x3+5x4+3x5+10x6+x7+4x8=1310x2+3x3+10x4+x5+6x6+10x7+6x8=16.2.There exist two sparse solutions x1∗=(0,0.9453,0,0,0,0.4061,0.4310,0)T and x2∗=(0,0,0,1.2,0,0.7,0,0)T, where x2∗ is the global optimal sparse solution. We choose x0=A+y as an initial point. Comparing the results in Table 1 with Table 2, we see that AGP quickly finds x2∗ in smaller and smaller subspace, while AST limited by the initial point just obtains the suboptimal solution x1∗. On the other hand, the computing times of AST and AGP are 0.0063 s and 0.0089 s, respectively. AGP costs some time to find an adaptive stepsize at each iteration, but it can obtain the global minimizer. Obviously, it is more important to find the global optimal sparse solution of problem (3).Table 1
List of the partial iteration solutions solved by AST.
k x k T 1 (0.0339, 0.5510, 0.0625, 0.3716, 0.0024, 0.4874, 0.3344, 0.0860) 3 (−0.0000, 0.7245, 0.0007, 0.2784, −0.0000, 0.4747, 0.3310, 0.0017) 5 (−0.0000, 0.8575, 0.0000, 0.1115, −0.0000, 0.4334, 0.3910, 0.0000) 7 (−0.0000, 0.9379, 0.0000, 0.0094, −0.0000, 0.4084, 0.4276, 0.0000) 9 (−0.0000, 0.9453, 0.0000, 0.0000, −0.0000, 0.4061, 0.4310, 0.0000)Table 2
List of the partial iteration solutions solved by AGP.
k x D k T D k 1 (0.0030, 0.6181, 0, 0.3752, −0.0115,0.5101, 0.2972,0.0410) ( 1,2 , 3,4 , 5,6 , 7,8 ) 2 (−0.0005, 0.6860, 0.3288, 0.0017, 0.4870, 0.3128) ( 1,2 , 4,5 , 6,7 ) 3 (−0.0070, 1.1946, 0.0229, 0.7034, 0.0010) ( 1,4 , 5,6 , 7 ) 4 (1.2000, 0.7000) ( 4,6 )


## 2.1. Description of Affine Scaling Transformation Method

For convenience, problem (2) can be rewritten as(3)minxEpx=∑i=1nxips.t.y=Ax.Note that the objective function is nondifferentiable with zero components. AST uses an affine scaling transformation to solve problem (3). For the (k+1)th iteration, it defines a symmetric scaling matrix Wk+1=diag⁡(xi1-p/2) and a scaled variable(4)q=Wk+1-1x,equivalentlyx=Wk+1q.Thus, problem (3) in x is transformed to the problem in q(5)minqEpWk+1qs.t.y=Ak+1q,where Ak+1=AWk+1.Given a search directionlk=p(I-Ak+1+Ak+1)qk, the new solution xk+1 is (6)xk+1=Wk+1qk+1=xk-μkWk+1lk,where I∈Rn×n is an identity matrix, Ak+1+=Ak+1T(Ak+1Ak+1T)-1 is a Moore-Penrose pseudoinverse matrix, and μk is a stepsize.Using a fixed stepsizeμk=1/p, AST is summarized as(7)Wk+1=diag⁡xki1-p/2,(8)qk+1=Ak+1+y,whereAk+1=AWk+1,(9)xk+1=Wk+1qk+1.The convergence theorem of AST is as follows.Theorem 1.
Starting from an initial pointx0, AST generates a sequence {xk}k=1∞ converging to a sparse solution x∗of problem (3).From (9), we see that some small entries of iteration solution converge to zero, because they are sequentially compressed by the scaling elements in Wk+1. Thus, a sequence of iteration solutions of AST will converge to a sparse solution x∗, which may be close to x0. However, this solution may be not the sparsest solution of problem (3). Making the iteration solution enter the attraction basin of other sparse solution is very important to reduce the effect of the initial point. Furthermore, Theorem 1 shows that AST obtains x∗ within an infinite number of iterations, which affects the convergence rate. How to enhance the convergence speed of AST is another problem to be solved.


## 2.2. Derivation of Adaptive Gradient Projection Algorithm

To solve the above two problems, we first consider the convergence process of AST if an iteration solution has some zero entries.Lemma 2.
Given a block matrixP=P1P2P3P4, we get (10)P-1=-U-1P4P2-1U-1P2-1+P2-1P1U-1P4P2-1-P2-1P1U-1,where U=P3-P4P2-1P1 is a Schur complement.Lemma 3.
Ifxk with S zero entries is a solution of problem (3), then these zero entries will not change in the remaining iterations.For simplicity, let the frontS entries of xk be zero (i.e., xk=(xk1,xk2)T=(0,xk2)T), where xk1=(xk(1),…,xk(S))T, xk2=(xk(S+1),…,xk(n))T. Then, xk+1can be computed as follows:(11)xk+1=Wk+1qk+1=Wk+1Ak+1+Axk=Wk+1AWk+1+Axk,where Wk+1=diag⁡Wk+11,Wk+12=diag⁡0,Wk+12. Partitioning A, we calculate AWk+1 in (11) to be(12)AWk+1=A11A12A21A22000Wk+12=0A12Wk+120A22Wk+12,and its Moore-Penrose pseudoinverse matrix is(13)AWk+1+=AWk+1TAWk+1AWk+1T-1,where(14)AWk+1AWk+1T-1=A12Wk+122A12TA12Wk+122A22TA22Wk+122A12TA22Wk+122A22T-1.BecauseAWk+1 is full row rank, AWk+1(AWk+1)T is also full rank, which has an invertible submatrix. For convenience, assume that A12(Wk+12)2A22T is an invertible submatrix. Otherwise, we partition (AWk+1(AWk+1)T)-1 to get an invertible submatrix according to Lemma 2. Defining P1=A12(Wk+12)2A12T, P2=A12(Wk+12)2A22T, P3=A22(Wk+12)2A12T, P4=A22(Wk+12)2A22T, we get(15)AWk+1AWk+1T-1=B11B12B21B22,where U=P3-P4P2-1P1, B11=-U-1P4P2-1, B22=-P2-1P1U-1, B12=U-1, B21=P2-1+P2-1P1U-1P4P2-1.Substituting (12) and (15) into (13), we have(16)AWk+1+=00A12Wk+12TA22Wk+12TB11B12B21B22=00C21C22,where C21=(A12Wk+12)TB11+(A22Wk+12)TB21, C22=(A12Wk+12)TB12+(A22Wk+12)TB22. Equation (11) then becomes(17)xk+1=Wk+1AWk+1+Axk=000Wk+1200C21C22A12xk2A22xk2=0Wk+12C21A12+C22A22xk2.The front S entries of xk+1 in (17) are still zero, and the reverse cannot occur in the remaining iterations.Lemma3 implies that an unknown sparse solution can be identified in smaller and smaller subspace. It motivates us to accelerate convergence by sequentially shrinking the solving range. Meanwhile, the choice of subspace cannot be limited by the initial point; that is, the iteration solution is able to enter the subspace that does not contain the initial point. AST chooses a fixed stepsize, so it cannot move the iteration solution from one octant to another distant octant. These solutions concentrate in the attraction basin of the suboptimal sparse solution. Moving the iteration solutions out of the current attraction basin is a goal of the Adaptive Gradient Projection algorithm.To find the search direction at an iteration solutionx, we define the gradient (18)g=∇xEpx=∂Epx∂x1,…,∂Epx∂xnT,where (19)∂Epx∂xi=pxip-2xi,ifxi≠0delete,ifxi=0,and delete represents that the partial derivative is not computed as x(i)=0, and the corresponding component is deleted from g. Definition (18) avoids the nondifferentiable problem of lp-norm minimization such that the gradient can be calculated in subspace. Then, we provide the algorithm derivation below.Initially, we reset an initial pointx0=A+y as(20)xD0j=x0i,ifx0i≠0delete,ifx0i=0,where the index set D0=(α1,…,αJ0) records the locations of entries as x0(i)≠0. For example, if x0=(0.2,-0.1,0.5,0, -0.2)T, then D0=(1,2,3,5) and xD0=(0.2,-0.1,0.5,-0.2)T.For the(k+1)th iteration, let W~k+1=diag⁡xDki1-p/2 and A~k+1=ADkW~k+1; the gradient g~k and the search direction l~k are(21)g~k=∂EpxDk∂xDk1,…,∂EpxDk∂xDkJkT,l~k=Ik-A~k+1+A~k+1g~k,where Dk=(α1,…,αJk) records the locations of entries as xDk(j)≠0(j=1,…,Jk), the column vectors of ADk are selected from A due to Dk, and Ik∈RJk×Jk is an identity matrix. In the span space of ADk, the new solution x~k+1 is defined due to (6):(22)x~k+1=xDk-μkW~k+1l~k,where μk is a stepsize.The major challenge in solving problem (3) is to identify the most appropriate subspace where the sparse solution locates. Equation (22) states that μk is important to find an appropriate subspace; thus, a function E(p)(x~k+1) with respect to μ is defined to investigate the property of the stepsize(23)Fμ=EpxDk-μW~k+1l~k.Figure 1(b) shows that the piecewise convex function F(μ) has nonunique minimum points that correspond to the zero entries of x~k+1. We can compute these extreme points.Figure 1
Function curves ofF(μ) with respect to μ. (a) Fixed stepsize selected by AST, marked as “+.” (b) Adaptive stepsize selected by AGP, marked as “∗.”
(a) (b)Without loss of generality, let every entry ofx~k+1 equal to zero (i.e., x~k+1(j)=0). Then, the extreme point μk,j is computed as (24)μk,j=xDkjV~k+1j,where j=1,…,Jk and V~k+1(j)=W~k+1l~k. An adaptive stepsize is chosen to find the minimal objective function value(25)μk∗=arg⁡minμk,j⁡EpxDk-μk,jW~k+1l~k+1,and the new solution x~k+1 is written as(26)x~k+1=xDk-μk∗W~k+1l~k.The minimum point (μk∗,E(p)(x~k+1)), marked as “∗” in Figure 1(b), is determined by comparing three extreme values. Using the adaptive stepsize to obtain an iteration solution is beneficial to accelerate convergence. However, AST cannot obtain a minimum point at the search direction Wk+1lk in (6), and the corresponding point (1/p,E(p)(xk+1)) is marked as “+” in Figure 1(a). Using the fixed stepsize makes the iteration solutions gather in the adjacent region of the initial point. On the other hand, we set x~k+1(j)=0 as x~k+1j<ε(j=1,…,Jk), where ε is a threshold. AGP then determines multiple zero entries at each iteration so that it can quickly identify subspace where the sparse solution locates.After some entries ofx~k+1 become zero, the set of their indices dk+1 is deleted from Dk (i.e., Dk+1=Dk∖dk+1). We define xDk+1←x~k+1(Dk+1) that represents the entries of x~k+1 located in Dk+1 that are assigned to xDk+1. Thus, (26) can be restated as (27)xDk+1⟵xDk-μk∗W~k+1l~k+1.For example, if x~k+1=(0.3,1×10-6,0,0,-0.1)T and ε=1×10-4, then Dk+1=(1,5) and xDk+1=(0.3,-0.1)T. The iterations are performed until the needed support set is determined.Returning the final solutionxDL to n-dimensional space is convenient to obtain the sparse solution x∗. By presetting x∗=0∈Rn, then x∗(DL)←xDL represents that the entries of xDL located in DL that are assigned to x∗. For example, if xDL=(0.3,-0.1)T and DL=(1,5), then x∗=(0.3,0,0,0,-0.1)T.As discussed above, AGP is summarized as follows.Algorithm 4 (Adaptive Gradient Projection Algorithm).
⁠
Step 1 (initialization). Given a threshold τ, compute an initial point x0=A+y and set an index set D0=(α1,…,αJ0) and the iteration index k=0.
Step 2 (iteration)while  Stopping criterion not met do
Computeg~k and l~k due to (21),Choose an adaptive stepsize by(28)μk∗=arg⁡minμk,j⁡EpxDk-μk,jW~k+1l~k,Compute a solutionx~k+1=xDk-μk∗W~k+1l~k,Update the solutionxDk+1←xDk-μk∗W~k+1l~k,Increase iteration indexk.end whileEpxDk+1-EpxDk<τ
Step 3 (solution). An optimal sparse solution x∗(Dk+1)←xDk+1.


## 2.3. Convergence Analysis

The convergence property of AGP is discussed as follows.Lemma 5.
AGP can determine at least one zero entry at each iteration.Due to (26), there are three cases that AGP determines zero entry at each iteration. The first case is that one entry of xDk is set to zero, if xDk moves from one octant to the coordinate surface of another distant octant. In the second case, more than one entry of xDk become zero when the new iteration solution x~k+1 exactly locates on the coordinate axis of another distant octant. In the third case, if x~k+1 locates on the side of the coordinate axis of another distant octant, we set x~k+1(j)=0 as x~k+1j<ε(j=1,…,Jk). Therefore, AGP can determine at least one zero entry at each iteration.Theorem 6.
Letx∗∈Rn with K nonzero entries be a sparse solution of problem (3). The number of iterations of AGP is no more than n-K.Ifx∗ has K nonzero entries, then the locations of n-K zero entries need to be determined. According to Lemma 5, AGP obtains multiple zero entries at each iteration, and these zero entries do not change in the remaining iterations based on the definition in (20). Therefore, the number of iterations of AGP is no more than n-K.Remark 7.
Theorem6 shows that AGP obtains a sparse solution within a finite number of iterations, while Theorem 1 shows that AST requires an infinite number of iterations to obtain a sparse solution. In theory, the number of iterations of AGP is less than AST.Figure2 gives an example to show the improved convergence performance of AGP compared to AST. There are three sparse solutions x1∗,x2∗,x3∗∈R3, where x3∗ is the global optimal sparse solution. To clearly display the iteration process of AGP, we return all xDk to three dimensional space, which form a sequence {xk}k=1L, where xk(Dk)←xDk represents that the entries of xDk located in Dk which are assigned to xk.Figure 2
Iteration processes of AST and AGP. (a) Sequence solved by AST converges tox1∗. (b) Sequence solved by AGP converges to x3∗. (c) Iteration process of AST. (d) Iteration process of AGP.
(a) (b) (c) (d)Starting fromx0, a sequence {xk}k=16solved by AST converges to x1∗ in Figure 2(a). Figure 2(c) shows that all iteration solutions concentrate in the attraction basin of x1∗ in the contour map. The second iteration solution of AGP in Figure 2(b), however, moves away from x1∗ and reaches x3∗. In Figure 2(d), the iteration solution moves out of the attraction basin of x1∗ and enters the attraction basin of x3∗, in which the adaptive stepsize plays an important role. This example verifies that AGP can find a sparser solution than AST by calculating the minimum point of the search direction at each iteration.


## 2.4. Comparison of Convergence Performance

To compare the convergence performance of AST and AGP, we give an experiment by the followinglp-norm problem(29)minE0.5x=∑i=18xi0.5s.t.x1+9x2+x3+9x4+2x5+x6+6x7+7x8=11.511x1+9x2+4x3+5x4+3x5+10x6+x7+4x8=1310x2+3x3+10x4+x5+6x6+10x7+6x8=16.2.There exist two sparse solutions x1∗=(0,0.9453,0,0,0,0.4061,0.4310,0)T and x2∗=(0,0,0,1.2,0,0.7,0,0)T, where x2∗ is the global optimal sparse solution. We choose x0=A+y as an initial point. Comparing the results in Table 1 with Table 2, we see that AGP quickly finds x2∗ in smaller and smaller subspace, while AST limited by the initial point just obtains the suboptimal solution x1∗. On the other hand, the computing times of AST and AGP are 0.0063 s and 0.0089 s, respectively. AGP costs some time to find an adaptive stepsize at each iteration, but it can obtain the global minimizer. Obviously, it is more important to find the global optimal sparse solution of problem (3).Table 1
List of the partial iteration solutions solved by AST.
k x k T 1 (0.0339, 0.5510, 0.0625, 0.3716, 0.0024, 0.4874, 0.3344, 0.0860) 3 (−0.0000, 0.7245, 0.0007, 0.2784, −0.0000, 0.4747, 0.3310, 0.0017) 5 (−0.0000, 0.8575, 0.0000, 0.1115, −0.0000, 0.4334, 0.3910, 0.0000) 7 (−0.0000, 0.9379, 0.0000, 0.0094, −0.0000, 0.4084, 0.4276, 0.0000) 9 (−0.0000, 0.9453, 0.0000, 0.0000, −0.0000, 0.4061, 0.4310, 0.0000)Table 2
List of the partial iteration solutions solved by AGP.
k x D k T D k 1 (0.0030, 0.6181, 0, 0.3752, −0.0115,0.5101, 0.2972,0.0410) ( 1,2 , 3,4 , 5,6 , 7,8 ) 2 (−0.0005, 0.6860, 0.3288, 0.0017, 0.4870, 0.3128) ( 1,2 , 4,5 , 6,7 ) 3 (−0.0070, 1.1946, 0.0229, 0.7034, 0.0010) ( 1,4 , 5,6 , 7 ) 4 (1.2000, 0.7000) ( 4,6 )


## 3. Application of Adaptive Gradient Projection Algorithm in Compressed Spectrum Sensing

The Compressive Spectrum Sensing (CSS) is considered for this study, because it performs the same tasks as signal sparse representation. In [15, 16], the model of CSS is formulated as follows:(30)H0:y=Φw,PU  absentH1:y=Φs+w,PU  present,where y is a measurement, s is a Primary User (PU) signal, w is a Gaussian noise, s+w is a Secondary User (SU) received signal, and Φ∈Rm×n is a Gaussian random matrix. Assume that s and w can be represented on the discrete cosine basis Ψ, (i.e., s=Ψxs and w=Ψxw), where xs and xw are spectrum coefficients. Let A=ΦΨ; the model in (30) can be reformulated as (31)H0:y=Axw,PUabsentH1:y=Axs+xw=Axsw,PUpresent.CSS intends to reconstruct xsw∗ from y=Axsw, so the reconstruction error εr=Φxsw∗-Φxsw2/Φxsw2 is used to evaluate the reconstruction performance.Corresponding tos and s+w in Figure 3(a), Figure 3(b) shows that xs has K=4 nonzero entries, while xw is distributed throughout the frequency domain. The reconstructed spectrum coefficient is obtained by solving the following problem (32)minxE0.7xsw=∑i=164xswi0.7s.t.y=Axsw,where A∈R20×64. After 21 iterations, xAST∗ solved by AST in Figure 3(d) is unsatisfactory, while xAGP∗ solved by AGP converges to xsw after 17 iterations. The corresponding computing times of AST and AGP are 0.0154 s and 0.0227 s, respectively. The reconstructed signals ΦxAST∗ and ΦxAGP∗ are shown in Figure 3(c), and the reconstruction errors are 27.22% and 9.99%, respectively. At the cost of a little computing time, the reconstruction performance of AGP is improved compared to AST in noise environment, so AGP exhibits better performance of noise suppression than AST.Figure 3
Reconstruction of the SU received signal using AST and AGP, respectively. (a) PU signals and SU received signal s+w. (b) Coefficients xs and xsw. (c) Reconstructed SU received signals solved by AST and AGP. (d) Reconstructed coefficients solved by AST and AGP.
(a) (b) (c) (d)Note that the characteristic of noise suppressing can greatly improve the detection performance of CSS, especially when the number of nonzero entriesK is not given in advance. We can reconstruct the SU received signal by choosing some larger nonzero entries of xsw∗ with a threshold η. Setting η=10, Figure 4(b) shows the denoising spectrum coefficients are sparser than the coefficients in Figure 3(d). The corresponding reconstructed SU received signals are shown in Figure 4(a). The reconstruction errors reduce to 21.71% and 8.50%. Meanwhile, the variance σw2 of white noise w reduces to σw^2.Figure 4
SU received signals are reconstructed with the denoising spectrum coefficients solved by AST and AGP, respectively. (a) Reconstructed SU received signals based on AST and AGP. (b) Denoising spectrum coefficients solved by AST and AGP.
(a) (b)Next, we consider the detection performance using the reconstructed SU signal with denoising coefficient. LetPf be a false alarm probability and λ be a judgment threshold. Then, a binary hypothesis testing problem is used to determine whether the PU is present(33)pd=0,H0:esd<λ1,H1:esd≥λ,where e(sd)=sd22 denotes the energy of the detection signal sd=Ψxd. The Nt Monte Carlo experiments are performed to test the detection probability Pd=Nd/Nt, where Nd is the number of accurately detecting PU signal. Given Pf=0.05, Nt=100, Figure 5 shows that the Energy Detection (ED) method [17] exhibits high mistaken probabilities in low signal-to-noise-ratio (SNR) environments. However, the detection probabilities of AST, AGP, IRL1, and ITM are greatly enhanced, when the reconstructed SU received signals are solved by the denoising spectrum coefficients. For example, when SNR equals to −5 dB, the detection probabilities using AST, AGP, IRL1, and ITM improve by 75.47%, 79.25%, 58.49%, and 47.17% compared with ED. Furthermore, when SNR changes from −15 dB to −1 dB, AGP shows better detection performance than AST, IRL1, and ITM because of its improved reconstruction performance. Figure 6 shows the corresponding computing time of five reconstruction algorithms, in which the time consumption of AGP increases at most 43.66% and 23.39% compared with ITM and AST. Spending a little more computing time, AGP can attain the best result of spectrum sensing especially in low SNR environment.Figure 5
Comparison of the detection performance using ED, ITM, AST, AGP, and IRL1 for different SNRs.Figure 6
Comparison of the computing time using ED, ITM, AST, AGP, and IRL1 for different SNRs.Note that the sparsity of the spectrum coefficient vector has impact on the reconstruction performance oflp-norm minimization. Given SNR is −7 dB, Figure 7 displays that the detection probabilities of AST, AGP, IRL1, and ITM descend whenKchanges from 2 to 10. This is because the measurement vector y∈R20 in (32) is not able to attain the whole information of a SU received signal whenKis larger than 6. Therefore, the unsatisfactory reconstruction results of lp-norm minimization greatly affect the detection performance of CSS via AST, IRL1, and ITM, while the performance degradation of CSS via AGP is slower than that of the three reconstruction algorithms. Meanwhile, AST, AGP, IRL1, and ITM cost more computing time to find the sparse solution in Figure 8. The above results reveal that the detection performance of CSS needs to be improved when the number of measurement is insufficient. ED determines the state of PU by measuring the energy of a SU received signal, so the property of the sparsity has little impact on its detection result and computing time.Figure 7
Comparison of the detection performance using ED, ITM, AST, AGP, and IRL1 for different sparsity of the spectrum coefficient vector.Figure 8
Comparison of the computing time using ED, ITM, AST, AGP, and IRL1 for different sparsity of the spectrum coefficient vector.


## 4. Conclusions

Signal sparse representation has become a fundamental tool that is embedded into various application systems. One of its fundamental problems is finding a sparse coefficient. In this paper, we develop a novel AGP algorithm to solve thelp-norm minimization. Theoretical analysis demonstrates that AGP can find a sparser solution than AST, because it avoids the iteration solutions concentrating in the attraction basin of a suboptimal sparse solution. Applying AGP to compressed spectrum sensing, it can obtain the better detection performance than ED, AST, IRL1, and ITM by spending a little more computing time. Future research will extend AGP to more scenarios.



---

*Source: 9547934-2018-05-14.xml*