# An Adaptive Prediction-Correction Method for Solving Large-Scale Nonlinear Systems of Monotone Equations with Applications

Authors: Gaohang Yu; Shanzhou Niu; Jianhua Ma; Yisheng Song
Journal: Abstract and Applied Analysis
 (2013)

---

## Abstract

Combining multivariate spectral gradient method with projection scheme, this paper presents an adaptive prediction-correction method for solving large-scale nonlinear systems of monotone equations. The proposed method possesses some favorable properties: (1) it is progressive step by step, that is, the distance between iterates and the solution set is decreasing monotonically; (2) global convergence result is independent of the merit function and its Lipschitz continuity; (3) it is a derivative-free method and could be applied for solving large-scale nonsmooth equations due to its lower storage requirement. Preliminary numerical results show that the proposed method is very effective. Some practical applications of the proposed method are demonstrated and tested on sparse signal reconstruction, compressed sensing, and image deconvolution problems.


---

## Body

## 1. Introduction

Considering the problem to find solutions of the following nonlinear monotone  equations:(1)g(x)=0,
where g:ℜn→ℜn is a continuous and monotone, that is, 〈g(x)-g(y),x-y〉≥0 for all x,y∈ℜn.Nonlinear monotone equations arise in many practical applications such as ballistic trajectory computation [1] and vibration systems [2], the first-order necessary condition of the unconstrained convex optimization problem, and the subproblems in the generalized proximal algorithms with Bregman distances [3]. Moreover, we can convert some monotone variational inequality into systems of nonlinear monotone equations by means of fixed point maps or normal maps [4] if the underlying function satisfies some coercive conditions. Solodov and Svaiter [5] proposed a projection method for solving (1). A nice property of the projection method is that the whole sequence of iterates is always globally convergent to a solution of the system without any additional regularity assumptions. Moreover, Zhang and Zhou [6] presented a spectral gradient projection (SG) method for solving systems of monotone equations which combines a modified spectral gradient method and projection method. This method is shown to be globally convergent if the nonlinear monotone equations is Lipschitz continuous. Xiao et al. [7] proposed a spectral gradient method to minimize a nonsmooth minimization problem, arising from spare solution recovery in compressed sensing, consisting of a least-squares data-fitting term and a ℓ1-norm regularization term. This problem is firstly formulated as a convex quadratic program (QP) problem and then reformulated to an equivalent nonlinear monotone equation. Furthermore, Yin et al. [8] developed a nonlinear conjugate gradient method for ℓ1-norm regularization problems in compressed sensing. Yu [9, 10] extended the spectral gradient method and conjugate gradient-type method to solve large-scale nonlinear system of equations, respectively. Recently, the authors in [11] proposed a multivariate spectral gradient projection method for solving nonlinear monotone equations with convex constraints. Numerical results show that multivariate spectral gradient method (MSG) could improve its performance very well.Following this line, based on multivariate spectral gradient method (MSG), we present an adaptive prediction-correction method for solving nonlinear monotone  equations  (1) in the next section. Its global convergence result is established, which is independent of the merit function and Lipschitz continuity. Section 3 presents some numerical experiments to demonstrate and test its practical performance on compressed sensing and image deconvolution problems. Finally, we have a conclusion section.


## 2. Adaptive Prediction-Correction Method

Considering the projection method [5] for solving nonlinear monotone  equations  (1), suppose that we have obtained a direction dk. By performing some kind of line search procedure along the direction dk, a point zk=xk+αkdk can be computed such that
(2)〈g(zk),xk-zk〉>0.
By the monotonicity of g, for any x- such that g(x-)=0, we have
(3)〈g(zk),x--zk〉≤0.
Thus, the hyperplane
(4)Hk={x∈ℜn∣〈g(zk),x-zk〉=0}
strictly separates the current iterate xk from solutions of the systems of monotone equations. Once we get the separating hyperplane, the next iterate xk+1 is computed by projecting xk on it.Recalling the multivariate spectral gradient (MSG) method [12] for minimization problem min{f(x)∣x∈ℜn}, its iterative formula is defined by xk+1=xk-diag{1/λk1,1/λk2,…,1/λkn}gk, where gk is the gradient of f at xk and diag{λk1,λk2,…,λkn} is obtained by minimizing
(5)∥diag{λ1,λ2,…,λn}sk-1-yk-1∥2
with respect to {λi}i=1n, where sk-1=xk-xk-1,yk=gk-gk-1. In particular, when f(x) has positive definite diagonal Hessian matrix, multivariate spectral gradient method will be convergent quadratically [12].Let theith column of yk and sk denoted by ski and yki, respectively. Combining multivariate spectral gradient method with projection scheme, we can present an adaptive prediction-correction method for solving monotone  equations  (1) as follows.Algorithm 1 (multivariate spectral gradient (MSG) method).
Givenx0∈ℜn, β∈(0,1), σ∈(0,1), 0<ɛ<1, r≥0, δ>0. Set k=0.Step 1.
If∥gk∥=0, stop.Step 2.
(a) Ifk=0, set dk=-g(xk).
(b) else ifyk-1i/sk-1i>0, then set λki=yk-1i/sk-1i;  otherwise set λki=(sk-1Tyk-1)/(sk-1Tsk-1) for i=1,2,…,n, where sk-1=xk-xk-1, yk-1=g(xk)-g(xk-1)+rsk-1.
(c) else ifλki≤ɛ or λki≥1/ɛ, set λki=δ for i=1,2,…,n.
Set dk=-diag{1/λk1,1/λk2,…,1/λkn}gk.Step 3 (prediction step).
Compute step lengthαk, set zk=xk+αkdk, where αk=βmk with mk being the smallest nonnegative integer m such that
(6)-〈g(xk+βmdk),dk〉≥σβm∥dk∥2.Step 4 (correction step).
Compute(7)xk+1=xk-〈g(zk),xk-zk〉∥g(zk)∥2g(zk).Step 5.
Setk=k+1 and go to Step 1.By using multivariate spectral gradient method, we obtain prediction sequence{zk}, and then we get correction sequence {xk} via projection. It follows from (17) that xk+1 will be more close to the solution x* than xk, that is, the sequence {xk} makes progress iterate by iterate. From Step 2(c), we have
(8)min{ϵ,1δ}∥gk∥≤∥dk∥≤max{1ϵ,1δ}∥gk∥.In what follows, we assume thatg(xk)≠0 for all k≥0; otherwise we have got the solution of the problem (1). The following lemma states that Algorithm 1 is well defined.Lemma 2.
There exists a nonnegative numbermk satisfying (6) for all k≥0.Proof.
Suppose that there exists ak0≥0 such that (6) is not satisfied for any nonnegative integer m, that is,
(9)-〈g(xk0+βmdk),dk0〉<σβm∥dk0∥2,∀m≥1.
Let m→∞ and using the continuity of g yields
(10)-〈g(xk0),dk0〉≤0.
From Steps 1, 2, and 5, we have
(11)g(xk)≠0,dk≠0,∀k≥0.
Thus,
(12)-〈g(x0),d0〉=〈g(x0),g(x0)〉>0,-〈g(xk),dk〉=〈g(xk),diag{1λk1,1λk2,…,1λkn}g(xk)〉≥min{ϵ,1δ}∥gk∥2>0,∀k≥1.
The last inequality contradicts (10). Hence the statement is proved.Lemma 3.
Let{xk} and {zk} be any sequence generated by Algorithm 1. Suppose that g is monotone and that the solution set of (1) is not empty, then {xk} and {zk} are both bounded. Furthermore, it holds that
(13)limk→∞∥xk-zk∥=0,(14)limk→∞∥xk+1-xk∥=0.Proof.
From (6), we have
(15)〈g(zk),xk-zk〉=-αk〈g(zk),dk〉≥σαk2∥dk∥2=σ∥xk-zk∥2.
Let x* be an arbitrary point such that g(x*)=0. Taking account of the monotonicity of g, we have
(16)〈g(zk),xk-x*〉=〈g(zk),xk-zk〉+〈g(zk),zk-x*〉≥〈g(zk),xk-zk〉+〈g(x*),zk-x*〉=〈g(zk),xk-zk〉.
From (7), (14), and (16), it follows that
(17)∥xk+1-x*∥2=∥xk-〈g(zk),xk-zk〉∥g(zk)∥2g(zk)-x*∥2=∥xk-x*∥2-〈g(zk),xk-zk〉2∥g(zk)∥2≤∥xk-x*∥2-σ2∥xk-zk∥4∥g(zk)∥2.
Hence the sequence {∥xk-x*∥} is decreasing and convergent; moreover, the sequence {∥xk∥} is bounded. Since the g is continuous, there exists a constant C>0 such that
(18)∥g(zk)∥≤C.
By the Cauchy-Schwarz inequality, the monotonicity of g and (15), we have
(19)∥g(xk)∥≥〈g(xk),xk-zk〉∥xk-zk∥≥〈g(zk),xk-zk〉∥xk-zk∥≥σ∥xk-zk∥.
From (18) and (19), we obtain that {zk} is also bounded. It follows from (17) and (18) that
(20)σ2C2∑k=1∞‍∥xk-zk∥4≤∑k=1∞‍(∥xk-x*∥2-∥xk+1-x*∥2)<∞,
which implies
(21)limk→∞∥xk-zk∥=0.
From (7), using the Cauchy-Schwarz inequality, we obtain that
(22)∥xk+1-xk∥=〈g(zk),xk-zk〉∥g(zk)∥≤∥xk-zk∥.
Thus limk→∞∥xk+1-xk∥=0.
The proof is complete.Now we can establish the global convergence of Algorithm1.Theorem 4.
Letxk be generated by Algorithm 1; then {xk} converges to an x- such that g(x-)=0.Proof.
Sincezk=xk+αkdk, it follows from Lemma 3 that
(23)limk→∞αk∥dk∥=limk→∞∥xk-zk∥=0.
From (8) and (18), it holds that {dk} is bounded.
Now we consider the following two possible cases:(i)
liminfk→∞∥d(xk)∥=0.(ii)
liminfk→∞∥d(xk)∥>0.
If (i) holds, from (8), we have liminfk→∞∥g(xk)∥=0. By the continuity of g and the boundedness of {xk}, it is clear that the sequence {xk} has some accumulation point x- such that g(x-)=0. From (17), we also have that the sequence {∥xk-x-∥} converges. Therefore, {xk} converges to x-.
If (ii) holds, from (8), we have liminfk→∞∥g(xk)∥>0. By (23), it holds that
(24)limk⟶∞αk=0.
By the line search rule, we have for all k sufficiently large, mk-1 will not satisfy (6). This means
(25)-〈g(xk+βmk-1dk),dk〉<σβmk-1∥dk∥2.
Since the sequences {xk}, {dk} are bounded, we choose a subsequence, let k→∞ in (25), we obtain that
(26)-〈g(x~),d~〉≤0,
where x~,d~ are limits of corresponding subsequences. On the other hand, by (8), it holds that
(27)-〈g(x~),d~〉>0,
which contradicts (26). Hence, liminfk→∞∥d(xk)∥>0 is impossible.
The proof is complete.


## 3. Numerical Experiments

In this section, we report some preliminary numerical experiments to test our algorithms with comparison to spectral gradient projection method [6]. Firstly, in Section 3.1 we test these algorithms on solving nonlinear systems of monotone equations. Secondly, in Section 3.2, we apply HSG-V algorithm to solve ℓ1-norm regularization problem arising from compressed sensing. All of numerical experiments were performed under Windows XP and MATLAB 7.0 running on a personal computer with an Intel Core 2 Duo CPU at 2.2 GHz and 2 GB of memory.


### 3.1. Test on Nonlinear Systems of Monotone Equations

We test the performance of our algorithms for solving some monotone equations (see details in the appendix). The termination condition is∥g(xk)∥≤10-6. The parameters are specified as follows. For MSG method, we set β=0.5,σ=0.01,ϵ=10-10,r=0.01. In Step 2, the parameter δ is chosen in the following way:
(28)δ={1if∥g(xk)∥>1,∥g(xk)∥-1if10-5≤∥g(xk)∥≤1,105if∥g(xk)∥<10-5.Firstly, we test the performance of the MSG method on the Problem1 with n=1000, the initial point x0=(1,1,…,1)T. Figure 1 displays the performance of MSG method for Problem 1 which indicates that prediction sequences {zk} are better than correction sequences {xk} at most time. Taking this into account, we relax the MSG method such that Step 4 in Algorithm 1 is replaced by the following: if modxk+1=xk-〈g(zk),xk-zk〉∥g(zk)∥2g(zk),eslsexk+1=zk,end.(a) Norm of sequence versus iteration for MSG algorithm. (b) MSG-V algorithm versus MSG and SG algorithm, where the iteration has been cut to 100 for the SG algorithm.
(a)
(b)In this case, we refer to this modification as “MSG-V” method. WhenM≡1, the above algorithm will reduce to Algorithm 1. The performance of those methods on the  Problem (1) is shown in Figure 1, from which we can see that the MSG-V method is preferable quite frequently to the SG method while it also outperforms the MSG method. Furthermore, motivated to accelerate the performance of MSG-V method, we present a hybrid spectral gradient (HSG-V) algorithm. The main idea of the HSG-V algorithm is to run MSG-V algorithm when yk-1i/sk-1i>0 for i=1,2,…,n; otherwise switch to spectral gradient projection (SG) method.And then we compare the performance of MSG method, MSG-V method, and HSG-V method with the spectral gradient projection (SG) method in [6] on test problems with different initial points. We set β=0.5, σ=0.01, r=0.01 in the spectral gradient projection (SG) method in [6], and M=10 for MSG-V method and HSG-V method.Numerical results are shown in Tables1, 2, 3, 4, 5, and 6 with the form NI/NF/T/BK, where we report the dimension of the problem (n), the initial points (Init), the number of iteration (NI), the number of function evaluations (NF), and the CPU time (Time) in seconds and the number of backtracking (BK). The symbol “F” denotes that the method fails for this test problem, or the number of the iterations is greater than 10000.Table 1
Numerical results for SG/MSG methods on Problem1.
Init (n)
SG
MSG
NI/NF/Time/BK
NI/NF/Time/BK
x
1 (100)
7935/56267/7.375/6
1480/9774/1.609/1
x
2 (100)
4365/25627/3.125/2
981/6223/0.906/1
x
3 (100)
3131/18028/2.11/7
1139/8240/1.266/1
x
4 (100)
2287/13025/1.453/4
294/1091/0.172/1
x
5 (100)
1685/9535/1.188/3
212/640/0.093/1
x
6 (100)
1788/10238/1.156/3
243/745/0.11/1
x
7 (100)
1608/9236/1.047/2
220/664/0.109/1
x
8 (100)
1629/9283/1.172/4
185/558/0.078/1
x
9 (100)
1478/8407/0.953/4
8/20/0.016/0
x
10 (100)
1611/9131/1.031/3
184/555/0.078/1
x
11 (100)
1475/8404/0.938/4
39/99/0.016/0
x
12 (100)
1226/6938/0.797/5
19/46/0.016/0
x
1 (200)
F
2846/20922/6.328/1
x
2 (200)
8506/50896/11.985/4
1535/11707/3.5/1
x
3 (200)
6193/37063/8.687/7
1826/15256/4.5/0
x
4 (200)
4563/27333/6.5/7
266/1055/0.312/1
x
5 (200)
3343/19760/5.078/4
376/1133/0.422/1
x
6 (200)
3620/21536/6.11/7
200/617/0.172/1
x
7 (200)
3249/19340/4.531/6
148/444/0.125/0
x
8 (200)
3253/19383/4.5/5
323/973/0.344/1
x
9 (200)
2974/17649/4.109/4
8/21/0.015/0
x
10 (200)
3256/19214/5.062/4
308/928/0.391/1
x
11 (200)
2995/17784/5.266/4
42/110/0.047/0
x
12 (200)
2483/14698/3.453/3
27/63/0.047/0
x
1 (300)
F
F
x
2 (300)
F
3374/29158/12.782/1
x
3 (300)
9334/57185/20.985/2
1293/10136/4.656/1
x
4 (300)
6734/41348/14.735/4
406/1601/0.687/1
x
5 (300)
5011/30857/11.265/7
235/706/0.282/1
x
6 (300)
5380/33167/11.875/6
300/919/0.546/1
x
7 (300)
4812/29977/10.657/6
187/559/0.235/0
x
8 (300)
4825/29770/10.656/4
158/466/0.187/0
x
9 (300)
4396/27551/10.062/3
8/21/0.016/0
x
10 (300)
4774/29731/10.969/3
203/610/0.266/1
x
11 (300)
4411/27366/9.859/8
52/144/0.062/0
x
12 (300)
3656/23021/8.36/6
32/75/0.031/0
x
1 (500)
F
F
x
2 (500)
F
4915/46911/37.906/1
x
3 (500)
F
1754/15152/12.375/1
x
4 (500)
F
489/1905/1.547/1
x
5 (500)
8360/51414/37.485/6
269/803/0.797/1
x
6 (500)
8996/56185/39.75/6
295/900/0.734/1
x
7 (500)
8128/50525/35.703/2
256/766/0.672/1
x
8 (500)
8089/50688/36.484/4
387/1163/1.156/0
x
9 (500)
7453/46083/33.75/2
8/22/0.016/0
x
10 (500)
8118/50185/35.985/4
403/1211/1.187/1
x
11 (500)
7525/46275/33.14/4
55/149/0.11/0
x
12 (500)
6235/38408/28.047/9
38/95/0.11/0
x
1 (1000)
F
F
x
2 (1000)
F
8998/93619/200.78/0
x
3 (1000)
F
2939/26376/55.86/0
x
4 (1000)
F
783/3016/6.438/0
x
5 (1000)
F
364/1085/2.75/0
x
6 (1000)
F
429/1309/3.266/0
x
7 (1000)
F
499/1500/3.687/1
x
8 (1000)
F
481/1444/3.969/0
x
9 (1000)
F
8/23/0.047/0
x
10 (1000)
F
346/1032/2.515/0
x
11 (1000)
F
74/201/0.391/0
x
12 (1000)
F
50/124/0.234/0Table 2
Numerical results for MSG-V/HSG-V methods on Problem1.
Init (n)
MSG-V
HSG-V
NI/NF/Time/BK
NI/NF/Time/BK
x
1 (100)
48/162/0.031/0
139/471/0.14/0
x
2 (100)
37/120/0.016/0
165/572/0.079/7
x
3 (100)
29/93/0.015/0
158/522/0.062/2
x
4 (100)
22/61/0.016/0
134/461/0.063/0
x
5 (100)
8/22/0.016/0
8/22/0.015/0
x
6 (100)
9/26/0.015/0
9/26/0.015/0
x
7 (100)
8/22/0.016/0
8/22/0.016/0
x
8 (100)
8/21/0.015/0
8/21/0.016/0
x
9 (100)
8/20/0.015/0
8/20/0.016/0
x
10 (100)
24/75/0.031/1
24/75/0.031/1
x
11 (100)
8/21/0.015/0
8/21/0.016/0
x
12 (100)
6/16/0.016/0
6/16/0.016/0
x
1 (200)
43/134/0.047/0
174/587/0.172/0
x
2 (200)
39/142/0.047/0
184/640/0.172/0
x
3 (200)
35/118/0.031/1
205/693/0.188/0
x
4 (200)
19/59/0.031/0
148/519/0.125/0
x
5 (200)
8/23/0.296/0
8/23/0.015/0
x
6 (200)
9/27/0.016/0
9/27/0.016/0
x
7 (200)
8/23/0.016/0
8/23/0.016/0
x
8 (200)
8/22/0.015/0
8/22/0.016/0
x
9 (200)
8/21/0.016/0
8/21/0.015/0
x
10 (200)
25/79/0.046/1
25/79/0.031/1
x
11 (200)
8/22/0.016/0
8/22/0.016/0
x
12 (200)
6/17/0.015/0
6/17/0.016/0
x
1 (300)
50/200/0.094/0
246/865/0.375/4
x
2 (300)
56/196/0.093/1
265/977/0.375/8
x
3 (300)
33/119/0.047/0
345/1253/0.515/7
x
4 (300)
28/90/0.031/0
244/825/0.329/0
x
5 (300)
8/23/0.016/0
8/23/0.015/0
x
6 (300)
9/27/0.015/0
9/27/0.016/0
x
7 (300)
8/23/0.016/0
8/23/0.015/0
x
8 (300)
8/22/0.016/0
8/22/0.016/0
x
9 (300)
8/21/0.016/0
8/21/0.016/0
x
10 (300)
26/82/0.031/1
26/82/0.031/1
x
11 (300)
8/23/0.016/0
8/23/0.016/0
x
12 (300)
6/18/0.015/0
6/18/0.015/0
x
1 (500)
51/218/0.188/0
290/1054/0.765/8
x
2 (500)
41/132/0.125/0
330/1159/0.953/0
x
3 (500)
47/164/0.14/1
383/1394/0.969/0
x
4 (500)
28/91/0.125/0
246/864/0.609/0
x
5 (500)
9/26/0.047/0
9/26/0.032/0
x
6 (500)
9/28/0.031/0
9/28/0.015/0
x
7 (500)
9/26/0.047/0
9/26/0.032/0
x
8 (500)
8/23/0.032/0
8/23/0.015/0
x
9 (500)
8/22/0.031/0
8/22/0.016/0
x
10 (500)
27/86/0.062/1
27/86/0.062/1
x
11 (500)
8/23/0.016/0
8/23/0.032/0
x
12 (500)
6/19/0.016/0
6/19/0.015/0
x
1 (1000)
49/205/0.547/0
437/1656/3.094/2
x
2 (1000)
41/138/0.344/0
506/1824/3.406/0
x
3 (1000)
49/181/0.437/1
607/2137/4.094/2
x
4 (1000)
37/121/0.282/1
426/1582/3/0
x
5 (1000)
9/27/0.062/0
9/27/0.062/0
x
6 (1000)
9/29/0.063/0
86/308/0.579/6
x
7 (1000)
9/27/0.046/0
9/27/0.046/0
x
8 (1000)
8/24/0.063/0
8/24/0.047/0
x
9 (1000)
8/23/0.047/0
12/44/0.078/2
x
10 (1000)
29/93/0.172/1
29/93/0.188/1
x
11 (1000)
8/24/0.047/0
8/24/0.078/0
x
12 (1000)
6/20/0.031/0
6/20/0.078/0Table 3
Numerical results for SG/MSG methods on Problem2.
Init (n)
SG
MSG
NI/NF/Time/BK
NI/NF/Time/BK
x
1 (100)
F
349/712/0.094/0
x
2 (100)
F
352/711/0.094/0
x
3 (100)
F
351/711/0.094/0
x
4 (100)
F
353/717/0.109/0
x
5 (100)
F
346/696/0.094/0
x
6 (100)
F
347/698/0.078/0
x
7 (100)
F
345/694/0.109/0
x
8 (100)
F
320/644/0.078/0
x
9 (100)
359/719/0.031/0
359/719/0.047/0
x
10 (100)
22/67/0.015/1
22/67/0.015/1
x
11 (100)
434/869/0.047/0
434/869/0.063/0
x
12 (100)
424/849/0.031/0
424/849/0.047/0
x
1 (200)
F
437/888/0.218/0
x
2 (200)
F
439/885/0.219/0
x
3 (200)
F
438/885/0.219/0
x
4 (200)
F
440/891/0.219/0
x
5 (200)
F
433/870/0.343/0
x
6 (200)
F
434/872/0.203/0
x
7 (200)
F
432/868/0.219/0
x
8 (200)
F
358/720/0.172/0
x
9 (200)
372/745/0.047/0
371/743/0.063/0
x
10 (200)
22/66/0.015/0
23/70/0.015/1
x
11 (200)
544/1089/0.063/0
544/1089/0.094/0
x
12 (200)
534/1069/0.047/0
534/1069/0.109/0
x
1 (300)
F
498/1010/0.375/0
x
2 (300)
F
500/1007/0.375/0
x
3 (300)
F
500/1009/0.375/0
x
4 (300)
F
501/1013/0.36/0
x
5 (300)
F
494/992/0.375/0
x
6 (300)
F
495/994/0.375/0
x
7 (300)
F
494/992/0.359/0
x
8 (300)
F
368/740/0.266/0
x
9 (300)
373/747/0.047/0
373/747/0.093/0
x
10 (300)
22/66/0.015/0
23/70/0.016/1
x
11 (300)
621/1243/0.078/0
621/1243/0.157/0
x
12 (300)
611/1223/0.078/0
611/1223/0.25/0
x
1 (500)
F
588/1190/0.781/0
x
2 (500)
F
590/1187/0.781/0
x
3 (500)
F
589/1187/0.781/0
x
4 (500)
F
591/1193/0.797/0
x
5 (500)
F
584/1172/0.782/0
x
6 (500)
F
585/1174/0.906/0
x
7 (500)
F
583/1170/0.797/0
x
8 (500)
F
372/748/0.468/0
x
9 (500)
373/747/0.078/0
373/747/0.125/0
x
10 (500)
22/66/0.015/0
23/70/0.016/1
x
11 (500)
734/1469/0.141/0
734/1469/0.234/0
x
12 (500)
724/1449/0.14/0
724/1449/0.25/0
x
1 (1000)
F
736/1486/2.563/0
x
2 (1000)
F
739/1485/2.406/0
x
3 (1000)
F
738/1485/2.578/0
x
4 (1000)
F
740/1491/2.407/0
x
5 (1000)
F
733/1470/2.562/0
x
6 (1000)
F
734/1472/2.531/0
x
7 (1000)
F
732/1468/2.407/0
x
8 (1000)
F
372/748/1.125/0
x
9 (1000)
373/747/0.125/0
373/747/0.343/0
x
10 (1000)
24/73/0.016/1
24/73/0.032/1
x
11 (1000)
921/1843/0.281/0
921/1843/0.562/0
x
12 (1000)
912/1825/0.266/0
912/1825/0.547/0Table 4
Numerical results for MSG-V/HSG-V methods on Problem2.
Init (n)
MSG-V
HSG-V
NI/NF/Time/BK
NI/NF/Time/BK
x
1 (100)
27/82/0.015/1
27/82/0.016/1
x
2 (100)
435/872/0.047/0
435/872/0.094/0
x
3 (100)
416/838/0.047/0
416/838/0.062/0
x
4 (100)
434/872/0.047/0
434/872/0.047/0
x
5 (100)
424/850/0.047/0
424/850/0.047/0
x
6 (100)
347/697/0.047/0
347/697/0.047/0
x
7 (100)
346/695/0.047/0
346/695/0.032/0
x
8 (100)
318/640/0.078/0
318/640/0.062/0
x
9 (100)
355/711/0.031/0
355/711/0.031/0
x
10 (100)
22/67/0.016/1
22/67/0.016/1
x
11 (100)
434/869/0.063/0
434/869/0.062/0
x
12 (100)
424/849/0.046/0
424/849/0.047/0
x
1 (200)
27/82/0.015/1
27/82/0.016/1
x
2 (200)
545/1092/0.094/0
545/1092/0.078/0
x
3 (200)
525/1056/0.094/0
525/1056/0.078/0
x
4 (200)
544/1092/0.094/0
544/1092/0.078/0
x
5 (200)
533/1068/0.093/0
533/1068/0.078/0
x
6 (200)
435/873/0.063/0
435/873/0.078/0
x
7 (200)
433/869/0.078/0
433/869/0.063/0
x
8 (200)
355/714/0.172/0
356/716/0.078/0
x
9 (200)
367/735/0.062/0
367/735/0.047/0
x
10 (200)
23/70/0.015/1
23/70/0.016/1
x
11 (200)
544/1089/0.094/0
544/1089/0.078/0
x
12 (200)
534/1069/0.094/0
534/1069/0.078/0
x
1 (300)
28/85/0.016/1
28/85/0.016/1
x
2 (300)
622/1246/0.14/0
622/1246/0.11/0
x
3 (300)
602/1210/0.156/0
602/1210/0.125/0
x
4 (300)
621/1246/0.25/0
621/1246/0.109/0
x
5 (300)
610/1222/0.125/0
610/1222/0.125/0
x
6 (300)
496/995/0.11/0
496/995/0.094/0
x
7 (300)
494/991/0.125/0
494/991/0.094/0
x
8 (300)
365/734/0.25/0
365/734/0.109/0
x
9 (300)
368/737/0.094/0
368/737/0.063/0
x
10 (300)
23/70/0.031/1
23/70/0.015/1
x
11 (300)
621/1243/0.141/0
621/1243/0.11/0
x
12 (300)
611/1223/0.125/0
611/1223/0.125/0
x
1 (500)
28/85/0.015/1
28/85/0.015/1
x
2 (500)
735/1472/0.25/0
735/1472/0.203/0
x
3 (500)
715/1436/0.219/0
715/1436/0.203/0
x
4 (500)
734/1472/0.25/0
734/1472/0.188/0
x
5 (500)
723/1448/0.219/0
723/1448/0.187/0
x
6 (500)
586/1175/0.187/0
586/1175/0.156/0
x
7 (500)
584/1171/0.204/0
584/1171/0.141/0
x
8 (500)
369/742/0.453/0
369/742/0.156/0
x
9 (500)
368/737/0.125/0
368/737/0.094/0
x
10 (500)
23/70/0.015/1
23/70/0.015/1
x
11 (500)
734/1469/0.219/0
734/1469/0.203/0
x
12 (500)
724/1449/0.234/0
724/1449/0.235/0
x
1 (1000)
28/85/0.016/1
28/85/0.047/1
x
2 (1000)
923/1848/0.531/0
923/1848/0.485/0
x
3 (1000)
902/1810/0.641/0
902/1810/0.437/0
x
4 (1000)
922/1848/0.516/0
922/1848/0.453/0
x
5 (1000)
911/1824/0.531/0
911/1824/0.453/0
x
6 (1000)
737/1477/0.406/0
737/1477/0.344/0
x
7 (1000)
733/1469/0.422/0
733/1469/0.344/0
x
8 (1000)
369/742/1.125/0
369/742/0.297/0
x
9 (1000)
368/737/0.219/0
368/737/0.172/0
x
10 (1000)
24/73/0.015/1
24/73/0.015/1
x
11 (1000)
921/1843/0.625/0
921/1843/0.438/0
x
12 (1000)
912/1825/0.563/0
912/1825/0.453/0Table 5
Numerical results for SG/MSG methods on Problem3.
Init (n)
SG
MSG
NI/NF/Time/BK
NI/NF/Time/BK
x
1 (100)
161/753/0.094/2
246/1062/0.296/3
x
2 (100)
103/424/0.062/3
185/794/0.219/2
x
3 (100)
118/517/0.063/2
204/935/0.266/5
x
4 (100)
63/224/0.031/1
194/894/0.25/2
x
5 (100)
63/234/0.031/2
149/662/0.187/3
x
6 (100)
81/307/0.047/2
191/831/0.235/1
x
7 (100)
64/237/0.031/2
168/738/0.203/1
x
8 (100)
53/194/0.032/2
94/378/0.109/1
x
9 (100)
53/192/0.015/2
178/808/0.219/3
x
10 (100)
76/288/0.047/2
229/1008/0.281/1
x
11 (100)
73/273/0.031/2
203/924/0.25/4
x
12 (100)
60/225/0.016/3
195/888/0.266/1
x
1 (200)
216/1203/0.468/2
251/1129/0.515/2
x
2 (200)
147/728/0.282/2
168/702/0.407/3
x
3 (200)
157/759/0.312/2
180/821/0.422/1
x
4 (200)
58/206/0.094/3
214/956/0.453/1
x
5 (200)
64/238/0.094/1
174/793/0.359/2
x
6 (200)
78/294/0.125/2
194/882/0.422/2
x
7 (200)
44/156/0.062/2
170/757/0.359/1
x
8 (200)
48/173/0.078/1
93/368/0.172/1
x
9 (200)
54/192/0.078/2
191/890/0.391/2
x
10 (200)
84/314/0.125/3
152/627/0.282/1
x
11 (200)
61/222/0.094/2
193/903/0.422/2
x
12 (200)
63/236/0.093/3
121/531/0.25/2
x
1 (300)
541/5455/20.282/3
247/1066/4.187/5
x
2 (300)
142/724/2.734/2
135/512/2.063/1
x
3 (300)
195/1084/4.031/2
197/892/3.5/1
x
4 (300)
55/196/0.734/2
193/868/3.328/2
x
5 (300)
68/254/0.953/2
154/693/2.703/4
x
6 (300)
77/295/1.11/2
241/1168/4.484/2
x
7 (300)
76/281/1.094/2
186/851/3.313/5
x
8 (300)
57/207/0.765/2
127/528/2/1
x
9 (300)
59/210/0.797/1
190/939/3.578/1
x
10 (300)
91/342/1.266/3
142/664/2.563/1
x
11 (300)
79/288/1.109/3
168/767/2.906/1
x
12 (300)
72/266/0.984/1
114/448/1.75/1
x
1 (500)
488/4021/42.907/1
212/927/9.985/1
x
2 (500)
240/1440/15.343/3
166/712/7.64/4
x
3 (500)
254/1544/16.485/1
228/1050/11.313/2
x
4 (500)
59/210/2.266/3
273/1564/16.843/3
x
5 (500)
70/261/2.75/2
189/905/9.781/2
x
6 (500)
82/313/3.328/2
190/866/9.266/1
x
7 (500)
76/284/3.078/3
149/642/6.984/1
x
8 (500)
59/215/2.282/2
97/381/4.141/1
x
9 (500)
51/185/1.985/2
439/2832/30.391/3
x
10 (500)
84/319/3.421/2
66/238/2.562/1
x
11 (500)
77/280/2.969/2
74/266/2.891/1
x
12 (500)
67/250/2.719/3
57/189/2.078/1
x
1 (1000)
2780/36160/1510.7/2
199/853/35.969/3
x
2 (1000)
331/2242/94.734/2
160/656/27.656/1
x
3 (1000)
352/2532/106.25/1
197/891/37.359/2
x
4 (1000)
71/260/10.891/1
182/794/33.985/2
x
5 (1000)
71/268/11.234/2
190/891/37.546/3
x
6 (1000)
84/319/13.422/3
160/698/29.188/4
x
7 (1000)
73/271/11.391/2
157/663/27.547/1
x
8 (1000)
50/182/7.578/2
112/446/18.641/4
x
9 (1000)
49/173/7.328/2
232/1162/48.656/1
x
10 (1000)
85/318/13.375/2
56/172/7.391/1
x
11 (1000)
81/297/12.485/3
61/185/7.781/1
x
12 (1000)
69/255/10.781/1
49/154/6.578/1Table 6
Numerical results for MSG-V/HSG-V methods on Problem3.
Init (n)
MSG-V
HSG-V
NI/NF/Time/BK
NI/NF/Time/BK
x
1 (100)
92/377/0.078/1
55/172/0.047/6
x
2 (100)
93/374/0.079/1
59/177/0.031/0
x
3 (100)
86/360/0.078/1
40/120/0.031/0
x
4 (100)
83/363/0.062/1
40/111/0.032/1
x
5 (100)
45/173/0.047/1
20/56/0.015/0
x
6 (100)
57/204/0.047/2
42/121/0.016/2
x
7 (100)
53/202/0.031/1
30/87/0.031/0
x
8 (100)
47/181/0.047/2
22/61/0.016/0
x
9 (100)
49/194/0.047/1
33/100/0.015/1
x
10 (100)
48/165/0.031/1
30/97/0.032/3
x
11 (100)
49/181/0.031/1
26/75/0.015/0
x
12 (100)
37/125/0.032/0
29/93/0.016/0
x
1 (200)
88/335/0.172/1
53/173/0.078/1
x
2 (200)
83/330/0.14/1
50/142/0.078/0
x
3 (200)
76/290/0.141/1
42/126/0.047/2
x
4 (200)
69/266/0.125/1
35/101/0.063/3
x
5 (200)
48/190/0.094/1
25/72/0.031/3
x
6 (200)
69/294/0.156/2
34/99/0.047/0
x
7 (200)
55/215/0.109/5
30/81/0.047/0
x
8 (200)
51/217/0.11/1
22/61/0.031/0
x
9 (200)
46/153/0.078/1
24/64/0.031/0
x
10 (200)
42/129/0.078/1
33/91/0.031/0
x
11 (200)
49/180/0.094/0
30/92/0.047/1
x
12 (200)
37/125/0.062/2
30/85/0.047/0
x
1 (300)
89/322/1.266/1
53/168/0.625/0
x
2 (300)
91/348/1.282/1
55/162/0.609/1
x
3 (300)
72/278/1.046/1
37/109/0.422/0
x
4 (300)
78/339/1.297/1
28/81/0.297/1
x
5 (300)
45/178/0.735/2
20/55/0.281/0
x
6 (300)
63/248/0.937/3
38/113/0.453/2
x
7 (300)
53/208/0.797/1
33/91/0.344/0
x
8 (300)
63/295/1.109/1
22/61/0.234/0
x
9 (300)
45/177/0.672/1
27/71/0.266/0
x
10 (300)
45/148/0.641/1
40/108/0.406/0
x
11 (300)
43/144/0.531/2
32/89/0.344/1
x
12 (300)
36/129/0.5/0
28/83/0.312/2
x
1 (500)
85/289/3.125/1
50/158/1.672/0
x
2 (500)
78/245/2.625/0
56/157/1.75/2
x
3 (500)
74/289/3.156/2
40/118/1.235/1
x
4 (500)
62/223/2.375/1
47/131/1.437/1
x
5 (500)
49/194/2.11/1
25/74/0.813/3
x
6 (500)
55/181/1.922/2
40/116/1.218/0
x
7 (500)
49/163/1.797/1
26/74/0.781/0
x
8 (500)
53/219/2.328/1
22/61/0.657/0
x
9 (500)
49/184/2/0
25/69/0.781/2
x
10 (500)
41/158/1.656/2
35/99/1.062/6
x
11 (500)
48/173/1.922/1
31/83/0.891/0
x
12 (500)
35/126/1.359/2
27/76/0.812/0
x
1 (1000)
97/376/15.688/3
50/165/6.922/3
x
2 (1000)
78/263/11.015/1
52/151/6.235/2
x
3 (1000)
80/303/12.766/1
44/128/5.343/1
x
4 (1000)
73/291/12.219/0
36/101/4.235/0
x
5 (1000)
43/165/6.968/1
22/66/2.75/2
x
6 (1000)
59/213/9.094/4
44/120/5.016/0
x
7 (1000)
55/201/8.438/1
27/78/3.281/3
x
8 (1000)
57/250/10.5/1
22/60/2.547/0
x
9 (1000)
46/166/7/0
29/80/3.266/4
x
10 (1000)
39/126/5.234/0
31/87/3.64/0
x
11 (1000)
47/165/6.969/1
35/96/4.032/3
x
12 (1000)
36/114/4.797/2
34/91/3.812/0As we can see from Tables1–6 that the HSG-V algorithm is preferable quite frequently to the SG method  and  also outperforms the MSG algorithm and MSG-V algorithm, since it can solve about 80% and 70% of the problems with the best time and the smallest number of function evaluations, respectively. We also find that the SG algorithm seems more sensitive to the initial points.Figure2 shows the performance of these algorithms relative to the number of function evaluations and CPU time, respectively, which were evaluated using the profiles of Dolan and Moré [13]. That is, for each algorithm, we plot the fraction P of problems for which the method is within a factor t of the smallest number of function evaluations/CPU time. Clearly, the left side of the figure gives the percentage of the test problems for which a method is the best one according to the number of function evaluations or CPU time, respectively. As we can see from Figure 2, “HSG-V” algorithm has the best performance.(a) Performance profiles for the number of function evaluations. (b) Performance profiles for the CPU time.
(a)
(b)


### 3.2. Test onℓ1-Norm Regularization Problem in Compressed Sensing

There has been considerable interest in solving theℓ1-norm regularized least-square problem
(29)minx∈ℜnf(x)≡12∥Ax-y∥22+μ∥x∥1,
where A∈ℜm×n(m≪n) is a linear operator, y∈ℜm is an observation, and μ is a nonnegative parameter. Equation (29) mainly appears in compressed sensing: an emerging methodology in digital signal processing and has attracted intensive research activities over the past few years. Compressed sensing is based on the fact that if original signal is sparse or approximately sparse in some orthogonal basis, then an exact restoration can be produced by solving (29).Recently,  Figueiredo et al. [14] proposed gradient projection method for sparse reconstruction (GPSR). The first key step of GPSR method is to express (29) as a quadratic program. For any x∈ℜn it can be formulated as x=u-v, u≥0, v≥0, where u∈ℜn,v∈ℜn, and ui=(xi)+,vi=(-xi)+ for i=1,2,…,n with (·)+=max{0,·}. We thus have ∥x∥1=enTu+enTv, where en=(1,1,…,1)T is the vector consisting of n ones. Hence (29) can be rewritten as the following quadratic program:
(30)minu,v12∥y-A(u-v)∥22+μenTu+μenTv,s.t.u≥0,v≥0.
Furthermore, from [14], (30) can be written in following form
(31)minu,v12zTBz+cTz,s.t.z≥0,
where
(32)z=(uv),b=ATy,c=μe2n+(-bb),B=(ATA-ATA-ATAATA).
It is obvious that B is a positive semidefinite matrix, hence, (30) is a convex QP problem. Figueiredo et al. [14] proposed a gradient projection method with BB step length for solving this problem.Xiao et al.  [7] indicated that the QP problem (30) is equivalent to the linear complementary problem: find z∈ℜ2n such that
(33)z≥0,Bz+c≥0,〈Bz+c,z〉=0.
It is obvious that z is a solution of (33) if and only if it is a solution of the following nonlinear systems of equation
(34)g(z)=min{z,Bz+c}=0.
The function g is vector valued, and the “min” is interpreted as componentwise minimum. Xiao et al. [7] proved that g is monotone. Hence, (34) can be solved effectively by the HSG-V algorithm.Firstly, we consider a typical CS scenario that goal is to reconstruct a length-n sparse signal from m observations. We measure the quality of restoration by means of squared error (MSE) to the original signal x-, that is,
(35)MSE=1n∥x--x*∥2,
where x* is the restored signal. We test a small size signal with n=212, m=210, and the original contains 27 randomly nonzero elements. A is the Gaussian matrix which is generated by command randn(m,n) in MATLAB. In this test, the measurement y is usually contaminated by noise, that is,(36)y=Ax-+ω,
where ω is the Gaussian noise distributed as N(0,0.0001). The parameters are taken as β=0.1, σ=0.01,  ϵ=10-10, r=1.2, M=2,  μ is forced in decrease as the measure of [14]. To get better quality estimated signals, the process is terminated when the relative change of the objective function is below 10-5, that is,
(37)∥fk-fk-1∥∥fk-1∥<10-5,
where fk denotes the function value at xk.Figures3 and 4 report the results of HSG-V for a signal sparse reconstruction from its limited measurement. Comparing the first and last plot in Figure 3, we can find that the original sparse signal is restored almost exactly from the limited measurement. From the right plot in Figure 4, we observe that all the blue dots are circled by the red circles, which shows that the original signal has been found almost exactly. All together, this simple experiment shows that HSG-V algorithms perform well, and it is an efficient method to denoise sparse signals.(a) Original signal with length 4096 and 128 nonzero elements. (b) The noisy measurement with length 1024. (c) Recovery signal by HSG-V with 232 iterations, 15.16 s CPU time in seconds, and 3.14e-06 error.
(a)
(b)
(c)(a) Original signal with 128 nonzero elements, (b) noisy measurement, (c) restored signal (red circles) versus original signal (blue dots) withMSE=6.72e-06, 12.66 CPU time in seconds, and 188 iterations.
(a)
(b)
(c)In the next experiment, we compare the performance of our algorithm with the SGCS algorithm for image deconvolution, in whichA is a partial DWT matrix whose m rows are chosen randomly from n×n DWT matrix. To measure the quality of restoration, we use the SNR (signal to noise ratio) defined as SNR=20log10(∥x̅∥/∥x-x̅∥). Figure 5 shows the original test images, and Figure 6 shows the restoration results by the SGCS and HSG-V algorithm, respectively. These results show that the HSG-V algorithm can restore blurred image quite well and obtain better quality reconstructed images in an efficient manner.Figure 5
The original images: cameraman/barbara/bridge.The blurred image (first column), the restored image by SGCS algorithm (second column), and HSG-V algorithm.
(a)
(b)
(c)


## 3.1. Test on Nonlinear Systems of Monotone Equations

We test the performance of our algorithms for solving some monotone equations (see details in the appendix). The termination condition is∥g(xk)∥≤10-6. The parameters are specified as follows. For MSG method, we set β=0.5,σ=0.01,ϵ=10-10,r=0.01. In Step 2, the parameter δ is chosen in the following way:
(28)δ={1if∥g(xk)∥>1,∥g(xk)∥-1if10-5≤∥g(xk)∥≤1,105if∥g(xk)∥<10-5.Firstly, we test the performance of the MSG method on the Problem1 with n=1000, the initial point x0=(1,1,…,1)T. Figure 1 displays the performance of MSG method for Problem 1 which indicates that prediction sequences {zk} are better than correction sequences {xk} at most time. Taking this into account, we relax the MSG method such that Step 4 in Algorithm 1 is replaced by the following: if modxk+1=xk-〈g(zk),xk-zk〉∥g(zk)∥2g(zk),eslsexk+1=zk,end.(a) Norm of sequence versus iteration for MSG algorithm. (b) MSG-V algorithm versus MSG and SG algorithm, where the iteration has been cut to 100 for the SG algorithm.
(a)
(b)In this case, we refer to this modification as “MSG-V” method. WhenM≡1, the above algorithm will reduce to Algorithm 1. The performance of those methods on the  Problem (1) is shown in Figure 1, from which we can see that the MSG-V method is preferable quite frequently to the SG method while it also outperforms the MSG method. Furthermore, motivated to accelerate the performance of MSG-V method, we present a hybrid spectral gradient (HSG-V) algorithm. The main idea of the HSG-V algorithm is to run MSG-V algorithm when yk-1i/sk-1i>0 for i=1,2,…,n; otherwise switch to spectral gradient projection (SG) method.And then we compare the performance of MSG method, MSG-V method, and HSG-V method with the spectral gradient projection (SG) method in [6] on test problems with different initial points. We set β=0.5, σ=0.01, r=0.01 in the spectral gradient projection (SG) method in [6], and M=10 for MSG-V method and HSG-V method.Numerical results are shown in Tables1, 2, 3, 4, 5, and 6 with the form NI/NF/T/BK, where we report the dimension of the problem (n), the initial points (Init), the number of iteration (NI), the number of function evaluations (NF), and the CPU time (Time) in seconds and the number of backtracking (BK). The symbol “F” denotes that the method fails for this test problem, or the number of the iterations is greater than 10000.Table 1
Numerical results for SG/MSG methods on Problem1.
Init (n)
SG
MSG
NI/NF/Time/BK
NI/NF/Time/BK
x
1 (100)
7935/56267/7.375/6
1480/9774/1.609/1
x
2 (100)
4365/25627/3.125/2
981/6223/0.906/1
x
3 (100)
3131/18028/2.11/7
1139/8240/1.266/1
x
4 (100)
2287/13025/1.453/4
294/1091/0.172/1
x
5 (100)
1685/9535/1.188/3
212/640/0.093/1
x
6 (100)
1788/10238/1.156/3
243/745/0.11/1
x
7 (100)
1608/9236/1.047/2
220/664/0.109/1
x
8 (100)
1629/9283/1.172/4
185/558/0.078/1
x
9 (100)
1478/8407/0.953/4
8/20/0.016/0
x
10 (100)
1611/9131/1.031/3
184/555/0.078/1
x
11 (100)
1475/8404/0.938/4
39/99/0.016/0
x
12 (100)
1226/6938/0.797/5
19/46/0.016/0
x
1 (200)
F
2846/20922/6.328/1
x
2 (200)
8506/50896/11.985/4
1535/11707/3.5/1
x
3 (200)
6193/37063/8.687/7
1826/15256/4.5/0
x
4 (200)
4563/27333/6.5/7
266/1055/0.312/1
x
5 (200)
3343/19760/5.078/4
376/1133/0.422/1
x
6 (200)
3620/21536/6.11/7
200/617/0.172/1
x
7 (200)
3249/19340/4.531/6
148/444/0.125/0
x
8 (200)
3253/19383/4.5/5
323/973/0.344/1
x
9 (200)
2974/17649/4.109/4
8/21/0.015/0
x
10 (200)
3256/19214/5.062/4
308/928/0.391/1
x
11 (200)
2995/17784/5.266/4
42/110/0.047/0
x
12 (200)
2483/14698/3.453/3
27/63/0.047/0
x
1 (300)
F
F
x
2 (300)
F
3374/29158/12.782/1
x
3 (300)
9334/57185/20.985/2
1293/10136/4.656/1
x
4 (300)
6734/41348/14.735/4
406/1601/0.687/1
x
5 (300)
5011/30857/11.265/7
235/706/0.282/1
x
6 (300)
5380/33167/11.875/6
300/919/0.546/1
x
7 (300)
4812/29977/10.657/6
187/559/0.235/0
x
8 (300)
4825/29770/10.656/4
158/466/0.187/0
x
9 (300)
4396/27551/10.062/3
8/21/0.016/0
x
10 (300)
4774/29731/10.969/3
203/610/0.266/1
x
11 (300)
4411/27366/9.859/8
52/144/0.062/0
x
12 (300)
3656/23021/8.36/6
32/75/0.031/0
x
1 (500)
F
F
x
2 (500)
F
4915/46911/37.906/1
x
3 (500)
F
1754/15152/12.375/1
x
4 (500)
F
489/1905/1.547/1
x
5 (500)
8360/51414/37.485/6
269/803/0.797/1
x
6 (500)
8996/56185/39.75/6
295/900/0.734/1
x
7 (500)
8128/50525/35.703/2
256/766/0.672/1
x
8 (500)
8089/50688/36.484/4
387/1163/1.156/0
x
9 (500)
7453/46083/33.75/2
8/22/0.016/0
x
10 (500)
8118/50185/35.985/4
403/1211/1.187/1
x
11 (500)
7525/46275/33.14/4
55/149/0.11/0
x
12 (500)
6235/38408/28.047/9
38/95/0.11/0
x
1 (1000)
F
F
x
2 (1000)
F
8998/93619/200.78/0
x
3 (1000)
F
2939/26376/55.86/0
x
4 (1000)
F
783/3016/6.438/0
x
5 (1000)
F
364/1085/2.75/0
x
6 (1000)
F
429/1309/3.266/0
x
7 (1000)
F
499/1500/3.687/1
x
8 (1000)
F
481/1444/3.969/0
x
9 (1000)
F
8/23/0.047/0
x
10 (1000)
F
346/1032/2.515/0
x
11 (1000)
F
74/201/0.391/0
x
12 (1000)
F
50/124/0.234/0Table 2
Numerical results for MSG-V/HSG-V methods on Problem1.
Init (n)
MSG-V
HSG-V
NI/NF/Time/BK
NI/NF/Time/BK
x
1 (100)
48/162/0.031/0
139/471/0.14/0
x
2 (100)
37/120/0.016/0
165/572/0.079/7
x
3 (100)
29/93/0.015/0
158/522/0.062/2
x
4 (100)
22/61/0.016/0
134/461/0.063/0
x
5 (100)
8/22/0.016/0
8/22/0.015/0
x
6 (100)
9/26/0.015/0
9/26/0.015/0
x
7 (100)
8/22/0.016/0
8/22/0.016/0
x
8 (100)
8/21/0.015/0
8/21/0.016/0
x
9 (100)
8/20/0.015/0
8/20/0.016/0
x
10 (100)
24/75/0.031/1
24/75/0.031/1
x
11 (100)
8/21/0.015/0
8/21/0.016/0
x
12 (100)
6/16/0.016/0
6/16/0.016/0
x
1 (200)
43/134/0.047/0
174/587/0.172/0
x
2 (200)
39/142/0.047/0
184/640/0.172/0
x
3 (200)
35/118/0.031/1
205/693/0.188/0
x
4 (200)
19/59/0.031/0
148/519/0.125/0
x
5 (200)
8/23/0.296/0
8/23/0.015/0
x
6 (200)
9/27/0.016/0
9/27/0.016/0
x
7 (200)
8/23/0.016/0
8/23/0.016/0
x
8 (200)
8/22/0.015/0
8/22/0.016/0
x
9 (200)
8/21/0.016/0
8/21/0.015/0
x
10 (200)
25/79/0.046/1
25/79/0.031/1
x
11 (200)
8/22/0.016/0
8/22/0.016/0
x
12 (200)
6/17/0.015/0
6/17/0.016/0
x
1 (300)
50/200/0.094/0
246/865/0.375/4
x
2 (300)
56/196/0.093/1
265/977/0.375/8
x
3 (300)
33/119/0.047/0
345/1253/0.515/7
x
4 (300)
28/90/0.031/0
244/825/0.329/0
x
5 (300)
8/23/0.016/0
8/23/0.015/0
x
6 (300)
9/27/0.015/0
9/27/0.016/0
x
7 (300)
8/23/0.016/0
8/23/0.015/0
x
8 (300)
8/22/0.016/0
8/22/0.016/0
x
9 (300)
8/21/0.016/0
8/21/0.016/0
x
10 (300)
26/82/0.031/1
26/82/0.031/1
x
11 (300)
8/23/0.016/0
8/23/0.016/0
x
12 (300)
6/18/0.015/0
6/18/0.015/0
x
1 (500)
51/218/0.188/0
290/1054/0.765/8
x
2 (500)
41/132/0.125/0
330/1159/0.953/0
x
3 (500)
47/164/0.14/1
383/1394/0.969/0
x
4 (500)
28/91/0.125/0
246/864/0.609/0
x
5 (500)
9/26/0.047/0
9/26/0.032/0
x
6 (500)
9/28/0.031/0
9/28/0.015/0
x
7 (500)
9/26/0.047/0
9/26/0.032/0
x
8 (500)
8/23/0.032/0
8/23/0.015/0
x
9 (500)
8/22/0.031/0
8/22/0.016/0
x
10 (500)
27/86/0.062/1
27/86/0.062/1
x
11 (500)
8/23/0.016/0
8/23/0.032/0
x
12 (500)
6/19/0.016/0
6/19/0.015/0
x
1 (1000)
49/205/0.547/0
437/1656/3.094/2
x
2 (1000)
41/138/0.344/0
506/1824/3.406/0
x
3 (1000)
49/181/0.437/1
607/2137/4.094/2
x
4 (1000)
37/121/0.282/1
426/1582/3/0
x
5 (1000)
9/27/0.062/0
9/27/0.062/0
x
6 (1000)
9/29/0.063/0
86/308/0.579/6
x
7 (1000)
9/27/0.046/0
9/27/0.046/0
x
8 (1000)
8/24/0.063/0
8/24/0.047/0
x
9 (1000)
8/23/0.047/0
12/44/0.078/2
x
10 (1000)
29/93/0.172/1
29/93/0.188/1
x
11 (1000)
8/24/0.047/0
8/24/0.078/0
x
12 (1000)
6/20/0.031/0
6/20/0.078/0Table 3
Numerical results for SG/MSG methods on Problem2.
Init (n)
SG
MSG
NI/NF/Time/BK
NI/NF/Time/BK
x
1 (100)
F
349/712/0.094/0
x
2 (100)
F
352/711/0.094/0
x
3 (100)
F
351/711/0.094/0
x
4 (100)
F
353/717/0.109/0
x
5 (100)
F
346/696/0.094/0
x
6 (100)
F
347/698/0.078/0
x
7 (100)
F
345/694/0.109/0
x
8 (100)
F
320/644/0.078/0
x
9 (100)
359/719/0.031/0
359/719/0.047/0
x
10 (100)
22/67/0.015/1
22/67/0.015/1
x
11 (100)
434/869/0.047/0
434/869/0.063/0
x
12 (100)
424/849/0.031/0
424/849/0.047/0
x
1 (200)
F
437/888/0.218/0
x
2 (200)
F
439/885/0.219/0
x
3 (200)
F
438/885/0.219/0
x
4 (200)
F
440/891/0.219/0
x
5 (200)
F
433/870/0.343/0
x
6 (200)
F
434/872/0.203/0
x
7 (200)
F
432/868/0.219/0
x
8 (200)
F
358/720/0.172/0
x
9 (200)
372/745/0.047/0
371/743/0.063/0
x
10 (200)
22/66/0.015/0
23/70/0.015/1
x
11 (200)
544/1089/0.063/0
544/1089/0.094/0
x
12 (200)
534/1069/0.047/0
534/1069/0.109/0
x
1 (300)
F
498/1010/0.375/0
x
2 (300)
F
500/1007/0.375/0
x
3 (300)
F
500/1009/0.375/0
x
4 (300)
F
501/1013/0.36/0
x
5 (300)
F
494/992/0.375/0
x
6 (300)
F
495/994/0.375/0
x
7 (300)
F
494/992/0.359/0
x
8 (300)
F
368/740/0.266/0
x
9 (300)
373/747/0.047/0
373/747/0.093/0
x
10 (300)
22/66/0.015/0
23/70/0.016/1
x
11 (300)
621/1243/0.078/0
621/1243/0.157/0
x
12 (300)
611/1223/0.078/0
611/1223/0.25/0
x
1 (500)
F
588/1190/0.781/0
x
2 (500)
F
590/1187/0.781/0
x
3 (500)
F
589/1187/0.781/0
x
4 (500)
F
591/1193/0.797/0
x
5 (500)
F
584/1172/0.782/0
x
6 (500)
F
585/1174/0.906/0
x
7 (500)
F
583/1170/0.797/0
x
8 (500)
F
372/748/0.468/0
x
9 (500)
373/747/0.078/0
373/747/0.125/0
x
10 (500)
22/66/0.015/0
23/70/0.016/1
x
11 (500)
734/1469/0.141/0
734/1469/0.234/0
x
12 (500)
724/1449/0.14/0
724/1449/0.25/0
x
1 (1000)
F
736/1486/2.563/0
x
2 (1000)
F
739/1485/2.406/0
x
3 (1000)
F
738/1485/2.578/0
x
4 (1000)
F
740/1491/2.407/0
x
5 (1000)
F
733/1470/2.562/0
x
6 (1000)
F
734/1472/2.531/0
x
7 (1000)
F
732/1468/2.407/0
x
8 (1000)
F
372/748/1.125/0
x
9 (1000)
373/747/0.125/0
373/747/0.343/0
x
10 (1000)
24/73/0.016/1
24/73/0.032/1
x
11 (1000)
921/1843/0.281/0
921/1843/0.562/0
x
12 (1000)
912/1825/0.266/0
912/1825/0.547/0Table 4
Numerical results for MSG-V/HSG-V methods on Problem2.
Init (n)
MSG-V
HSG-V
NI/NF/Time/BK
NI/NF/Time/BK
x
1 (100)
27/82/0.015/1
27/82/0.016/1
x
2 (100)
435/872/0.047/0
435/872/0.094/0
x
3 (100)
416/838/0.047/0
416/838/0.062/0
x
4 (100)
434/872/0.047/0
434/872/0.047/0
x
5 (100)
424/850/0.047/0
424/850/0.047/0
x
6 (100)
347/697/0.047/0
347/697/0.047/0
x
7 (100)
346/695/0.047/0
346/695/0.032/0
x
8 (100)
318/640/0.078/0
318/640/0.062/0
x
9 (100)
355/711/0.031/0
355/711/0.031/0
x
10 (100)
22/67/0.016/1
22/67/0.016/1
x
11 (100)
434/869/0.063/0
434/869/0.062/0
x
12 (100)
424/849/0.046/0
424/849/0.047/0
x
1 (200)
27/82/0.015/1
27/82/0.016/1
x
2 (200)
545/1092/0.094/0
545/1092/0.078/0
x
3 (200)
525/1056/0.094/0
525/1056/0.078/0
x
4 (200)
544/1092/0.094/0
544/1092/0.078/0
x
5 (200)
533/1068/0.093/0
533/1068/0.078/0
x
6 (200)
435/873/0.063/0
435/873/0.078/0
x
7 (200)
433/869/0.078/0
433/869/0.063/0
x
8 (200)
355/714/0.172/0
356/716/0.078/0
x
9 (200)
367/735/0.062/0
367/735/0.047/0
x
10 (200)
23/70/0.015/1
23/70/0.016/1
x
11 (200)
544/1089/0.094/0
544/1089/0.078/0
x
12 (200)
534/1069/0.094/0
534/1069/0.078/0
x
1 (300)
28/85/0.016/1
28/85/0.016/1
x
2 (300)
622/1246/0.14/0
622/1246/0.11/0
x
3 (300)
602/1210/0.156/0
602/1210/0.125/0
x
4 (300)
621/1246/0.25/0
621/1246/0.109/0
x
5 (300)
610/1222/0.125/0
610/1222/0.125/0
x
6 (300)
496/995/0.11/0
496/995/0.094/0
x
7 (300)
494/991/0.125/0
494/991/0.094/0
x
8 (300)
365/734/0.25/0
365/734/0.109/0
x
9 (300)
368/737/0.094/0
368/737/0.063/0
x
10 (300)
23/70/0.031/1
23/70/0.015/1
x
11 (300)
621/1243/0.141/0
621/1243/0.11/0
x
12 (300)
611/1223/0.125/0
611/1223/0.125/0
x
1 (500)
28/85/0.015/1
28/85/0.015/1
x
2 (500)
735/1472/0.25/0
735/1472/0.203/0
x
3 (500)
715/1436/0.219/0
715/1436/0.203/0
x
4 (500)
734/1472/0.25/0
734/1472/0.188/0
x
5 (500)
723/1448/0.219/0
723/1448/0.187/0
x
6 (500)
586/1175/0.187/0
586/1175/0.156/0
x
7 (500)
584/1171/0.204/0
584/1171/0.141/0
x
8 (500)
369/742/0.453/0
369/742/0.156/0
x
9 (500)
368/737/0.125/0
368/737/0.094/0
x
10 (500)
23/70/0.015/1
23/70/0.015/1
x
11 (500)
734/1469/0.219/0
734/1469/0.203/0
x
12 (500)
724/1449/0.234/0
724/1449/0.235/0
x
1 (1000)
28/85/0.016/1
28/85/0.047/1
x
2 (1000)
923/1848/0.531/0
923/1848/0.485/0
x
3 (1000)
902/1810/0.641/0
902/1810/0.437/0
x
4 (1000)
922/1848/0.516/0
922/1848/0.453/0
x
5 (1000)
911/1824/0.531/0
911/1824/0.453/0
x
6 (1000)
737/1477/0.406/0
737/1477/0.344/0
x
7 (1000)
733/1469/0.422/0
733/1469/0.344/0
x
8 (1000)
369/742/1.125/0
369/742/0.297/0
x
9 (1000)
368/737/0.219/0
368/737/0.172/0
x
10 (1000)
24/73/0.015/1
24/73/0.015/1
x
11 (1000)
921/1843/0.625/0
921/1843/0.438/0
x
12 (1000)
912/1825/0.563/0
912/1825/0.453/0Table 5
Numerical results for SG/MSG methods on Problem3.
Init (n)
SG
MSG
NI/NF/Time/BK
NI/NF/Time/BK
x
1 (100)
161/753/0.094/2
246/1062/0.296/3
x
2 (100)
103/424/0.062/3
185/794/0.219/2
x
3 (100)
118/517/0.063/2
204/935/0.266/5
x
4 (100)
63/224/0.031/1
194/894/0.25/2
x
5 (100)
63/234/0.031/2
149/662/0.187/3
x
6 (100)
81/307/0.047/2
191/831/0.235/1
x
7 (100)
64/237/0.031/2
168/738/0.203/1
x
8 (100)
53/194/0.032/2
94/378/0.109/1
x
9 (100)
53/192/0.015/2
178/808/0.219/3
x
10 (100)
76/288/0.047/2
229/1008/0.281/1
x
11 (100)
73/273/0.031/2
203/924/0.25/4
x
12 (100)
60/225/0.016/3
195/888/0.266/1
x
1 (200)
216/1203/0.468/2
251/1129/0.515/2
x
2 (200)
147/728/0.282/2
168/702/0.407/3
x
3 (200)
157/759/0.312/2
180/821/0.422/1
x
4 (200)
58/206/0.094/3
214/956/0.453/1
x
5 (200)
64/238/0.094/1
174/793/0.359/2
x
6 (200)
78/294/0.125/2
194/882/0.422/2
x
7 (200)
44/156/0.062/2
170/757/0.359/1
x
8 (200)
48/173/0.078/1
93/368/0.172/1
x
9 (200)
54/192/0.078/2
191/890/0.391/2
x
10 (200)
84/314/0.125/3
152/627/0.282/1
x
11 (200)
61/222/0.094/2
193/903/0.422/2
x
12 (200)
63/236/0.093/3
121/531/0.25/2
x
1 (300)
541/5455/20.282/3
247/1066/4.187/5
x
2 (300)
142/724/2.734/2
135/512/2.063/1
x
3 (300)
195/1084/4.031/2
197/892/3.5/1
x
4 (300)
55/196/0.734/2
193/868/3.328/2
x
5 (300)
68/254/0.953/2
154/693/2.703/4
x
6 (300)
77/295/1.11/2
241/1168/4.484/2
x
7 (300)
76/281/1.094/2
186/851/3.313/5
x
8 (300)
57/207/0.765/2
127/528/2/1
x
9 (300)
59/210/0.797/1
190/939/3.578/1
x
10 (300)
91/342/1.266/3
142/664/2.563/1
x
11 (300)
79/288/1.109/3
168/767/2.906/1
x
12 (300)
72/266/0.984/1
114/448/1.75/1
x
1 (500)
488/4021/42.907/1
212/927/9.985/1
x
2 (500)
240/1440/15.343/3
166/712/7.64/4
x
3 (500)
254/1544/16.485/1
228/1050/11.313/2
x
4 (500)
59/210/2.266/3
273/1564/16.843/3
x
5 (500)
70/261/2.75/2
189/905/9.781/2
x
6 (500)
82/313/3.328/2
190/866/9.266/1
x
7 (500)
76/284/3.078/3
149/642/6.984/1
x
8 (500)
59/215/2.282/2
97/381/4.141/1
x
9 (500)
51/185/1.985/2
439/2832/30.391/3
x
10 (500)
84/319/3.421/2
66/238/2.562/1
x
11 (500)
77/280/2.969/2
74/266/2.891/1
x
12 (500)
67/250/2.719/3
57/189/2.078/1
x
1 (1000)
2780/36160/1510.7/2
199/853/35.969/3
x
2 (1000)
331/2242/94.734/2
160/656/27.656/1
x
3 (1000)
352/2532/106.25/1
197/891/37.359/2
x
4 (1000)
71/260/10.891/1
182/794/33.985/2
x
5 (1000)
71/268/11.234/2
190/891/37.546/3
x
6 (1000)
84/319/13.422/3
160/698/29.188/4
x
7 (1000)
73/271/11.391/2
157/663/27.547/1
x
8 (1000)
50/182/7.578/2
112/446/18.641/4
x
9 (1000)
49/173/7.328/2
232/1162/48.656/1
x
10 (1000)
85/318/13.375/2
56/172/7.391/1
x
11 (1000)
81/297/12.485/3
61/185/7.781/1
x
12 (1000)
69/255/10.781/1
49/154/6.578/1Table 6
Numerical results for MSG-V/HSG-V methods on Problem3.
Init (n)
MSG-V
HSG-V
NI/NF/Time/BK
NI/NF/Time/BK
x
1 (100)
92/377/0.078/1
55/172/0.047/6
x
2 (100)
93/374/0.079/1
59/177/0.031/0
x
3 (100)
86/360/0.078/1
40/120/0.031/0
x
4 (100)
83/363/0.062/1
40/111/0.032/1
x
5 (100)
45/173/0.047/1
20/56/0.015/0
x
6 (100)
57/204/0.047/2
42/121/0.016/2
x
7 (100)
53/202/0.031/1
30/87/0.031/0
x
8 (100)
47/181/0.047/2
22/61/0.016/0
x
9 (100)
49/194/0.047/1
33/100/0.015/1
x
10 (100)
48/165/0.031/1
30/97/0.032/3
x
11 (100)
49/181/0.031/1
26/75/0.015/0
x
12 (100)
37/125/0.032/0
29/93/0.016/0
x
1 (200)
88/335/0.172/1
53/173/0.078/1
x
2 (200)
83/330/0.14/1
50/142/0.078/0
x
3 (200)
76/290/0.141/1
42/126/0.047/2
x
4 (200)
69/266/0.125/1
35/101/0.063/3
x
5 (200)
48/190/0.094/1
25/72/0.031/3
x
6 (200)
69/294/0.156/2
34/99/0.047/0
x
7 (200)
55/215/0.109/5
30/81/0.047/0
x
8 (200)
51/217/0.11/1
22/61/0.031/0
x
9 (200)
46/153/0.078/1
24/64/0.031/0
x
10 (200)
42/129/0.078/1
33/91/0.031/0
x
11 (200)
49/180/0.094/0
30/92/0.047/1
x
12 (200)
37/125/0.062/2
30/85/0.047/0
x
1 (300)
89/322/1.266/1
53/168/0.625/0
x
2 (300)
91/348/1.282/1
55/162/0.609/1
x
3 (300)
72/278/1.046/1
37/109/0.422/0
x
4 (300)
78/339/1.297/1
28/81/0.297/1
x
5 (300)
45/178/0.735/2
20/55/0.281/0
x
6 (300)
63/248/0.937/3
38/113/0.453/2
x
7 (300)
53/208/0.797/1
33/91/0.344/0
x
8 (300)
63/295/1.109/1
22/61/0.234/0
x
9 (300)
45/177/0.672/1
27/71/0.266/0
x
10 (300)
45/148/0.641/1
40/108/0.406/0
x
11 (300)
43/144/0.531/2
32/89/0.344/1
x
12 (300)
36/129/0.5/0
28/83/0.312/2
x
1 (500)
85/289/3.125/1
50/158/1.672/0
x
2 (500)
78/245/2.625/0
56/157/1.75/2
x
3 (500)
74/289/3.156/2
40/118/1.235/1
x
4 (500)
62/223/2.375/1
47/131/1.437/1
x
5 (500)
49/194/2.11/1
25/74/0.813/3
x
6 (500)
55/181/1.922/2
40/116/1.218/0
x
7 (500)
49/163/1.797/1
26/74/0.781/0
x
8 (500)
53/219/2.328/1
22/61/0.657/0
x
9 (500)
49/184/2/0
25/69/0.781/2
x
10 (500)
41/158/1.656/2
35/99/1.062/6
x
11 (500)
48/173/1.922/1
31/83/0.891/0
x
12 (500)
35/126/1.359/2
27/76/0.812/0
x
1 (1000)
97/376/15.688/3
50/165/6.922/3
x
2 (1000)
78/263/11.015/1
52/151/6.235/2
x
3 (1000)
80/303/12.766/1
44/128/5.343/1
x
4 (1000)
73/291/12.219/0
36/101/4.235/0
x
5 (1000)
43/165/6.968/1
22/66/2.75/2
x
6 (1000)
59/213/9.094/4
44/120/5.016/0
x
7 (1000)
55/201/8.438/1
27/78/3.281/3
x
8 (1000)
57/250/10.5/1
22/60/2.547/0
x
9 (1000)
46/166/7/0
29/80/3.266/4
x
10 (1000)
39/126/5.234/0
31/87/3.64/0
x
11 (1000)
47/165/6.969/1
35/96/4.032/3
x
12 (1000)
36/114/4.797/2
34/91/3.812/0As we can see from Tables1–6 that the HSG-V algorithm is preferable quite frequently to the SG method  and  also outperforms the MSG algorithm and MSG-V algorithm, since it can solve about 80% and 70% of the problems with the best time and the smallest number of function evaluations, respectively. We also find that the SG algorithm seems more sensitive to the initial points.Figure2 shows the performance of these algorithms relative to the number of function evaluations and CPU time, respectively, which were evaluated using the profiles of Dolan and Moré [13]. That is, for each algorithm, we plot the fraction P of problems for which the method is within a factor t of the smallest number of function evaluations/CPU time. Clearly, the left side of the figure gives the percentage of the test problems for which a method is the best one according to the number of function evaluations or CPU time, respectively. As we can see from Figure 2, “HSG-V” algorithm has the best performance.(a) Performance profiles for the number of function evaluations. (b) Performance profiles for the CPU time.
(a)
(b)


## 3.2. Test onℓ1-Norm Regularization Problem in Compressed Sensing

There has been considerable interest in solving theℓ1-norm regularized least-square problem
(29)minx∈ℜnf(x)≡12∥Ax-y∥22+μ∥x∥1,
where A∈ℜm×n(m≪n) is a linear operator, y∈ℜm is an observation, and μ is a nonnegative parameter. Equation (29) mainly appears in compressed sensing: an emerging methodology in digital signal processing and has attracted intensive research activities over the past few years. Compressed sensing is based on the fact that if original signal is sparse or approximately sparse in some orthogonal basis, then an exact restoration can be produced by solving (29).Recently,  Figueiredo et al. [14] proposed gradient projection method for sparse reconstruction (GPSR). The first key step of GPSR method is to express (29) as a quadratic program. For any x∈ℜn it can be formulated as x=u-v, u≥0, v≥0, where u∈ℜn,v∈ℜn, and ui=(xi)+,vi=(-xi)+ for i=1,2,…,n with (·)+=max{0,·}. We thus have ∥x∥1=enTu+enTv, where en=(1,1,…,1)T is the vector consisting of n ones. Hence (29) can be rewritten as the following quadratic program:
(30)minu,v12∥y-A(u-v)∥22+μenTu+μenTv,s.t.u≥0,v≥0.
Furthermore, from [14], (30) can be written in following form
(31)minu,v12zTBz+cTz,s.t.z≥0,
where
(32)z=(uv),b=ATy,c=μe2n+(-bb),B=(ATA-ATA-ATAATA).
It is obvious that B is a positive semidefinite matrix, hence, (30) is a convex QP problem. Figueiredo et al. [14] proposed a gradient projection method with BB step length for solving this problem.Xiao et al.  [7] indicated that the QP problem (30) is equivalent to the linear complementary problem: find z∈ℜ2n such that
(33)z≥0,Bz+c≥0,〈Bz+c,z〉=0.
It is obvious that z is a solution of (33) if and only if it is a solution of the following nonlinear systems of equation
(34)g(z)=min{z,Bz+c}=0.
The function g is vector valued, and the “min” is interpreted as componentwise minimum. Xiao et al. [7] proved that g is monotone. Hence, (34) can be solved effectively by the HSG-V algorithm.Firstly, we consider a typical CS scenario that goal is to reconstruct a length-n sparse signal from m observations. We measure the quality of restoration by means of squared error (MSE) to the original signal x-, that is,
(35)MSE=1n∥x--x*∥2,
where x* is the restored signal. We test a small size signal with n=212, m=210, and the original contains 27 randomly nonzero elements. A is the Gaussian matrix which is generated by command randn(m,n) in MATLAB. In this test, the measurement y is usually contaminated by noise, that is,(36)y=Ax-+ω,
where ω is the Gaussian noise distributed as N(0,0.0001). The parameters are taken as β=0.1, σ=0.01,  ϵ=10-10, r=1.2, M=2,  μ is forced in decrease as the measure of [14]. To get better quality estimated signals, the process is terminated when the relative change of the objective function is below 10-5, that is,
(37)∥fk-fk-1∥∥fk-1∥<10-5,
where fk denotes the function value at xk.Figures3 and 4 report the results of HSG-V for a signal sparse reconstruction from its limited measurement. Comparing the first and last plot in Figure 3, we can find that the original sparse signal is restored almost exactly from the limited measurement. From the right plot in Figure 4, we observe that all the blue dots are circled by the red circles, which shows that the original signal has been found almost exactly. All together, this simple experiment shows that HSG-V algorithms perform well, and it is an efficient method to denoise sparse signals.(a) Original signal with length 4096 and 128 nonzero elements. (b) The noisy measurement with length 1024. (c) Recovery signal by HSG-V with 232 iterations, 15.16 s CPU time in seconds, and 3.14e-06 error.
(a)
(b)
(c)(a) Original signal with 128 nonzero elements, (b) noisy measurement, (c) restored signal (red circles) versus original signal (blue dots) withMSE=6.72e-06, 12.66 CPU time in seconds, and 188 iterations.
(a)
(b)
(c)In the next experiment, we compare the performance of our algorithm with the SGCS algorithm for image deconvolution, in whichA is a partial DWT matrix whose m rows are chosen randomly from n×n DWT matrix. To measure the quality of restoration, we use the SNR (signal to noise ratio) defined as SNR=20log10(∥x̅∥/∥x-x̅∥). Figure 5 shows the original test images, and Figure 6 shows the restoration results by the SGCS and HSG-V algorithm, respectively. These results show that the HSG-V algorithm can restore blurred image quite well and obtain better quality reconstructed images in an efficient manner.Figure 5
The original images: cameraman/barbara/bridge.The blurred image (first column), the restored image by SGCS algorithm (second column), and HSG-V algorithm.
(a)
(b)
(c)


## 4. Conclusion

In this paper, we develop an adaptive prediction-correction method for solving nonlinear monotone equations. Under some assumptions, we establish its global convergence. Base on the prediction-correction method, an efficient hybrid spectral gradient (HSG-V) algorithm is proposed, which is composite of MSG-V, algorithm and SG algorithm. Numerical results show that the HSG-V algorithm is preferable and outperforms the MSG, MSG-V and SG algorithm. Moreover, HSG-V algorithm is applied to solveℓ1-norm regularized problems arising from sparse signal reconstruction. Numerical experiments show that HSG-V algorithm works well, and it provides an efficient approach for compressed sensing and image deconvolution.



---

*Source: 619123-2013-05-08.xml*