The modified accelerated Bregman method for regularized basis pursuit problem

Abstract

In this paper, a modified accelerated Bregman method (MABM) for solving the regularized basis pursuit problem is considered and analyzed in detail. This idea is based on the fact that the linearized Bregman method (LBM) proposed by Osher et al. (Multiscale Model. Simul. 4(2):460-489, 2005) is equivalent to a gradient descent method applied to a certain dual formulation which converges to the solution of the regularized basis pursuit problem. The proposed method is based on an extrapolation technique which is used in accelerated proximal gradient methods presented by Nesterov (Dokl. Akad. Nauk SSSR 269:543-547, 1983). It is verified that the modified accelerated Bregman method (MABM) is equivalent to the corresponding accelerated augmented Lagrangian method (AALM). The theoretical results confirm that the method has a rapid convergence rate of $O(1/{(k+1)}^2)$.

1 Introduction

Compressed sensing, an interesting research field involving how to obtain information, acts as a crucial role in signal processing, image restoration, etc. The origin of its name is based on the idea of encoding a large sparse signal exploiting a relatively small number of linear measurements, then decoding the signal either through minimizing the 1-norm or utilizing a combinational algorithm, a greedy algorithm, etc. It resulted from elementary analysis and approximation theory by Kashin [1], but was brought into the forefront by the work of Candés et al. [2–4] and Donoho [5] who constructed specific methods and showed their application prospects. The concrete model considered in compressed sensing is the so-called basis pursuit problem [6, 7]

$$\underset{x\in {\mathrm{\Re }}^n}{min}{\parallel x\parallel }_1\text{subject to }Ax=b,$$

(1.1)

where $A\in {\mathrm{\Re }}^{m\times n}$, $b\in {\mathrm{\Re }}^m$. It can be deemed a classical transform in the compressed sensing field into the following NP-hard discrete optimization problem:

$$\underset{x\in {\mathrm{\Re }}^n}{min}{\parallel x\parallel }_0\text{subject to }Ax=b,$$

(1.2)

where $A\in {\mathrm{\Re }}^{m\times n}$, $b\in {\mathrm{\Re }}^m$, ${\parallel \cdot \parallel }_0$ denotes the number of nonzero elements.

In many practical circumstances, the data or signals are frequently represented by a few matrices, which, in fact, is convenient for data processing and analysis. However, the data are often given with damage, loss or noise pollution, etc. In this case, how to restore the original data is among the practical difficulties faced when solving the matrix reconstruction problem. Being similar to handling the original signal (vector form) in the compressed sensing field, matrix remodeling refers to an original compressible or sparse representation matrix which can be exactly or approximately reconstructed with a proper model. The matrix reconstruction problem can be classified with matrix completion (MC) [8, 9] and matrix recovery (MR) [10, 11], which is met in various areas, e.g., a famous application is the Netflix system [12] in matrix completion; while the matrix recovery problem originates from face image processing, background modeling and so forth, it can be applied to image alignment as by Peng et al. [13]. Generally speaking, the matrix reconstruction problem is written as

$$minrank(X)\text{subject to }X\in C,$$

(1.3)

where $X\in {\mathrm{\Re }}^{m\times n}$ and C is a convex set. Normally, the following affine constrained minimization problem can be considered:

$$minrank(X)\text{subject to }A(X)=b,$$

(1.4)

where the linear map $A:{\mathrm{\Re }}^{m\times n}\to {\mathrm{\Re }}^d$, $b\in {\mathrm{\Re }}^d$ is a given vector.

The model emerges in many fields, such as determining a low-order controller for a plant [14] and a minimum order linear system realization [15], and solving low-dimensional Euclidean embedding problems [16]. A natural generalization in the sense of compressed sensing, (1.4) can be formulated as the nuclear norm minimization problem

$$min{\parallel X\parallel }_{\ast }\text{subject to }A(X)=b,$$

(1.5)

where ${\parallel \cdot \parallel }_{\ast }$ denotes the sum of singular values of the corresponding matrix. The matrix completion problem

$$minrank(X)\text{subject to }{X}_{i,j}=M_{i,j},(i,j)\in \mathrm{\Omega },$$

(1.6)

where $X\in {\mathrm{\Re }}^{m\times n}$, $M\in {\mathrm{\Re }}^{m\times n}$, Ω is a certain index set, is considered as a special case of (1.3). The idea is inspired by the method presented in [17, 18]etc. Now, we consider the so-called regularized basis pursuit problem

$$\underset{x\in {\mathrm{\Re }}^n}{min}{\parallel x\parallel }_1+\frac{\mu }{2}{\parallel x\parallel }_2^2\text{subject to }Ax=b.$$

(1.7)

Adding the penalized term of the constraint condition to the objection function of the regularized basis pursuit problem, we obtain

$$\underset{x\in {\mathrm{\Re }}^n}{min}{\parallel x\parallel }_1+\frac{\mu }{2}{\parallel x\parallel }_2^2+\frac{\lambda }{2}{\parallel Ax-b\parallel }_2^2.$$

(1.8)

Particularly in [18], putting in the term in (1.7) yields the tractable object function, which is a strictly convex function. Thus, the linearly constrained basis pursuit problem has a sole solution and its dual problem is smooth. When μ is sufficiently small, the solution to (1.7) is also the solution of (1.1). This exact regularization property of (1.7) was studied in [19, 20]. Problem (1.7) has a 2-norm in the regularizer term, thus it is considered less sensitive to noise than the basis pursuit problem (1.1).

To solve (1.1), a linearized Bregman iteration method was presented in [21], which was motivated by [22]. The idea of the linearized Bregman method is to combine a fixed point iteration with the Bregman method in [23, 24], but the linearized Bregman method is a bit slow in the convergence result. Hence, many accelerated schemes have been brought up in various theses. For example, in [21] the kicking technique was introduced. Yin [19] verified that the linearized Bregman method is equivalent to a gradient descent method applied to the Lagrangian dual problem of (1.7). They improved the linearized Bregman method, utilizing the Barzilai-Borwein line of searching [25], nonlinear conjugate gradient methods, and the method of limited memory BFGS [26]. Huang et al. [18] proposed an accelerated linearized Bregman method which is based on the fact that the linearized Bregman method is equivalent to the gradient descent method applied to a Lagrangian dual of problem (1.7) and the extrapolation technique, which is adopted in the accelerated proximal gradient methods [27] proposed by Nesterov et al. To solve problem (1.7), Goldstein et al. [28] used an alternating split technique and its Lagrange dual problem.

Based on these studies, we extend the accelerated Bregman method to solve (1.7) in which the object function might be not differentiable but have the ‘good’ performance (convex and continuous). We put forward a new improvement formula based on the accelerated Bregman method. It can be proved to have the property that the modified Bregman method is equivalent to the corresponding accelerated augmented Lagrangian method, and the latter has a rapid convergence rate which can be deemed to be an improvement of [17].

The rest of this article is organized as follows. In Section 2, we sketch the original Bregman method and the linearized Bregman method which are useful for the subsequent analysis. In Section 3, we introduce the accelerated augmented Lagrangian method (AALM), and we present our modified accelerated Bregman method (MABM). Section 4 is devoted to the convergence of the regularized basis pursuit problem and here we analyze the error bound of the MABM in detail. In Section 5, we give some conclusions and discuss the research plans for our future work.

2 The original Bregman method and its linearized form

The Bregman method was introduced into image processing by Osher et al. in [23] for solving the total-variation (TV)-based image restoration problems. Let $\phi (\cdot )$ be a Bregman function, the Bregman distance [29] of the point u to the point v is defined as

$$D_{\phi }^p(u,v):=\phi (u)-\phi (v)-〈p,u-v〉,$$

(2.1)

where $p\in \partial \phi (v)$, the subdifferential of φ at v. Note that updating the formula for (1.7), this Bregman iterative regularization procedure recursively solves

$$x^{k+1}:=arg\underset{x}{min}{D}_{\phi }^{p^k}(x,x^k)+\frac{\lambda }{2}{\parallel Ax-b\parallel }_2^2$$

(2.2)

for $k=0,1,\dots$ , starting with $x^0=0$, $p^0=0$. Since (2.2) is a convex programming problem, the optimality conditions can be given by

$$0\in \partial \phi \left(x^{k+1}\right)-p^k-\lambda A^T(b-A{x}^{k+1}),$$

(2.3)

from which we obtain the updated formula

$$p^{k+1}:=p^k+\lambda A^T(b-A{x}^{k+1}).$$

(2.4)

Hence, the Bregman iterative scheme is given by

$$\{\begin{array}{l}{x}^{k+1}:=arg{min}_x{D}_{\phi }^{p^k}(x,x^k)+\frac{\lambda }{2}{\parallel Ax-b\parallel }_2^2,\\ p^{k+1}:=p^k+\lambda A^T(b-A{x}^{k+1}).\end{array}$$

(2.5)

By the following lemma, we get the equivalent form of (2.5)

$$\{\begin{array}{l}{x}^{k+1}:=arg{min}_x\phi (x)+\frac{\lambda }{2}{\parallel Ax-b^k\parallel }_2^2,\\ b^{k+1}:=b^k+(b-A{x}^{k+1}),\end{array}$$

(2.6)

starting with $x^0=0$, $b^0=b$.

For the sake of the requirement for the whole theoretical analysis, in the following, we propose some significant equivalence results, and we give the detailed proofs.

Lemma 2.1 The Bregman iterative scheme, which is given by (2.5), will obtain the same optimum point in the first term as (2.6) if

$$p^k=\lambda A^T(b^k-b)$$

(2.7)

holds, where λ is a certain positive constant.

Proof From the first formula of (2.5) and the definition of Bregman distance (2.1), we get

$$\begin{array}{rcl}{x}^{k+1}& =& arg\underset{x}{min}\phi (x)-\phi \left(x^k\right)-〈p^k,x-x^k〉+\frac{\lambda }{2}{\parallel Ax-b\parallel }_2^2\\ =& arg\underset{x}{min}\phi (x)-〈\lambda A^T(b^k-b),x〉+\frac{\lambda }{2}{\parallel Ax-b\parallel }_2^2\\ =& arg\underset{x}{min}\phi (x)-\lambda 〈b^k-b,Ax-b〉+\frac{\lambda }{2}{\parallel Ax-b\parallel }_2^2+\frac{\lambda }{2}{\parallel b^k-b\parallel }_2^2\\ =& arg\underset{x}{min}\phi (x)-\frac{\lambda }{2}{\parallel Ax-b^k\parallel }_2^2,\end{array}$$

therefore, we complete the proof. □

From the discussion above, we can give a crucial conclusion.

Theorem 2.2 The original Bregman iterative scheme (2.5) is equivalent to its variant (2.6).

Proof By induction, in fact, we only need to verify that (2.7) holds.

If $k=0$, $p^0=\lambda A^T(b^0-b)=0$, (2.5) holds by the initial conditions $p^0=0$ and $b^0=b$.

Now, we suppose that (2.7) holds for $k-1$. Then

$$\begin{array}{rcl}{p}^k& =& p^{k-1}+\lambda A^T(b-A{x}^k)\\ =& \lambda A^T(b^{k-1}-b)+\lambda A^T(b-A{x}^k)\\ =& \lambda A^T(b^{k-1}-b+b-A{x}^k)\\ =& \lambda A^T(b^k-b),\end{array}$$

where the first equality is from the second term of (2.5), and the third equality is from the second term of (2.6). Therefore, the original Bregman iterative scheme (2.5) is equivalent to its variant (2.6). □

Noting that [24, 30, 31] and the references therein, it was argued that the Bregman iterative method is equivalent to the augmented Lagrangian method. The significance of this statement will be demonstrated in our later analysis in Section 4.

For the following analysis, we define the Lagrangian function of (1.7),

$$L(x,\sigma ):=\phi (x)+〈\sigma ,b-Ax〉,$$

where $\sigma \in {\mathrm{\Re }}^m$ is the Lagrangian multiplier. The corresponding augmented Lagrangian function can be expressed as

$$L(x,\sigma ,\lambda ):=\phi (x)+〈\sigma ,b-Ax〉+\frac{\lambda }{2}{\parallel Ax-b\parallel }_2^2,$$

(2.8)

where $\phi (x):={\parallel x\parallel }_1+\frac{\mu }{2}{\parallel x\parallel }_2^2$ and $\frac{\lambda }{2}{\parallel Ax-b\parallel }_2^2$ is the penalty term.

The augmented Lagrangian iterative scheme is

$$\{\begin{array}{l}{x}^{k+1}:=arg{min}_x\phi (x)+〈{\sigma }^k,b-Ax〉+\frac{\lambda }{2}{\parallel Ax-b\parallel }_2^2,\\ {\sigma }^{k+1}:={\sigma }^k+\lambda (b-A{x}^{k+1}),\end{array}$$

(2.9)

starting from ${\sigma }^0=0$.

Lemma 2.3 The first item of the iterative sequence $\{x^k\}$ of (2.9) and that of (2.6) are equal if

$$b^k=b+\frac{1}{\lambda }\sigma$$

(2.10)

holds.

Proof From the first formula of (2.6) and (2.10), we get

$$\begin{array}{rcl}{x}^{k+1}& =& arg\underset{x}{min}\phi (x)+\frac{\lambda }{2}{\parallel Ax-b-\frac{{\sigma }^k}{\lambda }\parallel }_2^2\\ =& arg\underset{x}{min}\phi (x)+\frac{\lambda }{2}{\parallel Ax-b\parallel }_2^2+〈{\sigma }^k,b-Ax〉.\end{array}$$

The constant of the objective function does not affect the optimum point, so by comparing with the above equations, we get the conclusion. □

Theorem 2.4 The augmented Lagrangian iterative scheme (2.9) is equivalent to the Bregman iterative method variant (2.6).

Proof It is not difficult to see that the proof is the same as that of Theorem 2.2. Similarly, by the mathematical induction, we simply show that (2.7) holds.

If $k=0$, $b^0=b+\frac{{\sigma }^0}{\lambda }$, (2.7) holds by the initial conditions ${\sigma }^0=0$ and $b^0=b$. Now, we suppose that (2.7) holds for $n\le k-1$. Then, when $n=k$,

$$\begin{array}{rcl}{b}^k& =& b^{k-1}+(b-A{x}^k)=b+\frac{1}{\lambda }{\sigma }^{k-1}+(b-A{x}^k)\\ =& b+\frac{1}{\lambda }{\sigma }^{k-1}+\frac{1}{\lambda }({\sigma }^k-{\sigma }^{k-1})=b+\frac{1}{\lambda }{\sigma }^k,\end{array}$$

where the first equality is from the second term of (2.6), the second equality has its roots in induction, and the third equality is derived from the second term of (2.9). Therefore, the augmented Lagrangian iterative scheme (2.9) is equivalent to the Bregman iterative method variant (2.6). Moreover, we can get the equivalence of (2.5) and (2.9) from the two theorems above. □

For solving the subproblem of Bregman iterative method (2.2), different algorithms were conceived in [27, 32, 33], however, these methods have to perform significant iterations for solving the subproblem. In order to overcome the difficulties, the linearized Bregman method is obtained by linearizing the last term in (2.2) into $〈A^T(A{x}^k-b),x〉$ (where $\lambda =1$) and adding the $l_2$-proximity term $\frac{1}{2\gamma }{\parallel x-x^k\parallel }^2$. The concrete scheme is

$$\{\begin{array}{l}{x}^{k+1}:=arg{min}_x{D}_{\phi }^{p^k}(x,x^k)+〈A^T(A{x}^k-b),x〉+\frac{1}{2\gamma }{\parallel x-x^k\parallel }_2^2,\\ p^{k+1}:=p^k+A^T(A{x}^{k+1}-b)-\frac{1}{\gamma }(x-x^k).\end{array}$$

(2.11)

By the optimality conditions, we obtain the following formula:

$$0\in \partial \phi \left(x^{k+1}\right)-p^k-A^T(b-A{x}^k)+\frac{1}{\gamma }(x^{k+1}-x^k).$$

That is, for the second term of (2.11) $p^{k+1}\in \partial \phi (x^{k+1})$. In [7, 19, 21], the linearized Bregman method was analyzed; as $\gamma <\frac{2}{{\parallel A\parallel }^2}$ (where $\parallel \cdot \parallel$ denotes the spectral norm of the corresponding matrix) the iterates of the linearized Bregman method converge to the solution of the regularized basis pursuit problem

$$\underset{x\in {\mathrm{\Re }}^n}{min}{\parallel x\parallel }_1+\frac{1}{2\gamma }{\parallel x\parallel }_2^2\text{subject to }Ax=b.$$

It has appeared in the accelerated Bregman algorithm in recent years, such as in [18]etc. But we shall argue that the accelerated Bregman method has large room to advance. We give some valid improvements on these accelerated Bregman methods. It can be verified that the theoretical result as regards the proposed method has a rapid convergence rate of $O(1/{(k+1)}^2)$.

3 The modified accelerated Bregman method

In [24], the linearized Bregman algorithm could be written as follows.

Algorithm 3.1 (Linearized Bregman method (LBM))

Step 0. Input: $J(\cdot ),H(\cdot ),\gamma >0$; initial point: $x^0$, $p^0$.

Step 1. Initialize: $k=0$, let $x^0=0$ and $p^0=0$.

Step 2. Compute $x^{k+1}:=arg{min}_x{D}_{\phi }^{p^k}(x,x^k)+〈\mathrm{\nabla }H(x^k),x〉+\frac{1}{2\gamma }{\parallel x-x^k\parallel }_2^2$.

Step 3. Set $p^{k+1}:=p^k-\mathrm{\nabla }H(x^k)-\frac{1}{\gamma }(x^{k+1}-x^k)$.

Step 4. Set $k:=k+1$, go to step 2.

For the iterative scheme above, $H(x)=\frac{1}{2}{\parallel Ax-b\parallel }_2^2$. Next, we give its equivalence form from the following lemma.

Lemma 3.2 The linearized Bregman method (LBM) in Algorithm 3.1 is equivalent to the iterative scheme

$$\{\begin{array}{l}{x}^{k+1}:=arg{min}_x\phi (x)+\frac{1}{2\gamma }{\parallel x-\gamma u^k\parallel }_2^2,\\ u^{k+1}:=u^k+A^T(b-A{x}^{k+1}),\end{array}$$

(3.1)

starting from $u^0=A^{T}b$, where $u^k=p^k+A^T(b-A{x}^k)+\frac{x^k}{\gamma }$.

Proof From step 3 of Algorithm 3.1, we have

$$p^{k+1}=p^k+A^T(b-A{x}^k)-\frac{1}{\gamma }(x^{k+1}-x^k)=\cdots =\sum _{i=0}^k{A}^T(b-A{x}^i)-\frac{1}{\gamma }{x}^{k+1}.$$

(3.2)

Thus, we denote

$$u^k:=p^{k+1}+\frac{1}{\gamma }{x}^{k+1}=p^k+A^T(b-A{x}^k)+\frac{1}{\gamma }{x}^k=\sum _{i=0}^k{A}^T(b-A{x}^i);$$

then we simplify step 2 of Algorithm 3.1,

$$\begin{array}{rcl}{x}^{k+1}& =& arg\underset{x}{min}\phi (x)+〈p^k,x〉-〈A^T(b-A{x}^k),x〉+\frac{1}{2\gamma }{\parallel x-x^k\parallel }_2^2\\ =& arg\underset{x}{min}\phi (x)+\frac{1}{2\gamma }{\parallel x-\gamma [p^k+A^T(b-A{x}^k)+\frac{x^k}{\gamma }]\parallel }_2^2\\ =& arg\underset{x}{min}\phi (x)+\frac{1}{2\gamma }{\parallel x-\gamma u^k\parallel }_2^2.\end{array}$$

On the other hand,

$$\begin{array}{rcl}{u}^{k+1}& =& p^{k+1}+A^T(b-A{x}^{k+1})+\frac{1}{\gamma }{x}^{k+1}\\ =& p^k+A^T(b-A{x}^k)-\frac{1}{\gamma }(x^{k+1}-x^k)+A^T(b-A{x}^{k+1})+\frac{x^{k+1}}{\gamma }\\ =& p^k+A^T(b-A{x}^k)+\frac{1}{\gamma }{x}^k+A^T(b-A{x}^{k+1})\\ =& u^k+A^T(b-A{x}^{k+1}),\end{array}$$

where the second equality is from (3.2). So, step 2 and step 3 in Algorithm 3.1 can be rewritten as (3.1). □

Yin et al. presented all kinds of techniques, for example, line search, and L-BFGS and BB steps, to accelerate the linearized Bregman method. It is interesting that for the latter in [18] the accelerated linearized Bregman algorithm is argued for as follows.

Algorithm 3.3 (Accelerated linearized Bregman method (ALBM))

Step 0. Initialize: $x^0={\tilde{x}}^0=p^0={\tilde{p}}^0=0$, $\gamma >0$, $\lambda >0$, $k=0$.

Step 1. Compute $x^{k+1}:=arg{min}_x{D}_{\phi }^{{\tilde{p}}^k}(x,{\tilde{x}}^k)+\lambda 〈A^T(A{\tilde{x}}^k-b),x〉+\frac{1}{2\gamma }{\parallel x-{\tilde{x}}^k\parallel }_2^2$.

Step 2. Set $p^{k+1}:={\tilde{p}}^k-\lambda A^T(A{\tilde{x}}^k-b)-\frac{1}{\gamma }(x^{k+1}-{\tilde{x}}^k)$.

Step 3. Set ${\tilde{x}}^{k+1}:={\alpha }_k{x}^{k+1}+(1-{\alpha }_k)x^k$.

Step 4. Set ${\tilde{p}}^{k+1}:={\alpha }_k{p}^{k+1}+(1-{\alpha }_k){\tilde{x}}^k$.

Step 5. Set $k:=k+1$, go to step 1.

These methods motivated us to consider the following algorithm, and its acceleration idea is based on the extrapolation technique proposed by Nesterov in [34, 35]; see also the references therein.

Algorithm 3.4 (Modified accelerated Bregman method (MABM))

Step 0. Initialize: $x^0=p^0={\tilde{p}}^0=0$, $t_0=1$, $\lambda >0$, $k=0$.

Step 1. Compute $x^{k+1}:=arg{min}_x{D}_{\phi }^{p^k}(x,x^k)+\frac{\lambda }{2}{\parallel Ax-b\parallel }_2^2$.

Step 2. Set ${\tilde{p}}^{k+1}:=p^k+\lambda A^T(b-A{x}^k)$.

Step 3. Set $p^{k+1}:=(1-\frac{1-2t_k}{t_{k+1}}){\tilde{p}}^{k+1}+\frac{1-2t_k}{t_{k+1}}{p}^k$.

Step 4. Set $t_{k+1}=\frac{1}{3}(\sqrt{1+9t_k^2}+1)$.

Step 5. Set $k:=k+1$, go to step 2.

The basic idea of the equivalence between MABA and the corresponding AALM can be traced back to [31]. Especially, we can see that our updated iterative for $p^k$ is obviously better than the pre-iterative ${\tilde{p}}^k$ [17], since we consider a sufficient amount of information about the former iterative. In this way, most of the better iterative efficiency could be expected, which is just our purpose in improving the method. Then we will be dependent on a series of transformations in preparation for the convergence proof in Section 4.

Lemma 3.5 The MABM in Algorithm 3.4 is equal to the following iterative scheme:

$$\{\begin{array}{l}{x}^{k+1}:=arg{min}_x\phi (x)+\frac{\lambda }{2}{\parallel Ax-b^k\parallel }_2^2,\\ {\tilde{b}}^{k+1}:=b^k+(b-A{x}^{k+1}),\\ b^{k+1}:=(1-\frac{1-2t_k}{t_{k+1}}){\tilde{b}}^{k+1}+\frac{1-2t_k}{t_{k+1}}{b}^k,\end{array}$$

(3.3)

starting with $b^0=b$.

Proof Recalling (2.7) and noting Theorem 2.2, we can prove that (2.7) holds for all k by induction.

If $k=0$, $p^0=\lambda A^T(b^0-b)=0$, (2.7) holds by the initial conditions $p^0=0$ and $b^0=b$. Now, we assume that (2.7) holds for $n\le k-1$, then

$$\begin{array}{rcl}{\tilde{p}}^n& =& p^{n-1}+\lambda A^T(b-A{x}^n)=\lambda A^T(b^{n-1}-b)+\lambda A^T(b-A{x}^n)\\ =& \lambda A^T(b^{n-1}-b+b-A{x}^n)=\lambda A^T({\tilde{b}}^n-b),\end{array}$$

(3.4)

where the first equality is directly derived from step 2 of Algorithm 3.4, the first equality is derived from the induction hypothesis, the fourth equality utilizes the second step of (3.3).

Moreover, when $n=k$, we have

$$\begin{array}{rcl}{p}^k& =& (1-\frac{1-2t_k}{t_{k+1}}){\tilde{p}}^k+\frac{1-2t_k}{t_{k+1}}{p}^{k-1}\\ =& (1-\frac{1-2t_k}{t_{k+1}})\lambda A^T({\tilde{b}}^k-b)+\frac{1-2t_k}{t_{k+1}}\lambda A^T(b^{k-1}-b)\\ =& \lambda A^T[(1-\frac{1-2t_k}{t_{k+1}}){\tilde{b}}^k-(1-\frac{1-2t_k}{t_{k+1}})b+\frac{1-2t_k}{t_{k+1}}{b}^{k-1}-\frac{1-2t_k}{t_{k+1}}b]\\ =& \lambda A^T(b^k-b),\end{array}$$

where the first equality is from step 3 of Algorithm 3.4, the second term is from (3.4) and the induction hypothesis, the fourth equality is from the third term of (3.3), so (2.7) holds for all k. Namely, the MABM in Algorithm 3.4 is equal to (3.3). □

Lemma 3.6 Iterative scheme (3.3) is equal to the following AALM iterative scheme:

$$\{\begin{array}{l}{x}^{k+1}:=arg{min}_x\phi (x)+〈{\sigma }^k,b-Ax〉+\frac{\lambda }{2}{\parallel Ax-b^k\parallel }_2^2,\\ {\tilde{\sigma }}^{k+1}:={\sigma }^k+(b-A{x}^{k+1}),\\ {\sigma }^{k+1}:=(1-\frac{1-2t_k}{t_{k+1}}){\tilde{\sigma }}^{k+1}+\frac{1-2t_k}{t_{k+1}}{\sigma }^k,\end{array}$$

(3.5)

starting from ${\sigma }^0=0$, where ${\sigma }^k\in {\mathrm{\Re }}^m$ is the Lagrangian multiplier.

Proof It is not difficult to see that the idea has likeness to Theorem 2.4, we are just required to verify that (2.7) holds. To this end, we proceed by mathematical induction.

If $k=0$, $b^0=b+\frac{{\sigma }^0}{\lambda }$, (2.7) holds by the initial conditions ${\sigma }^0=0$ and $b^0=b$. Suppose that (2.7) holds for $n\le k-1$, then, when $n=k$, we have

$$\begin{array}{rcl}{\tilde{b}}^k& =& b^{k-1}+(b-A{x}^k)=b+\frac{1}{\lambda }{\sigma }^{k-1}+(b-A{x}^k)\\ =& b+\frac{1}{\lambda }{\sigma }^{k-1}+\frac{1}{\lambda }({\tilde{\sigma }}^k-{\sigma }^{k-1})=b+\frac{1}{\lambda }{\tilde{\sigma }}^k,\end{array}$$

where the first equality is from the second term of (3.3), the second equality stems from induction, and the third equality is derived from the second term of (3.5).

Thus, we get

$$\begin{array}{rcl}{b}^k& =& (1-\frac{1-2t_k}{t_{k+1}}){\tilde{b}}^k+\frac{1-2t_k}{t_{k+1}}{b}^{k-1}\\ =& (1-\frac{1-2t_k}{t_{k+1}})(b+\frac{1}{\lambda }{\tilde{\sigma }}^n)+\frac{1-2t_k}{t_{k+1}}(b+\frac{1}{\lambda }{\sigma }^{n-1})\\ =& b+\frac{1}{\lambda }(\frac{1-2t_k}{t_{k+1}}{\tilde{\sigma }}^n+\frac{1-2t_k}{t_{k+1}}{\sigma }^{n-1})\\ =& b+\frac{1}{\lambda }{\sigma }^n.\end{array}$$

Therefore, AALM (3.5) is equivalent to iterative scheme (3.3). Moreover, we can get the equivalence of the MABM in Algorithm 3.4 to AALM from the above two lemmas. □

Theorem 3.7 The MABM in Algorithm 3.4 is equivalent to the corresponding AALM (3.5).

4 The convergence analysis

A practical challenge for the regularized basis pursuit problem is to offer an efficient method to solve the non-smooth optimization problems. Many algorithms have been proposed in recent years [36]. In these methods, some schemes of approximation that have to do with the non-smooth norm term are usually employed. However, a fast global convergence is difficult to guarantee. Due to the non-smooth nature of the 1-norm, a simple method to solve these problems is the subgradient approach [37], which converges only as $O(\frac{1}{\sqrt{k}})$, where k is the iteration counter.

In this paper, we present an efficient method with fast global convergence rate to solve the regularized basis pursuit problem. Particularly, we verify that this result is an extended gradient algorithm with the convergence rate of $O(\frac{1}{\sqrt{k}})$, like that for smooth problems. Following the Nesterov method for accelerating the gradient method [34, 35], we show that the MABM can be further accelerated to converge as $O(1/{(k+1)}^2)$.

A series of lemmas in the following are to ensure the convergence rate of the MABM.

Lemma 4.1 Let $(x^n,{\sigma }^n)$ be generated by the augmented Lagrangian iterative scheme (2.9), and let $(x^{\ast },{\sigma }^{\ast })$ be a globally optimal solution of the problem

$$\underset{x\in {\mathrm{\Re }}^n}{min}\phi (x)\mathit{\text{s.t. }}Ax=b,$$

(4.1)

then the inequality

$$\phi \left(x^k\right)-\phi (x)\ge 〈\sigma ,A(x^k-x)〉$$

(4.2)

for any $(x,\sigma )=(x^n,{\sigma }^n)$ and $(x^{\ast },{\sigma }^{\ast })$ holds.

Proof By the optimality conditions, we get

$$0\in \partial \phi \left(x^n\right)-A^T{\sigma }^{n-1}-\lambda A^T(b-A{x}^n).$$

From the second term of (2.9), we obtain

$$A^T{\sigma }^n\in \partial \phi \left(x^n\right).$$

(4.3)

By the definition of subdifferential, we have

$$\phi \left(x^k\right)\ge \phi \left(x^n\right)+〈{\sigma }^n,A(x^k-x^n)〉.$$

So (4.1) holds for $(x,\sigma )=(x^n,{\sigma }^n)$. Owing to the fact that $(x^{\ast },{\sigma }^{\ast })$ of (4.1) satisfies the KKT condition, it is easy to obtain

$$0\in \partial \phi \left(x^{\ast }\right)-A^T{\sigma }^{\ast }\text{and}A{x}^{\ast }=b.$$

Compared with (4.3), inequality (4.2) holds for $(x,\sigma )=(x^{\ast },{\sigma }^{\ast })$, which completes the proof. □

Lemma 4.2 Let $(x^k,{\sigma }^k)$ be generated by the augmented Lagrangian iterative scheme (2.9). For any $(x,\sigma )$, the inequality

$$L(x^k,{\sigma }^k)-L(x,\sigma )\ge \frac{1}{\lambda }{\parallel {\sigma }^k-{\sigma }^{k-1}\parallel }_2^2-\frac{1}{\lambda }〈{\sigma }^{k-1}-\sigma ,{\sigma }^{k-1}-{\sigma }^k〉$$

(4.4)

holds.

Proof By the definition of the Lagrangian function and Lemma 4.1, we get the following result:

$$\begin{array}{rcl}L(x^k,{\sigma }^k)-L(x,\sigma )& =& \phi \left(x^k\right)-\phi (x)-〈\sigma ,b-Ax〉+〈{\sigma }^k,b-A{x}^k〉\\ \ge & 〈\sigma ,A(x^k-x)〉-〈\sigma ,b-Ax〉+〈{\sigma }^k,b-A{x}^k〉\\ =& 〈{\sigma }^k-\sigma ,b-A{x}^k〉\\ =& \frac{1}{\lambda }〈\sigma -{\sigma }^k,{\sigma }^k-{\sigma }^{k-1}〉\\ =& \frac{1}{\lambda }{\parallel {\sigma }^k-{\sigma }^{k-1}\parallel }_2^2-\frac{1}{\lambda }〈{\sigma }^{k-1}-\sigma ,{\sigma }^{k-1}-{\sigma }^k〉.\end{array}$$

The second inequality is derived from (4.2), and the third equality is from (2.9). □

From the fact that $A^T{\sigma }^k\in \partial \phi (x^k)$, $A^T{\sigma }^{\ast }\in \partial \phi (x^{\ast })$, and the definition of subdifferential, we have

$$\phi \left(x^{\ast }\right)\ge \phi \left(x^k\right)+〈{\sigma }^n,A(x^{\ast }-x^n)〉,$$

then

$$\phi \left(x^{\ast }\right)-〈{\sigma }^{\ast },A{x}^{\ast }-b〉\ge \phi \left(x^k\right)-〈{\sigma }^n,A{x}^n-b〉,$$

thus

$$L(x^{\ast },{\sigma }^{\ast })\ge L(x^k,{\sigma }^k),$$

(4.5)

where we exploit the fact that $A{x}^{\ast }=b$.

Lemma 4.3 Let $(x^k,{\sigma }^k)$ be generated by the augmented Lagrangian iterative scheme (2.9), then

$${\parallel {\sigma }^k-{\sigma }^{\ast }\parallel }_2^2\ge {\parallel {\sigma }^{k-1}-{\sigma }^{\ast }\parallel }_2^2-{\parallel {\sigma }^k-{\sigma }^{k-1}\parallel }_2^2-2\lambda (L(x^{\ast },{\sigma }^{\ast })-L(x^k,{\sigma }^k)).$$

Proof Considering (4.4) and replacing $(x,\sigma )$ with $(x^{\ast },{\sigma }^{\ast })$, we get

$$\begin{array}{rcl}{\parallel {\sigma }^k-{\sigma }^{\ast }\parallel }_2^2& =& {\parallel {\sigma }^k-{\sigma }^{k-1}+{\sigma }^{k-1}-{\sigma }^{\ast }\parallel }_2^2\\ =& {\parallel {\sigma }^k-{\sigma }^{k-1}\parallel }_2^2+2〈{\sigma }^k-{\sigma }^{k-1},{\sigma }^{k-1}-{\sigma }^{\ast }〉+{\parallel {\sigma }^{k-1}-{\sigma }^{\ast }\parallel }_2^2\\ \le & {\parallel {\sigma }^k-{\sigma }^{k-1}\parallel }_2^2+{\parallel {\sigma }^{k-1}-{\sigma }^{\ast }\parallel }_2^2\\ -2{\parallel {\sigma }^k-{\sigma }^{k-1}\parallel }_2^2-2\lambda (L(x^{\ast },{\sigma }^{\ast })-L(x^k,{\sigma }^k))\\ =& {\parallel {\sigma }^{k-1}-{\sigma }^{\ast }\parallel }_2^2-{\parallel {\sigma }^k-{\sigma }^{k-1}\parallel }_2^2-2\lambda (L(x^{\ast },{\sigma }^{\ast })-L(x^k,{\sigma }^k)),\end{array}$$

which completes the proof. □

Moreover, ${\parallel {\sigma }^k-{\sigma }^{\ast }\parallel }_2^2\le {\parallel {\sigma }^{k-1}-{\sigma }^{\ast }\parallel }_2^2-{\parallel {\sigma }^k-{\sigma }^{k-1}\parallel }_2^2$ holds due to (4.5), this implies the global convergence of (2.9). By summing the above inequality over $k=1,2,\dots ,n$, we get

$$\sum _{k=1}^n{\parallel {\sigma }^k-{\sigma }^{k-1}\parallel }_2^2\le {\parallel {\sigma }^1-{\sigma }^{\ast }\parallel }_2^2.$$

(4.6)

Hence,

$$\underset{k\to \mathrm{\infty }}{lim}{\parallel {\sigma }^k-{\sigma }^{k-1}\parallel }_2^2=0.$$

(4.7)

Theorem 4.4 Let $(x^k,{\sigma }^k)$ be generated by the augmented Lagrangian iterative scheme (2.9), then $L(x^{\ast },{\sigma }^{\ast })-L(x^k,{\sigma }^k)=O(\frac{1}{k})$.

Proof Noting (4.4) of Lemma 4.2 and substituting $(x^{n-1},{\sigma }^{n-1})$ for $(x,\sigma )$, we get

$$L(x^n,{\sigma }^n)-L(x^{n-1},{\sigma }^{n-1})\ge \frac{1}{\lambda }{\parallel {\sigma }^n-{\sigma }^{n-1}\parallel }_2^2.$$

(4.8)

By multiplying with $n-1$ and summing it over $n=1,\dots ,k$, we obtain

$$\begin{array}{c}\sum _{n=1}^k\{(n-1)L(x^n,{\sigma }^n)-(n-1)L(x^{n-1},{\sigma }^{n-1})\}\hfill \\ =\sum _{n=1}^k\{nL(x^n,{\sigma }^n)-(n-1)L(x^{n-1},{\sigma }^{n-1})-L(x^n,{\sigma }^n)\}\hfill \\ =kL(x^k,{\sigma }^k)-\sum _{k=1}^{n}L(x^n,{\sigma }^n)\hfill \\ \ge \sum _{n=1}^k\frac{n-1}{\lambda }{\parallel {\sigma }^n-{\sigma }^{n-1}\parallel }_2^2\ge 0.\hfill \end{array}$$

From the above inequality, we have

$$\sum _{n=1}^{k}L(x^n,{\sigma }^n)\le kL(x^k,{\sigma }^k).$$

(4.9)

On the other hand, it follows from Lemma 4.3 that

$$L(x^{\ast },{\sigma }^{\ast })-L(x^n,{\sigma }^n)\le \frac{1}{2\lambda }({\parallel {\sigma }^{n-1}-{\sigma }^{\ast }\parallel }_2^2-{\parallel {\sigma }^n-{\sigma }^{n-1}\parallel }_2^2-{\parallel {\sigma }^n-{\sigma }^{\ast }\parallel }_2^2).$$

Summing the inequality over $n=1,\dots ,k$, we obtain

$$\begin{array}{c}\sum _{n=1}^k(L(x^{\ast },{\sigma }^{\ast })-L(x^n,{\sigma }^n))\hfill \\ =-\sum _{n=1}^{k}L(x^n,{\sigma }^n)+nL(x^{\ast },{\sigma }^{\ast })\hfill \\ \le \frac{1}{2\lambda }\sum _{n=1}^k({\parallel {\sigma }^{n-1}-{\sigma }^{\ast }\parallel }_2^2-{\parallel {\sigma }^n-{\sigma }^{\ast }\parallel }_2^2-{\parallel {\sigma }^n-{\sigma }^{n-1}\parallel }_2^2)\hfill \\ =\frac{1}{2\lambda }({\parallel {\sigma }^0-{\sigma }^{\ast }\parallel }_2^2-{\parallel {\sigma }^k-{\sigma }^{\ast }\parallel }_2^2-\sum _{n=1}^k{\parallel {\sigma }^n-{\sigma }^{n-1}\parallel }_2^2).\hfill \end{array}$$

(4.10)

Combining (4.9) with (4.10), we get

$$\begin{array}{rcl}-kL(x^k,{\sigma }^k)+kL(x^{\ast },{\sigma }^{\ast })& \le & -\sum _{n=1}^{k}L(x^n,{\sigma }^n)+kL(x^{\ast },{\sigma }^{\ast })\\ \le & \frac{1}{2\lambda }({\parallel {\sigma }^0-{\sigma }^{\ast }\parallel }_2^2-{\parallel {\sigma }^k-{\sigma }^{\ast }\parallel }_2^2-\sum _{n=1}^k{\parallel {\sigma }^n-{\sigma }^{n-1}\parallel }_2^2)\\ \le & \frac{1}{2\lambda }{\parallel {\sigma }^0-{\sigma }^{\ast }\parallel }_2^2.\end{array}$$

Consequently, we obtain

$$L(x^{\ast },{\sigma }^{\ast })-L(x^k,{\sigma }^k)\le \frac{1}{2k\lambda }{\parallel {\sigma }^{\ast }-{\sigma }^0\parallel }_2^2=O\left(\frac{1}{k}\right).$$

This completes the proof. □

Comparing (2.9) with (3.5), we have the following two lemmas by replacing $(x^k,{\sigma }^k)$ with $(x^k,{\tilde{\sigma }}^k)$.

Lemma 4.5 Let $(x^k,{\tilde{\sigma }}^k)$ be generated by the augmented Lagrangian iterative scheme (3.5). For any $(x,\sigma )$, we have the inequality

$$L(x^k,{\tilde{\sigma }}^k)-L(x,\sigma )\ge \frac{1}{\lambda }{\parallel {\tilde{\sigma }}^k-{\sigma }^{k-1}\parallel }_2^2-\frac{1}{\lambda }〈{\sigma }^{k-1}-\sigma ,{\sigma }^{k-1}-{\tilde{\sigma }}^k〉.$$

(4.11)

Lemma 4.6 Let $(x^k,{\tilde{\sigma }}^k)$ be generated by the augmented Lagrangian iterative scheme (3.5), then

$${\parallel {\tilde{\sigma }}^k-{\sigma }^{\ast }\parallel }_2^2\ge {\parallel {\sigma }^{k-1}-{\sigma }^{\ast }\parallel }_2^2-{\parallel {\tilde{\sigma }}^k-{\sigma }^{k-1}\parallel }_2^2-2\lambda (L(x^{\ast },{\sigma }^{\ast })-L(x^k,{\tilde{\sigma }}^k)).$$

(4.12)

Theorem 4.7 Let $(x^k,{\tilde{\sigma }}^k)$ be generated by the augmented Lagrangian iterative scheme (3.5), then

$$L(x^{\ast },{\sigma }^{\ast })-L(x^k,{\tilde{\sigma }}^k)=O(1/{(k+1)}^2).$$

Proof We work from step 4 of Algorithm 3.4, i.e., $t_{k+1}=\frac{1}{3}(\sqrt{1+9t_k^2}+1)$, where $t_0=1$. By a simple calculation, we have

$$t_{k+1}(3t_{k+1}-2)=3t_k^2$$

(4.13)

and

$$t_k\ge \frac{k+2}{3}.$$

(4.14)

Based on Lemma 4.5, by replacing $(x,\sigma )$ with $(x^{n-1},{\tilde{\sigma }}^{n-1})$ and $(x^{\ast },{\sigma }^{\ast })$, setting $k=n$, we get the two inequalities

$$w_{n-1}-w_n\ge \frac{1}{\lambda }{\parallel {\tilde{\sigma }}^n-{\sigma }^{n-1}\parallel }_2^2-\frac{1}{\lambda }〈{\sigma }^{n-1}-{\tilde{\sigma }}^{n-1},{\sigma }^{n-1}-{\tilde{\sigma }}^n〉,$$

(4.15)

$$-w_n\ge \frac{1}{\lambda }{\parallel {\tilde{\sigma }}^n-{\sigma }^{n-1}\parallel }_2^2-\frac{1}{\lambda }〈{\sigma }^{n-1}-{\sigma }^{\ast },{\sigma }^{n-1}-{\tilde{\sigma }}^n〉,$$

(4.16)

where

$$w_n:=L(x^{\ast },{\sigma }^{\ast })-L(x^n,{\tilde{\sigma }}^n).$$

By multiplying both sides of (4.15), (4.16) with $3t_n-2$ and 2, respectively, and adding the two sides, we obtain

$$\begin{array}{c}(3t_n-2)w_n-3t_n{w}_{n+1}\hfill \\ \ge \frac{3t_n}{\lambda }{\parallel {\tilde{\sigma }}^n-{\sigma }^{n-1}\parallel }_2^2+\frac{1}{\lambda }〈2{\sigma }^{\ast }+(3t_n-2){\tilde{\sigma }}^{n-1}-3t_n{\sigma }^{n-1},{\sigma }^{n-1}-{\tilde{\sigma }}^n〉.\hfill \end{array}$$

(4.17)

For the sake of convenience, we denote

$$P_n:=2{\sigma }^{\ast }+(3t_n-2){\tilde{\sigma }}^{n-1}-4t_n{\tilde{\sigma }}^n+t_n{\sigma }^{n-1}$$

and

$$Q_n:=2{\sigma }^{\ast }+(3t_n-2){\tilde{\sigma }}^{n-1}-2t_n{\tilde{\sigma }}^n-t_n{\sigma }^{n-1}.$$

By multiplying both sides of (4.17) with $t_n$, we have

$$\begin{array}{c}{t}_n(3t_n-2)w_n-3t_n^2{w}_{n+1}\hfill \\ \ge \frac{3}{\lambda }{\parallel t_n({\tilde{\sigma }}^n-{\sigma }^{n-1})\parallel }_2^2\hfill \\ +\frac{1}{\lambda }〈2{\sigma }^{\ast }+(3t_n-2){\tilde{\sigma }}^{n-1}-3t_n{\sigma }^{n-1},t_n({\sigma }^{n-1}-{\tilde{\sigma }}^n)〉\hfill \\ =\frac{1}{\lambda }〈2{\sigma }^{\ast }+(3t_n-2){\tilde{\sigma }}^{n-1}-3t_n{\tilde{\sigma }}^n,t_n({\sigma }^{n-1}-{\tilde{\sigma }}^n)〉\hfill \\ =\frac{1}{4\lambda }{\parallel 2{\sigma }^{\ast }+(3t_n-2){\tilde{\sigma }}^{n-1}-4t_n{\tilde{\sigma }}^n+t_n{\sigma }^{n-1}\parallel }_2^2\hfill \\ -\frac{1}{4\lambda }{\parallel 2{\sigma }^{\ast }+(3t_n-2){\tilde{\sigma }}^{n-1}-2t_n{\tilde{\sigma }}^n-t_n{\sigma }^{n-1}\parallel }_2^2\hfill \\ =\frac{1}{4\lambda }{\parallel P_n\parallel }_2^2-\frac{1}{4\lambda }{\parallel Q_n\parallel }_2^2,\hfill \end{array}$$

where the second equality is derived from the fact that ${\parallel \alpha +\beta \parallel }_2^2-{\parallel \alpha -\beta \parallel }_2^2=4〈\alpha ,\beta 〉$.

Then we have

$$\begin{array}{rcl}{P}_n-Q_n& =& [2{\sigma }^{\ast }+(3t_n-2){\tilde{\sigma }}^{n-1}-4t_n{\tilde{\sigma }}^n+t_n{\sigma }^{n-1}]\\ -[2{\sigma }^{\ast }+(3t_n-2){\tilde{\sigma }}^{n-1}-2t_n{\tilde{\sigma }}^n-t_n{\sigma }^{n-1}]\\ =& 2t_n{\sigma }^{n-1}-2t_n{\tilde{\sigma }}^n\\ =& 2t_n{\sigma }^{n-1}-2t_n\frac{t_{n+1}{\sigma }^n-(1-2t_n){\sigma }^{n-1}}{t_{n+1}+2t_n-1}\\ =:& K_1({\sigma }^{n-1}-{\sigma }^n),\end{array}$$

where

$$K_1:=\frac{2t_n{t}_{n+1}}{t_{n+1}+2t_n-1},$$

and the third equality is from the third iterative scheme of (3.5) and we make a transposition to the third term. Thus,

$$\begin{array}{rcl}3t_{n-1}{w}_n-3t_n^2{w}_{n+1}& \ge & \frac{1}{4\lambda }{\parallel P_n\parallel }_2^2-\frac{1}{4\lambda }{\parallel P_n-(P_n-Q_n)\parallel }_2^2\\ \ge & \frac{1}{4\lambda }{\parallel P_n\parallel }_2^2-\frac{1}{4\lambda }({\parallel P_n\parallel }^2+{\parallel P_n-Q_n\parallel }_2^2)\\ \ge & -\frac{1}{4\lambda }{\parallel P_n-Q_n\parallel }_2^2\\ :=& -\frac{K_1}{4\lambda }{\parallel {\sigma }^{n-1}-{\sigma }^n\parallel }_2^2.\end{array}$$

Summing the inequality over $n=1,\dots ,k$, we get

$$3t_0^2{w}_1-3t_k^2{w}_{k+1}\ge -\sum _{n=1}^k\frac{K_1}{4\lambda }{\parallel {\sigma }^{n-1}-{\sigma }^n\parallel }_2^2.$$

(4.18)

Then, combining (4.7), (4.14) with (4.18), we have

$$\begin{array}{rcl}{w}_{k+1}& \le & \frac{3t_0^2{w}_1+{\sum }_{n=1}^k\frac{K_1}{4\lambda }{\parallel {\sigma }^{n-1}-{\sigma }^n\parallel }_2^2}{3t_k^2}\\ \le & \frac{9t_0^2{w}_1+3\epsilon }{{(k+2)}^2},\end{array}$$

as k tends to infinity, where ε is an arbitrarily small positive number. Hence,

$$L(x^{\ast },{\sigma }^{\ast })-L(x^k,{\tilde{\sigma }}^k)=O(1/{(k+1)}^2).$$

Thus, we complete the convergence proof. □

Remark The right formula of (4.18) exploits the fact that the choice of the penalty factor λ can be seen as a monotonically increasing sequence (such as ${\lambda }_k$) that depends on the selection of $t_k$ in Algorithm 3.4. In this way, we are not only able to guarantee the convergence in the formula of $K_1$ divided by ${\lambda }_k$, but also to play a critical role of punishment to the constraint condition.

5 Conclusion

In this paper, we put forward the modified accelerated Bregman method (MABM) for solving the regularized basis pursuit problem. We give some beneficial improvement tasks on the basis of some recent literature on the accelerated Bregman method, and we perform the theoretical feasibility analysis in detail. It can be showed that the proposed MABM has a rapid convergence rate of $O(1/{(k+1)}^2)$. We will devote our future study to combining the advantages of LBM with our MABM as regards theory and numerical results.