# A Parallel Splitting Augmented Lagrangian Method for Two-Block Separable Convex Programming with Application in Image Processing

Authors: Jing Liu; Yongrui Duan; Tonghui Wang
Journal: Mathematical Problems in Engineering
 (2020)

---

## Abstract

The augmented Lagrangian method (ALM) is one of the most successful first-order methods for convex programming with linear equality constraints. To solve the two-block separable convex minimization problem, we always use the parallel splitting ALM method. In this paper, we will show that no matter how small the step size and the penalty parameter are, the convergence of the parallel splitting ALM is not guaranteed. We propose a new convergent parallel splitting ALM (PSALM), which is the regularizing ALM’s minimization subproblem by some simple proximal terms. In application this new PSALM is used to solve video background extraction problems and our numerical results indicate that this new PSALM is efficient.


---

## Body

## 1. Introduction

Many problems arising from machine learning, such as compressive sensing [1, 2], the video background extraction problem [3–5], batch images alignment [6, 7], and transform invariant low-rank textures [8, 9] can be formulated as separable convex programming with linear constraints. In this paper, we consider the following two-block separable convex programming:(1)minθ1x1+θ2x2A1x1+A2x2=b,x1∈X1,x2∈X2,where i=1,2, Ai∈ℜℓ×ni, the ℓ×ni matrix on ℜ; b∈ℜℓ, the ℓ-dimensional vector on ℜ; Xi is the subset of ℜni. Here, θi:Xi⟼ℜi=1,2 are the proper lower semicontinuous convex functions, i.e.,(2)liminfx⟶x˜θix=θix˜,for allx˜∈domθi≠∅,θiλx+1−λy≤λθix+1−λθiy,for allx,y∈Xi,λ∈0,1.The solution set of problem (1), denoted by X∗, is assumed to be nonempty. Note that theoretical results to problem (1) can easily be extended to matrix variables.Letβ>0 be a penalty parameter, and the augmented Lagrangian functions of problem (1) can be written as(3)ℒβx1,x2,λ=θ1x2+θ2x2−λ⊤A1x1+A2x2−b+β2A1x1+A2x2−b2,where λ∈ℜℓ is the Lagrangian multiplier. It is well-known that the augmented Lagrangian method (ALM) [10] is one of the most successful first-order methods for convex programming with linear constraints. Applying it to problem (1), we can obtain the following procedure:(4)x1k+1,x2k+1=argminℒβx1,x2,λkx1∈X1,x2∈X2,λk+1=λk−αβA1x1k+1+A2x2k+1−b,where α∈0,2 is the step size. It has been proved that the sequence generated by the iterative scheme (4) is Fejér monotone and has the global convergence. In many practical problems, the proximal mapping proxνθi of θi, defined as(5)proxνθixi≔argminy∈ℛniθixi+12νy−xi2,has closed-form expression. For example, consider the video background extraction problem given by(6)minL,SL∗+τS1,subject  toL+S=D,where(7)L∗=∑i=1minm,nσiL,S1=∑i=1m∑j=1nsij.σ
i
L are the singular values of the m×n matrix L, U∑V⊤ is the singular value decomposition of L, and sij are elements of the m×n matrix S. Then, by [11], the proximal mapping (5) is rewritten as(8)proxν⋅∗L=UdiagScΣV⊤.Similarly, by [12], the proximal mapping (5) is given as(9)proxν⋅1S=SνS,where SνE is defined by(10)SνEij≔signEij⋅maxEij−ν,0,1≤i≤m,1≤j≤n,and sign⋅ is the sign function. However, the proximal mapping of L∗+τS1 does not admit closed-form expression so that the iterative scheme (4) for problem (5) has to resort some inner solver to compute its minimization problem in each iteration, which inevitably creates a chain of problems, such as an efficient solver to solve the minimization problem and stopping criterion to ensure the global convergence of inexact version of the iterative scheme (5). Therefore, we should not ignore the separable structure of the objective function of problem (1). That is, we’d better split the minimization subproblem in (5) into some smaller scale subproblems to fully utilize the individual property of θi.The alternating direction method of multipliers (ADMM) can decompose a complicated problem into some small-scale subproblems and solve these subproblems in a sequential manner or a parallel manner. Focusing on the way of splitting the augmented Lagrangian function in the spirit of the well-known alternating direction method (ADM), Tao and Yuan [4] have proposed a variant of the alternating splitting augmented Lagrangian method (ASALM) with convergent property, which can solve three-block separable convex programming. He et al. [13] propose a splitting method for solving a separable convex minimization problem with linear constraints, where the objective function is expressed as the sum of m individual functions without coupled variables. Aybat and Iyenga [14] have designed a variant of ADMM with increasing penalty for stable principal component pursuit (ADMIP) to solve the SPCP problem. Its preliminary computational tests show that ADMIP works very well in practice and outperforms ASALM which is a state-of-the-art ADMM algorithm for the SPCP problem with a constant penalty parameter.In this paper, following the abovementioned procedure, we split the minimization problem of ALM in the Jacobian manner and get the following iterative scheme:(11)x1k+1=argminℒβx1,x2k,λkx1∈X1,x2k+1=argminℒβx1k,x2,λkx2∈X2,λk+1=λk−αβA1x1k+1+A2x2k+1−b.The iterative scheme (11) takes advantages of the separable structure and parallel architectures. Unfortunately, it suffers from the weakness that its convergence cannot be guaranteed under the convex assumption of θi and X∗≠∅. To verify this, we shall apply the iterative scheme (11) to solve problem (1) given in Section 2 and show that the generated sequence diverges even β⟶0+. So, in Section 2, we propose a new parallel splitting ALM for problem (1), which is not only convergent but also keeps the good properties of the original ALM. Our numerical results in Section 3 indicate that the new PSALM is efficient.The remainder of this paper is organized as follows. In Section2, an example is given showing that the iterative scheme (11) maybe diverge, and a new parallel splitting ALM for problem (1) is proposed, which has the global convergence in both ergodic and nonergodic senses. For illustration of our main results, two numerical examples are given in Section 3 and a brief conclusion is drawn in Section 4.


## 2. Algorithm and Convergence Results

In this section, we will show that the iterative scheme (11) with any small positive α and β can be diverge so that a new parallel splitting ALM for problem (1) is proposed and the corresponding convergence results are established.In what follows,ℜn will stand for the n-dimensional Euclidean space, and set(12)x=x1,x2,w=x1,x2,λ,θx=θ1x1+θ2x2,A=A1,A2,X=X1×X2,W=X×ℜl.By the characterization of optimality condition for convex optimization, problem (1) can be readily characterized as the following mixed variational inequalities denoted by MVI W,F,θ:(13)θx−θx∗+w−w∗⊤Fw∗≥0,∀w∈W,where(14)Fw=−A1⊤λ−A2⊤λAx−b.BecauseFw is a linear mapping with the skew-symmetric coefficient matrix, it satisfies the following property:(15)w′−w⊤Fw′=w′−w⊤Fw,∀w′,w∈W.The solution set of MVIW,F,θ is denoted by W∗, which is nonempty under the assumption X∗≠∅.Based on the prototype algorithm proposed by He and Yuan in [15], we can introduce the following prototype algorithm to solve MVI W,F,θ:A prototype algorithm for MVIW,F,θ is denoted by ProAlo[Prediction] For givenwk, find w^k∈W and Q satisfying(16)θx−θx^k+w−w^k⊤Fw^k≥w−w^k⊤Qwk−w^k,∀w∈W,where the matrix Q has the property Q+Q⊤ which is positive definite[Correction] Determine a nonsingular matrixM, a scalar α>0, and generate the new iterate wk+1 via(17)wk+1=wk−αMwk−w^k.Similar to [15], we have the following convergence condition, which ensures that the ProAlo is globally convergent and has worst-case O1/t convergence rate in ergodic and nonergodic senses.Convergence ConditionThe matricesQ+Q⊤,H≔QM−1,Gα≔Q+Q⊤−αM⊤HM are positive definite.Now we give an example to show that the iterative scheme (11) maybe diverge for problem (1).Example 1.
Consider the linear equation [16](18)x1+x2=0.
Obviously, the linear equation (18) is a special case of problem (1) with the specifications: θ1=θ2=0,A1=A2=1,b=0,andX1=X2=ℜ. The augmented Lagrangian function of problem (18) is given by(19)ℒβx1,x2,λ=−λ⊤x1+x2+β2x1+x22.
Then, applying the iterative scheme (11) to solve problem (18) gives the following procedure:(20)x1k+1x2k+1λk+1=Px1kx2kλk,where(21)P=0−11β−101βαβαβ1−2α.
Three eigenvalues of the matrixP are(22)λ1=1,λ2=−α+α2+1,λ3=−α−α2+1.
For anyα,β>0, we have ρP=α+α2+1>1, let ρP is the spectral radius of P. Hence, the iterative scheme (20) with α,β>0 is divergent, which also indicates that the iterative scheme (11) diverge for problem (1) under the traditional assumption. In the following, we shall design a new parallel splitting ALM for problem (1), which maximally inherits the structure of the iterative scheme (11).Algorithm 1.
new PSALM
Step 1. Given an initial pointw0=x10,x20,λ0∈W; let parameters ν>0,α∈0,2ν/1+ν, β>0, and the tolerance ε>0. Set k=0.
Step 2. Compute the new iteratewk+1=x1k+1,x2k+1,λk+1 via
(23)
x
1
k
+
1
=
arg min
ℒ
β
x
1
,
x
2
k
,
λ
k
+
ν
β
2
A
1
x
1
−
A
1
x
1
k
2
x
1
∈
X
1
,
x
2
k
+
1
=
arg min
ℒ
β
x
1
k
,
x
2
,
λ
k
+
ν
β
2
A
2
x
2
−
A
2
x
2
k
2
x
2
∈
X
2
,
λ
k
+
1
=
λ
k
−
α
β
A
1
x
1
k
+
1
+
A
2
x
2
k
+
1
−
b
.
Step 3. IfmaxA1x1k−A1x1k+1,A2x2k−A2x2k+1,λk−λk+1≤ε, then stop; otherwise, replace k+1 by k, and go to Step 2.Remark 1.
The new PSALM iterative scheme (23) not only preserves the main advantage of the ALM iterative scheme (11) in treating the objective functions θ1 and θ2 individually, but also numerically accelerates (11) with some values of the step size α, e.g., α∈1,2, which can be achieved when ν>1.
In the following, we further make the following assumption about problem (1).Assumption 1.
The matricesA1andA2 in problem (1) are both full column ranks.
To establish the convergence results of new PSALM, we first cast it to a special case of the ProAlo. To accomplish this, let us define an auxiliary sequencew^k=x^1k,x^2k,λ^k as follows:(24)x^ik=xik+1,i=1,2,λ^k=λk−βA1x1k+A2x2k−b.
This together with the updated formula ofλ in (23) gives(25)λk+1=λk−α−βA1x1k−x^1k−βA2x2k−x^2k+λk−λ^k.
Thus,(26)wk+1=wk−αMwk−w^k,where the matrix M is defined as(27)M=In1α000In2α0−βA1−βA2Il.Lemma 1.
Letwk be the sequence generated by the new PSALM and w^k be defined as in (24), and it holds that(28)θx−θx^k+w−w^k⊤Fw^k≥w−w^k⊤Qwk−w^k,∀w∈W,where the matrix Q is defined by(29)Q=β1+νA1⊤A1000β1+νA2⊤A20−A1−A2Ilβ.Proof.
By the first-order optimality condition of the two minimization problems in (23), for any x1∈X1andx2∈X2, we have(30)θ1x1−θ1x^1k+x1−x^1k⊤−A1⊤λ^k−β1+νA1⊤A1x1k−x^1k≥0,θ2x2−θ2x^2k+x2−x^2k⊤−A2⊤λ^k−β1+νA2⊤A2x2k−x^2k≥0.
The definition of the variableλ^k in (24) gives(31)λ−λ^k⊤A1x^1k+A2x^2k−b+A1x1k−x^1k+A2x2k−x^2k+1βλ^k−λk≥0,∀λ∈ℜl.
Adding the above three inequalities, using the notation ofθx and Fw, we can get the compact form (28) and this completes the proof.Remark 2.
IfmaxA1x1k−A1x1k+1,A2x2k−A2x2k+1,λk−λk+1=0, then by (24), we have A1x1k=A1x^1k,A2x2k=A2x^2k,λk=λ^k. So, Qwk−w^k=0. Substituting it into the right-hand side of (28), we have(32)θx−θx^k+w−w^k⊤Fw^k≥0,∀w∈W.
So,wk∈W∗, and the stopping criterion of the PSALM is reasonable.
With inequalities (26) and (28) in hand, to establish the convergence results of the PSALM, we only need to ensure the matrices MandQ defined as in (27) and (29) satisfy the convergence condition.Lemma 2.
Let the matricesQandM be defined as in (27) and (29). If α∈0,2ν/1+ν and Assumption 1 holds, then(i)
The matrixQ+Q⊤ is positive definite(ii)
The matrixH=QM−1 is symmetric and positive definite(iii)
The matrixGα=Q+Q⊤−αM⊤HM is symmetric and positive definiteProof.
(i)
From the definition of the matrixQ, we have
(33)
Q
+
Q
⊤
=
2
β
1
+
ν
A
1
⊤
A
1
0
−
A
1
⊤
0
2
β
1
+
ν
A
2
⊤
A
2
−
A
2
⊤
−
A
1
−
A
2
2
I
l
β
,
which is positive definite fromν>0 and Assumption 1.
(ii)
From the definition of the matricesQandM, we have
(34)
H
=
α
β
1
+
ν
A
1
⊤
A
1
0
0
0
α
β
1
+
ν
A
2
⊤
A
2
0
0
0
I
l
β
,
which is symmetric and positive definite by Assumption 1.
(iii)
Similarly, from the definition ofQ,M, we have
(35)
G
α
=
β
1
+
ν
−
α
A
1
⊤
A
1
−
α
β
A
1
⊤
A
2
−
1
−
α
A
1
⊤
−
α
β
A
2
⊤
A
1
β
1
+
ν
−
α
A
2
⊤
A
2
−
1
−
α
A
2
⊤
−
1
−
α
A
1
−
1
−
α
A
2
2
−
α
I
l
β
=
L
⊤
R
α
L
,where(36)L=βA1000βA2000Ilβ,Rα=1+ν−αIl−αIl−1−αIl−αIl1+ν−αIl−1−αIl−1−αIl−1−αIl2−αIl.
From Assumption 1, we only need to prove the matrixRα is positive definite. In fact, it can be written as(37)1+ν−α−α−1−α−α1+ν−α−1−α−1−α−1−α2−α⊗Il,where ⊗ denotes the matrix Kronecker product. Thus, we only need to prove the 3 order matrix(38)1+ν−α−α−1−α−α1+ν−α−1−α−1−α−1−α2−α,is positive definite. Its three eigenvalues are λ1=1+ν, λ2=3+ν−3α−9α2−2αν−14α+ν2−2v+9/2,λ3=3+ν−3α+9α2−2αν−14α+ν2−2v+9/2. Then, solving the following three inequalities(39)1+ν>0,3+ν−3α−9α2−2αν−14α+ν2−2v+9>0,3+ν−3α+9α2−2αν−14α+ν2−2v+9>0,we get 0<α<2ν/1+ν. Therefore, the matrix G is positive definite for any α∈0,2ν/1+ν. In addition, from its expression, the matrix Gα is obviously symmetric. This completes the proof.
Lemma2 indicates that the matrices QandM defined as in (27) and (29) satisfy convergence condition, and according to the result in [15], we get the following convergence results of new PSALM.Theorem 1 (global convergence).
Letwk be the sequence generated by new PSALM. Then, it converges to some w∞, which belongs to W∗.Theorem 2 (ergodic convergence rate).
Letwk be the sequence generated by new PSALM, w^k be the corresponding sequence defined as in (24). Set(40)w¯t=1t∑k=0t−1w^k.
Then, for any integert≥0, we have(41)θx¯t−θx+w¯t−w⊤Fw≤12αtw−w0H2,∀w∈W.Theorem 3 (nonergodic convergence rate).
Letwk be the sequence generated by new PSALM. Then, for any w∗∈W∗ and integer t≥0, we have(42)Mwt−w^tH2≤1c0tw0−w∗H2,where c0>0 is a constant.
Note that the right-hand side of (41) is independent of the distance between the initial iterate w0 and the solution set W∗. Therefore, (41) is not a reasonable criterion to measure the nonergodic convergence rate. In the following, we give a refined result to measure the nonergodic convergence rate of the sequence wk generated by new PSALM.Lemma 4.
Letwk be the sequence generated by new PSALM. Then, for any w∈W, we have(43)αθx−θx^k+w−w^k⊤Fw^k≥12w−wk+1H2−w−wkH2+α2wk−w^Hk2.Proof.
The proof is similar to that of Lemma 3.1 in [15] and is omitted for brevity of this paper.Theorem 4 (refined ergodic convergence rate).
Letwk be the sequence generated by the PSALM, and set(44)w¯t=1t∑k=0t−1w^k.
Then, for any integert≥0, there exists a constant c>0 such that(45)θx¯t−θx∗≤c2αt,Ax¯t−b≤c2αt.Proof.
Choosew∗=x∗,λ∗∈W∗. Then, for any λ∈ℜl, we have w˜∗≔x∗,λ∈W. From the notion of Fw and (15), we have(46)w˜∗−w^k⊤Fw^k=w˜∗−w^k⊤Fw˜∗=x∗−x^kλ−λ^k⊤−A⊤λAx∗−b=−λ⊤Ax∗−Ax^k=λ⊤Ax^k−b.
Setw=w˜∗ in (43), and we obtain(47)αθx^k−θx∗−w˜∗−w^k⊤Fw^k≤12w˜∗−wkH2−w˜∗−wk+1H2−α2wk−w^kH2.
Combining the above two inequalities gives(48)αθx^k−θx∗−λ⊤Ax^k−b≤12w˜∗−wkH2−w˜∗−wk+1H2−α2wk−w^kH2.
Summing the abovementioned inequality fromk=0 to t−1 yields(49)∑k=0t−1θx^k−tθx∗−λ⊤A∑k=0t−1x^k−tb≤12αw˜∗−w0H2.
Dividing the both sides of the above inequality byt, we obtain(50)1t∑k=0t−1θx^k−θx∗−λ⊤Ax¯t−b≤12αtw˜∗−w0H2.
Then, it follows from the convexity ofθ1 and θ2 that(51)θx¯t−θx∗−λ⊤Ax¯t−b≤12αtx0−x∗λ0−λH2.
Since (51) holds for any λ, we set(52)λ=−Ax¯t−bAx¯t−b,and obtain(53)θx¯t−θx∗+Ax¯t−b≤12αtsupλ≤1x0−x∗λ0−λH2.
Set(54)c=supλ≤1x0−x∗λ0−λH2,and we thus obtain(55)θx¯t−θx∗+Ax¯t−b≤c2αt.
Sincex∗∈X∗, we have(56)θx¯t−θx∗≥0.
Combining the above two inequalities gives(57)θx¯t−θx∗≤c2αt,Ax¯t−b≤c2αt,which completes the proof.The following example is to test the influence of the parametersνandα on this new PSALM.Example 2 (go on with Example 1).
For this new PSALM, we setβ=1, and the resulting iterative scheme is(58)x1k+1x2k+1λk+1=11+νν−11−1ν1α1−να1−ν1+ν−2αx1kx2kλk.
Furthermore, we set the initial pointx10=x20=0andλ0=1, and the stopping criterion is set as(59)maxx1k+x2k,λk≤10−5,or the number of iterations exceeds 10000.
The left subplot of Figure1 graphically depicts the numerical results when ν=5andα=0.1:0.1:1.5. It reveals that when ν is fixed, the larger α is, the better of the new PSALM’s performance is. The right subplot of Figure 1 graphically depicts the numerical results when ν=0.1:0.1:5andα=1.9ν/1+ν. It reveals that when ν takes some values near 1, the new PSALM always performs best. This is in conformity with the intuition because the large value of this parameter makes the proximal term νβ/2A1x1−A1x1k2 taking a too heavy weight in the objective function ℒβx1,x2k,λk+νβ/2A1x1−A1x1k2, leads to a very small increment of the variable x1, and finally decreases the convergence speed of the new PSALM. On the contrary, the small value of this parameter also makes the step size α=1.9ν/1+ν to be very small. Therefore, how to choose a suitable combination of αandν is a challenging issue.Figure 1
Sensitivity test on the parametersνandα.Remark 3.
The step sizeα is at the denominator of the right-hand side terms of (45). Therefore, the bigger α is, the smaller the right-hand side terms of (45) are, and the new PSALM may need less iteration to generate an ε-approximate solution of problem (1).


## 3. Numerical Results

In this section, we demonstrate the potential efficiency of this new PSALM by solving the video background extraction problem (6).


### 3.1. Simulation Study

Firstly, we generate a low-rank matrixL∗∈ℜm×m and a sparse matrix S∗∈ℜm×m. Secondly, we get an observation matrix D=L∗+S∗ be an observation matrix. Thirdly, we want to recover the low-rank matrix L∗ and the sparse matrix S∗ by problem (6) with D as the input matrix and LandS as the unknown matrices. In the following, let rand spr represent the low-rank ratio of L∗ and the ratios of the number of nonzeros entries of S∗ (i.e., S∗0/pq), respectively. We use the following Matlab script to generate matrix D:(i)
L=randnm,r∗randnr,n(ii)
S=zerosm,n;q=randpermm∗n;K=roundspr∗m∗n;Sq1:K=randnK,1(iii)
D=L+SWe setm=n=100 and tested(60)r,spr=1.0,0.05,5,0.05,10,0.05,15,0.05,1.0,0.1,5,0.1,10,0.1,15,0.1.We empirically setτ=0.1 in problem (6), and α=1.3,β=0.05/meanabsD:,ν=2 in the PSALM. The initial iterate L0,S0,Λ0=0,0,0, and use the stopping criterion(61)RelChg≔Lk+1,Sk+1−Lk,Sk1+Lk,Sk<10−8,or the number of iterations exceeds 1000. Let L^andS^ be the numerical solution of problem (6) obtained by the PSALM, and we measure the quality of recovery by the relative error to L∗,S∗, which is defined by(62)RelErr≔L^,S^−L∗,S∗1+L∗,S∗.In Table1, we report the recovery results on simulated matrices with size m=n=100. Note that for the recovered sparse matrix S^, to eliminate the roundabout error, we have reset the component whose the absolute value is less than 0.01 to be 0, i.e., SabsS<0.01=0. From this table, it can be seen that (i) the rank of the low-rank matrix L∗ can be exactly recovered, while the sparse matrix S∗ is recovered approximately; (ii) though S∗ is not recovered completely, the relative error RelErr indicates that the precision of the recovered S^ is high.Table 1
Numerical results on simulated matrices with sizem=n=100.
r
,
spr
RelErr
RankL∗
RankL^
S
∗
0
S
^
0
(1, 0.05)
3.7215e − 05
1
1
500
499
(1, 0.1)
2.6670e − 05
1
1
1000
999
(5, 0.05)
3.7402e − 05
5
5
500
499
(5, 0.1)
2.7067e − 05
5
5
1000
1001
(10, 0.05)
4.2738e-06
10
10
500
500
(10, 0.1)
4.9249e − 06
10
10
1000
1000
(15, 0.05)
3.8210e − 05
15
15
500
504
(15, 0.1)
3.1827e − 05
15
15
1000
1028In Figure2, we present the convergence result for problem (6) with r=5and spr=0.1. From this figure, it can be observed that when the number of iterations k=80, the relative error RelErr achieves at a stable state. It decreases almost linearly with k before k=80, while it almost does not decrease any more after k=80.Figure 2
Convergence results forr=5and spr=0.1.


### 3.2. An Application Example

In this section, we apply the new PSALM(NEW−PSALM) to solve a concrete problem of model (6): the video background extraction problem [17], which aims to subtract the background from (the low-rank matrix L) a video clip (stacking as the matrix D) and meanwhile detect the moving objects (the sparse matrix S). We set τ=1/maxm,n in problem (6). We have downloaded the video clip: Highway from the Internet. For comparison, we also applied the iteration method in [4] (denoted by TY−VASALM) and the iteration method in [13] (denoted by HTY−IMA) to solve this problem.Figure3 presents the extracted backgrounds and foregrounds images by TY−VASALM, HTY−IMA, and NEW−PSALM. Clearly, all methods can extract satisfactory resultsFigure 3
The decomposed results by TY−VASALM (a), HTY−IMA (b), and NEW−PSALM (c).
(a)
(b)
(c)Table2 lists the detail experimental results, where the number of iterations (Iteration), CPU time in seconds (CPU), the rank of the recovered final low-rank matrix (Rank), and the number of nonzeros of the recovered final sparse matrix (Sparse) are reported. From the results given in Table 2, we see that NEW−PSALM is faster than the other two methods in terms of both iteration numbers and CPU time. In particular, NEW−PSALM outperforms all the other two methods in recovering low rank and sparse components. These results clearly illustrate the efficiency and robustness of NEW−PSALM.Table 2
Numerical results generated by TY−VASALM, HTY−IMA, and NEW−PSALM.
Algorithm
Iteration
CPU
Rank
Sparse
TY−VASALM
26
290.5518
58
5941722
HTY−IMA
20
389.5898
79
8146712
NEW−PSALM
17
51.8672
54
4683149


## 3.1. Simulation Study

Firstly, we generate a low-rank matrixL∗∈ℜm×m and a sparse matrix S∗∈ℜm×m. Secondly, we get an observation matrix D=L∗+S∗ be an observation matrix. Thirdly, we want to recover the low-rank matrix L∗ and the sparse matrix S∗ by problem (6) with D as the input matrix and LandS as the unknown matrices. In the following, let rand spr represent the low-rank ratio of L∗ and the ratios of the number of nonzeros entries of S∗ (i.e., S∗0/pq), respectively. We use the following Matlab script to generate matrix D:(i)
L=randnm,r∗randnr,n(ii)
S=zerosm,n;q=randpermm∗n;K=roundspr∗m∗n;Sq1:K=randnK,1(iii)
D=L+SWe setm=n=100 and tested(60)r,spr=1.0,0.05,5,0.05,10,0.05,15,0.05,1.0,0.1,5,0.1,10,0.1,15,0.1.We empirically setτ=0.1 in problem (6), and α=1.3,β=0.05/meanabsD:,ν=2 in the PSALM. The initial iterate L0,S0,Λ0=0,0,0, and use the stopping criterion(61)RelChg≔Lk+1,Sk+1−Lk,Sk1+Lk,Sk<10−8,or the number of iterations exceeds 1000. Let L^andS^ be the numerical solution of problem (6) obtained by the PSALM, and we measure the quality of recovery by the relative error to L∗,S∗, which is defined by(62)RelErr≔L^,S^−L∗,S∗1+L∗,S∗.In Table1, we report the recovery results on simulated matrices with size m=n=100. Note that for the recovered sparse matrix S^, to eliminate the roundabout error, we have reset the component whose the absolute value is less than 0.01 to be 0, i.e., SabsS<0.01=0. From this table, it can be seen that (i) the rank of the low-rank matrix L∗ can be exactly recovered, while the sparse matrix S∗ is recovered approximately; (ii) though S∗ is not recovered completely, the relative error RelErr indicates that the precision of the recovered S^ is high.Table 1
Numerical results on simulated matrices with sizem=n=100.
r
,
spr
RelErr
RankL∗
RankL^
S
∗
0
S
^
0
(1, 0.05)
3.7215e − 05
1
1
500
499
(1, 0.1)
2.6670e − 05
1
1
1000
999
(5, 0.05)
3.7402e − 05
5
5
500
499
(5, 0.1)
2.7067e − 05
5
5
1000
1001
(10, 0.05)
4.2738e-06
10
10
500
500
(10, 0.1)
4.9249e − 06
10
10
1000
1000
(15, 0.05)
3.8210e − 05
15
15
500
504
(15, 0.1)
3.1827e − 05
15
15
1000
1028In Figure2, we present the convergence result for problem (6) with r=5and spr=0.1. From this figure, it can be observed that when the number of iterations k=80, the relative error RelErr achieves at a stable state. It decreases almost linearly with k before k=80, while it almost does not decrease any more after k=80.Figure 2
Convergence results forr=5and spr=0.1.


## 3.2. An Application Example

In this section, we apply the new PSALM(NEW−PSALM) to solve a concrete problem of model (6): the video background extraction problem [17], which aims to subtract the background from (the low-rank matrix L) a video clip (stacking as the matrix D) and meanwhile detect the moving objects (the sparse matrix S). We set τ=1/maxm,n in problem (6). We have downloaded the video clip: Highway from the Internet. For comparison, we also applied the iteration method in [4] (denoted by TY−VASALM) and the iteration method in [13] (denoted by HTY−IMA) to solve this problem.Figure3 presents the extracted backgrounds and foregrounds images by TY−VASALM, HTY−IMA, and NEW−PSALM. Clearly, all methods can extract satisfactory resultsFigure 3
The decomposed results by TY−VASALM (a), HTY−IMA (b), and NEW−PSALM (c).
(a)
(b)
(c)Table2 lists the detail experimental results, where the number of iterations (Iteration), CPU time in seconds (CPU), the rank of the recovered final low-rank matrix (Rank), and the number of nonzeros of the recovered final sparse matrix (Sparse) are reported. From the results given in Table 2, we see that NEW−PSALM is faster than the other two methods in terms of both iteration numbers and CPU time. In particular, NEW−PSALM outperforms all the other two methods in recovering low rank and sparse components. These results clearly illustrate the efficiency and robustness of NEW−PSALM.Table 2
Numerical results generated by TY−VASALM, HTY−IMA, and NEW−PSALM.
Algorithm
Iteration
CPU
Rank
Sparse
TY−VASALM
26
290.5518
58
5941722
HTY−IMA
20
389.5898
79
8146712
NEW−PSALM
17
51.8672
54
4683149


## 4. Conclusion

In this paper, we have proposed a new parallel splitting augmented Lagrangian method(NEW−PSALM) for two-block separable convex programming and have established its various convergence results, including global convergence, ergodic, and nonerogdic convergence rate. Numerical results indicate that it is efficient for the video background extraction problem.Practical experiments indicate that the ALM and its various variants with the step sizeα∈1,2 can often accelerate the convergence speed, while in the new PSALM, to ensure the step size α∈1,2, the parameter ν must larger than 1, such as α∈0,1.9 only if ν≥19. However, as we have mentioned in Example 2, large ν often decreases the convergence speed of the new PSALM. Therefore, the ALM type methods with less restrictions imposed on νandα deserve further researching, and we leave this problem as a future research work.



---

*Source: 6872810-2020-02-21.xml*