A linearly convergent proximal ADMM with new iterative format for BPDN in compressed sensing problem

1.   Introduction

Compressive sensing (CS) problem is to recover a sparse signal $\bar{x}$ from an undetermined linear system $A\bar{x} = b$, where $\bar{x}\in\mathcal{R}^n$, $A$ is the sensing matrix and $A\in\mathcal{R}^{m\times n}$ ($m\ll n$), $b$ is the observed signal and $b\in\mathcal{R}^m$. A fundamental decoding model of CS problem is the following basis pursuit denoising (termed as BPDN) problem:

where $\mu\; (>0)$ is a parameter, and the norm $\|\cdot\|_1$ and $\|\cdot\|_2$ denote the Euclidean 1-norm and 2-norm, respectively.

Recently, a lot of numerical algorithms about BPDN problem have been extensively developed. In fact, the BPDN problem can be equivalently converted into a separable convex programming by introducing auxiliary variable. Thus the numerical methods, which can be used to solve the separable convex programming, are applicable to BPDN problem, such as the alternating direction method of multipliers and its linearized version ^[1,2,3,4], the Peaceman-Rachford splitting method (PRSM) or Douglas-Rachford splitting method (DRSM) of multipliers ^[5,6,7,8], the symmetric alternating direction method of multipliers ^[9], etc. Yang and Zhang ^[1] investigate the use of alternating direction algorithms for several $\ell_1$-norm minimization problems arising from sparse solution recovery in CS, including the basis pursuit problem, the basis-pursuit denoising problems, and so on. Yuan ^[2] presents a descent-like method, which can obtain a descent direction and an appropriate step size and improve the proximal alternating direction method. Yu et al. ^[5] apply the primal DRSM to solve equivalent transformation form of BPDN problem. He and Dan ^[6] furtherly study the multi-block separable convex minimization problem with linear constraints along the way by the primal application of DRSM, and present the exact and inexact versions of the new method in a unified framework. Compared to the DRSM, the PRSM requires more restrictive assumptions to ensure its convergence, while it is always faster whenever it is convergent. He and Liu et al.^[7] illustrate the reason for this difference, and develop a modified PRSM for separable convex programming, which includes BPDN problem as a special case. Sun and Liu ^[8] develop a generalized PRSM for BPDN problem, of which both subproblems are approximated by the linearization technique. He et al. ^[9] obtain the convergence of the symmetric version of ADMM with step sizes, where step sizes can be enlarged by Fortin and Glowinski's constant. On the other hand, BPDN problem can be equivalently transformed into an equation or variational inequality problem by splitting technique ^{[10,11,12,13,14,15]}, which can be solved by some standard methods such as conjugate gradient methods, proximal point algorithms and projection-type algorithms. Xiao and Zhu ^[10] transform BPDN problem into a convex constrained monotone equation, and present a conjugate gradient method for the equivalent form of the problem. Sun and Tian ^[11] propose a class of derivative-free conjugate gradient (CG) projection methods for nonsmooth equations with convex constraints, including the BPDN problem. Sun et al. ^[12] reformulate BPDN problem as variational inequality problem by splitting the decision variable into two nonnegative auxiliary variables, and propose a novel inverse matrix-free proximal point algorithm for BPDN problem. Base on the same transformation of BPDN problem, Feng and Wang ^[13] also propose a projection-type algorithm without any backtracking line search. Although there are so many ways to solve the problem, it is still needed to improve the solving speed and accuracy. In particular, as the dimension increases greatly, the solving speed and accuracy are adversely affected. In the paper, we will establish a new iterative format of proximal ADMM, which has closed-form solutions. The motivation behind this is for the better numerical performance when the dimension increases. Furthermore, the linear rate convergence result for new algorithm is established, which is also one of the most important motivations.

The rest of this paper is organized as follows. In Section 2, some equivalent reformulations of (1.1) and related theories of (1.1), which are the basis of our analysis, are given. In Section 3, basing on a special iterative format, we present a new type proximal ADMM, in which the corresponding subproblems have closed-form solutions. The global convergence of new method is discussed in detail. We establish a $R-$linear rate convergence theorem under suitable condition. In Section 4, some numerical experiments on sparse signal recovery are given, and we compare the CPU time and the relative error among the Peaceman-Rachford splitting method of multipliers^[8], the conjugate gradient methods^[11], the proximal point algorithms^[12], the projection-type algorithms^[13] and our algorithm, and show that our algorithm is more accurate and efficient than other algorithms. Finally, some conclusive remarks are drawn in the last section.

We end this section with some notations used in this paper. Vectors considered in this paper are all taken in Euclidean space equipped with the standard inner product. The notation $\mathcal{R}^{m\times n}$ stands for the set of all $m\times n$ real matrices. For $x, y\in \mathcal{R}^n,$ we use $(x; y)$ to denote the column vector $(x^\top, y^\top)^\top$. If $G\in\mathcal{R}^{n\times n}$ is a symmetric positive definite matrix, we denote by $\|x\|_G = \sqrt{x^\top Gx}$ the $G$-norm of the vector $x$.

2.   Equivalent reformulations of BPDN problem and preliminaries

2.1.   Equivalent reformulations of BPDN problem

In this section, we first establish some equivalent reformulations to the BPDN problem via some the related optimality theories.

It is obvious that the BPDN problem can be equivalently reformulated as the following optimization problem ^[8]

Then the augmented Lagrangian function of the convex programming ($2.1$) can be written as

where $\lambda$ is the Lagrangian multiplier for the linear constraints of ($2.1$) and $\lambda\in\mathcal{R}^n$,

By invoking the first-order optimality condition for convex programming, we can equivalently reformulate problem (2.1) as the following variational inequality problem: finding vector $x^* = ({x}_1^*; {x}_2^*)\in\mathcal{R}^{n}\times\mathcal{R}^{n}$ and $\lambda^*\in\mathcal{R}^n$ such that

Obviously, the system ($2.3$) is equivalent to the following problem: Find a vector $w^*\in\mathcal{W}$ such that

where $w = (x_1;x_2;\lambda)\in \mathcal{W} = {\mathcal{R}^{n}\times \mathcal{R}^{n}\times \mathcal{R}^{n}}$, $\theta(x) = \theta_1(x_1)+\theta_2(x_2)$, and

We denote the solution set of (2.4) by $\mathcal{W^*}$.

It is easy to verify that the mapping $F(\cdot)$ is not only monotone but also satisfies the following nice property

2.2.   Preliminaries

To proceed, we present the following definition, which will be needed in the sequel.

Definition 2.1. For sequence vector $\mu^k = (\mu_1^k, \mu_2^k, \cdots, \mu_n^k)^\top\in\mathcal{R}^n\; (k = 1, 2, \cdots)$, we define two new functions $\psi(\mu^k)$ and $\delta(\mu^k)$.

$(i)$ The function $\psi(\mu^k) = (\psi_1(\mu_1^k), \psi_1(\mu_2^k), \cdots, \psi_1(\mu_n^k))^\top$, and

where $k$ is positive integer, and $C > 0$ is a constant.

$(ii)$ The function $\delta(\mu^k) = \mu^k-\psi(\mu^k)$.

3.   Algorithm and convergence

In this section, we present a new type proximal ADMM for solving (2.1) by a special iterative format, and the global convergence of new method is also established in detail.

Algorithm 3.1.

Step 0. Select constants $\beta, \gamma, \varepsilon > 0$, two positive semi-definite matrices $R_i\in\mathcal{R}^{n\times n}(i = 1, 2)$. Choose an arbitrarily initial point $w^0 = (x_1^0;x_2^0;\lambda^0)\in {\mathcal{R}^{n}\times \mathcal{R}^{n}\times \mathcal{R}^{n}}$. Take

Set $k = 0$.

Step 1. By current iterate $w^k$, compute the new iterate $\hat{w}^{k} = (\hat{x}_1^{k}; \hat{x}_2^{k}; \hat\lambda^{k})$ via

Step 2. If $\|w^k-\hat{w}^{k}\|\leq\varepsilon$, then stop; otherwise, go to Step 3.

Step 3. Set $w^{k+1} = \rho\hat{w}^k+(1-\rho)\psi(w^{k})$, where $\rho\in(0, \eta)$ and $\eta$ is a constant defined in (3.1). Go to Step 1.

In the following, we show that it is reasonable to use $\|w^k-\hat{w}^k\|\leq\varepsilon$ to terminate Algorithm 3.1.

Lemma 3.1. If $w^k = \hat{w}^k$, then the vector $w^k$ is a solution of (2.4).

Proof. For $x_1$-subproblem in (3.2), using the first-order optimality condition, for any $x_1\in\mathcal{R}^n$, we obtain

where the first and the second equalities are by $\lambda^{k} = \hat{\lambda}^{k}+\gamma\beta(\hat{x}_1^{k}-\hat{x}_2^k)$, i.e.,

For $x_2$-subproblem in (3.2), similar to discussion above, one has

where the first and second equalities are by $\lambda^{k} = \hat{\lambda}^{k}+\gamma\beta(\hat{x}_1^{k}-\hat{x}_2^k)$, i.e.,

For $\lambda$-subproblem in (3.2), for any $\lambda\in\mathcal{R}^n$, one has

By (3.3)–(3.5), we get

where

Combining $w^k = \hat{w}^k$ with (3.6), one has

Substituting $\hat{w}^k$ and $\hat{x}^k$ in (3.8) with $w^k$ and $x^k$, respectively, we obtain

which indicates that $w^k$ is a solution of (2.4).

Remark 3.1. From Lemma 3.1, if Algorithm 3.1 stops at Step 2, then $w^k$ is a proximal solution of (2.4).

In the following, we assume that Algorithm 3.1 generates infinite sequences $\{w^k\}$ and $\{\hat{w}^k\}$. For convenience, we define two matrices to simplify our notation in the later analysis.

The following lemma gives some interesting properties of the two matrices $M, Q$ just defined. These properties are crucial in the convergence analysis of Algorithm 3.1.

Lemma 3.2. If $R_1$ and $R_2$ are two positive semi-definite matrices, then we have

$(i)$ Both matrices $M$ and $Q$ are positive semi-definite;

$(ii)$ The matrix $H_1: = 2Q-\gamma M$ is positive semi-definite if $0 < \gamma\leq1$;

$(iii)$ The matrix $H_2: = 2\gamma Q-M$ is positive semi-definite if $\gamma > 1$.

Proof. $(i)$ For any $w = (x_1;x_2;\lambda)$, one has

So the matrix $M$ is positive semi-definite.

The matrix $Q$ can be written as

Obviously, the matrix $Q_1$ is positive semi-definite, and we have

where the first inequality is obtained by the Cauchy-Schwartz inequality, the second inequality follows from the fact that $a^2+b^2\geq2ab, \forall a, b\in \mathcal{R}_+$, and the desired result follows.

$(ii)$ For the matrix $H_1$. By a direct computation, it yields that

Obviously, by $0 < \gamma\leq1$, the first part is positive semi-definite, and

and thus the desired result follows.

$(iii)$ For the matrix $H_2$. By a direct computation, it yields that

Similar to discussion above, using $\gamma > 1$, we obtain

Combining this with the positive semi-definite of $Q_1$, and the desired result follows.

Lemma 3.3. Let $\{w^k\}$ and $\{\hat{w}^k\}$ be two sequences generated by Algorithm 3.1. Then we have

Proof. From the definitions of $M$ in (3.9) and $G$ in (3.7), one has

where $\tilde{M} = \left(\begin{array}{cccc}0 & \beta I_n & -\frac{1-\gamma}{\gamma}I_n\\0 & -\beta I_n & \frac{1-\gamma}{\gamma}I_n\\0 & 0 & 0\end{array}\right).$ By a direct computation, it yields that

where the first inequality is by (2.4) with $w^*\in\mathcal{W}^*$, $w^k\in\mathcal{W}$, since $w^*\in\mathcal{W}^*\subseteq\mathcal{W}$, using (3.6) with $x = x^*$ and $w = w^*$, we have that the second inequality holds, the third equality follows from $x_1^* = x_2^*$, and the four equality comes from the fact $(\hat{x}_1^{k}-\hat{x}_2^k) = \frac{1}{\gamma\beta}(\lambda^{k}-\hat{\lambda}^{k})$. Applying (3.11), we get

and one has

where the second equality follows from the definition of matrix $Q$ in (3.9), and the desired result follows.

Lemma 3.4. For any solution $w^* = (x_1^*; x_2^*; \lambda^*)$ of (2.4), the sequence $\{w^k\}$ generated by Algorithm 3.1 satisfies

where the matrix $H$ is defined by

and $\eta$ is defined in (3.1).

Proof. From (3.1), if $0 < \gamma\leq1$, then $\eta = \gamma$. A direct computation yields that

where the first inequality follows from (3.10), the second equality follows from $H_1 = 2Q-\gamma M$ in Lemma 3.2 $(ii)$, and the second inequality follows from the fact that the matrix $H_1$ is positive semi-definite in Lemma 3.2.

If $\gamma\geq1$, then $\eta = \frac{1}{\gamma}$. Similar to discussion (3.14), we can also obtain

where the first equality comes from $H_2 = 2\gamma Q-M$ in Lemma 3.2 $(iii)$, and the second inequality follows from the fact that the matrix $H_2$ is positive semi-definite in Lemma 3.2.

The desired result follows by combining above.

Remark 3.2. By the definition of $\eta$ in (3.1), the matrix $H$ in (3.13) is positive semi-definite.

Theorem 3.1. For any solution $w^* = (x_1^*; x_2^*; \lambda^*)$ of (2.4), the sequence $\{w^k\}$ generated by Algorithm 3.1 satisfies

Proof. Since the matrix $H$ in (3.13) is positive semi-definite, by (3.12), one has

Thus, the desired result follows.

Theorem 3.2. Assume that the matrix $R_1$ is positive definite. Then the sequence $\{w^k\}$ generated by Algorithm 3.1 converges to some $\bar{w}\in \mathcal {W}^*$.

Proof. Using Definition 2.1, there exists a constant $c_1 > 0$ such that $\|\delta(w^{k})\|_M\leq \frac{c_1}{2^k}$. Combining this with ($3.16$), we obtain

where $w^*\in \mathcal {W}^*$. Since that the matrix $R_1$ is positive definite, it is easy to obtain that the matrix $M$ is positive definite. Combining this with (3.18), we have that $\{w^k\}$ is bounded.

Now, we break up the discussion into two cases.

Case 1. If there exists a subsequence $\{w^{k_j}\}$ such that $\|w^{k_j}-w^*\|_M\leq(1-\rho)\|\delta(w^{k_j})\|_M$, i.e., $\|w^{k_j}-w^*\|\leq(1-\rho)c_1\frac{1}{2^{k_j}}$, Then $\{w^{k_j}\}$ converges to $w^*$. Since the series of positive terms $\sum_{k = 1}^\infty \frac{1}{2^k}$ is convergent, by Cauchy convergence criterion, for any $\epsilon > 0$, there exists a positive integer $m$ such that

as positive integer $k, k_j\geq m\; (k\geq k_j)$. From $\lim_{j\rightarrow \infty}w^{k_j} = w^*$, for $\epsilon > 0$ above, there exists an integer $j$, such that

Combining (3.19) with (3.20), for sufficiently large positive integer $k, k_j (k\geq k_j)$, similar to discussion (3.18), we obtain

which indicates that the sequence $\{w^k\}$ converges globally to the point $w^*$.

Case 2. For any subsequence $\{w^{k_j}\}$ such that $\|w^{k_j}-w^*\|_M > (1-\rho)\|\delta(w^{k_j})\|_M$, i.e., $\|w^{k+1}-w^*\|_M > (1-\rho)\|\delta(w^{k})\|_M$.

Since $\{w^k\}$ is bounded, there exists constant $c_2 > 0$ such that $\|w^{k+1}-w^*\|\leq c_2$. By definition of $w^{k+1}$ in Step 3 of Algorithm 3.1, we have

Combining this with ($3.12$), one has

which together with the positive definiteness of $H$ yields

and one has

By (3.23), we know that the sequence $\{\hat{w}^k\}$ is also bounded since $\{w^k\}$ is bounded. Thus, it has at least a cluster point, saying $w^\infty: = (x_1^\infty; x_2^\infty; \lambda^\infty)$, and suppose that the subsequence $\{\hat{w}^{k_i}\}$ converges to $w^\infty$. By (3.26), one has $\lim_{k_i\rightarrow \infty}\|\lambda^{k_i}-\hat{\lambda}^{k_i}\| = 0.$ Taking limits on both sides of

we have

Furthermore, taking limits on both sides of (3.3) and (3.4), and using (3.24)–(3.26), we obtain

and

Therefore, $(x_1^\infty, x_2^\infty, \lambda^\infty)\in\mathcal{W}^*$.

Since the series of positive terms $\sum_{k = 1}^\infty \frac{1}{2^k}$ is convergent, by Cauchy convergence criterion, for any $\epsilon > 0$, there exists a positive integer $m$ such that

as positive integer $k, k_l\geq m (k\geq k_l)$. By (3.23) and $\lim_{j\rightarrow \infty}{\hat{w}^{k_j}} = w^\infty$, for $\epsilon > 0$ above, there exists an integer $l$, such that

Combining (3.27) with (3.28), for sufficiently large positive integer $k, k_l (k\geq k_l)$, similar to discussion (3.18), we obtain

which indicates that the sequence $\{w^k\}$ converges globally to the point $w^\infty$. The proof is completed.

In the end of this section, we discuss the convergence rate of Algorithm 3.1. To this end, the following assumptions is needed.

Assumption 3.1. For two sequences $\{w^k\}$ and $\{\hat{w}^k\}$, assume that there exist a positive constant $\sigma$ such that, for $w^k$, there exists $w^*\in\mathcal W^{*}$ such that

where

and $\partial(\|\hat{x}^k_2\|_1)$ denotes the subdifferential of the function $\|x_2\|_1$ at the point $\hat{x}^k_2$.

Lemma 3.5. Suppose that Assumption 3.1 holds. Then there exists a positive constant $\hat{\mu}$ such that

Proof. From (3.2), we have

By (3.29) and (3.30), a direct computation yields that

where $\bar{Q} = \left(\begin{array}{ccc}A^\top A+\beta I+R_1 & 0 & 0\\ 0 & \beta I+R_2 & 0\\0 & 0 & I\end{array}\right)$. Combining this with Assumption 3.1, we obtain

Let $\hat{\mu} = \sigma\|\bar{Q}\|$. Then the desired result follows.

Theorem 3.3 Suppose that the hypothesis of Theorem 3.2 and Assumption 3.1 hold, and $\frac{3}{4}\hat{\mu}^2 < (\eta-\rho)\rho < \frac{5}{4}\hat{\mu}^2$. Then the sequence $\{w^k\}$ generated by Algorithm 3.1 converges to a solution of (2.4) $R-$linearly.

Proof. From Theorem 3.2. Without loss of generality, we assume that the sequence $\{w^k\}$ converges to $w^*\in \mathcal {W}^*$. A direct computation yields that

where the second inequality follows from the fact that $a^2+b^2\geq 2ab, \forall a, b \in R$, the third inequality is obtained by (3.12), the fourth inequality follows by Lemma 3.5, and the fifth inequality is by (3.13).

Since the sequence $\{w^k\}$ converges to $w^*$, it follows that there exists a positive integer $k_0$, for all $k\ge k_0$, we obtain the following conclusions.

If $\|w^{k}-w^*\|_M\leq2(1-\rho)\|\delta(w^{k})\|_M$. By Definition 2.1, the following holds

If $\|w^{k}-w^*\|_M > 2(1-\rho)\|\delta(w^{k})\|_M$. Combining this with (3.31), we obtain

Let $\hat{\tau} = 2(1-\frac{(\eta-\rho)\rho}{\hat{\mu}^2})+\frac{1}{2}$. Then $0 < \hat{\tau} < 1$ by $\frac{3}{4}\hat{\mu}^2 < (\eta-\rho)\rho < \frac{5}{4}\hat{\mu}^2$. Therefore, we have

where $c_2$ is positive constant, i.e., $\|w^{k}-w^*\|_M\leq c_2\sqrt{\hat{\tau}}^{-1}\sqrt{\hat{\tau}}^{k}.$ Combining this with (3.32), one has

where $c_3$ is positive constant, and thus the desired result follows.

4.   Numerical results

In this section, we provide some numerical tests about BPDN problem to show the efficiency of method proposed in this paper. All codes are written by MATLAB 9.2.0.538062 and performed on a Windows 10 PC with an AMD FX-7500 Radeon R7, 10 Computer Cores 4C+6G CPU, 2.10GHz CPU and 8GB of memory. In experiment, we set $\mu = 0.001,$ and the measurement matrix $A$ is generated by MATLAB scripts:

The original signal $\bar{x}$ is generated by ${p = randperm(n); x(p(1:k)) = randn(k, 1)}.$

To simplify calculations of (3.2), we set $R_1 = \tau I_n-A^\top A$, where $\tau > 0$ is a constant. Combining this with the first equality in (3.30), one has

where $g^k = A^\top(Ax_1^k-b)$.

For the second equality in (3.30), we set $R_2 = 0$, then

The subdifferential of the absolute value function $|t|$ is given as follows

Combining this with (4.2), for $i = 1, 2, \cdots, n$, we obtain

where $\mathrm {shrink}_{c}(\ast)$ is the soft-thresholding operator defined as

and $c > 0$ is a constant. In addition, when $k = 0$, $k/|k|$ should be taken 0. Therefore, we have the following formula to calculate $\hat{x}_2^{k}$, i.e.,

Applying (4.1) and (4.3), then (3.2) in Algorithm 3.1 can be written as follow

For any methods, the stop criterion is

where $f_k$ denotes the objective value of (1.1) at iteration $x_k$.

In each test, we calculate the relative error

where $\bar{x}$ denotes the recovery signal.

4.1.   Test on additive Gaussian white noise

In this subsection, we apply Algorithm 2.3 in ^[11] (DFCGPM), Algorithm 2 in ^[12] (IMFPPA) and Algorithms 3.1 in this paper to recover a simulated sparse signal of which observation data is corrupted by additive Gaussian white noise, respectively. We set $n = 2^{12}, m = 2^{10}, k = 2^{7},$ and some parameters about tested algorithms are listed as follows:

Algorithms 3.1: $\beta = 0.2, \mu = 0.01, \gamma = 1.9, \tau = 0.5$;

IMFPPA: $\rho = 0.01, \gamma = 0.01, \tau = 0.2$;

DFCGPM: $C = 1, r = 0, \eta = 1, \rho = 0.4, \sigma = 0.01, \gamma = 1.9.$

The original signal, the measurement and the reconstructed signal(marked by red point) by Algorithm 3.1, DFCGPM and IMPPA are given in Figure 1. Obviously, from the first, third, fourth and the last subplots in Figure 1, all elements in the original signal are circled by the red points, which indicates that the three methods can recover the original signal quite well. Furthermore, we record the number of iterations (abbreviated as Iter), the CPU time in seconds (abbreviated as CPU Time), the relative error (abbreviated as RelErr) of the three methods. Figure 1 indicates that Algorithm 3.1 have higher accuracy than IMPPA method, and Algorithm 3.1 is also always faster than DFCGPM and IMPPA methods. Thus, Algorithm 3.1 is an efficient method for sparse signal recovery.

4.2.   Compared from different k-Sparse signal ($n=2^{12}, m=2^{10}$)

In this subsection, Algorithm 3.1 proposed in this paper is compared with IMFPPA ^[12], DFCGPM ^[11], Algorithm 3.1 in ^[8] (PPRSM) and Algorithm 3.1 in ^[13] (LAPM) from the CPU Time and the RelErr, where some parameters about PPRSM and LAPM are listed as follows:

PPRSM: $\gamma = 0.2, \sigma = 0.1$;

LAPM: $\beta = 0.25, \tau = 0.6$.

All algorithms have run 5 times, respectively, and the average of the the CPU Time and the RelErr are obtained. The numerical results are listed in Table 1. From the Table 1, It is obvious that the CPU time of Algorithm 3.1 is less than other algorithms in different k-Sparse signal whether it is Free noise or Gaussian noise, which shows that Algorithm 3.1 is faster. In addition, we find that the accuracy of algorithm 3.1 are also better than other algorithms. So, Algorithm 3.1 is a more efficient method for different k-Sparse signal recovery.

4.3.   Compared with DFCGPM and IMFPPA in Different Dimensions

In this subsection, Algorithm 3.1 proposed in this paper is compared with DFCGPM ^[11] and IMFPPA ^[12] from aspects of the CPU Time and the RelErr in different dimension, where some parameters about DFCGPM and IMFPPA are given in Subsection 4.1. We set $m = \frac{n}{4}, k = \frac{n}{32}$ and no additive Gaussian white noise. All algorithms have run 5 times, respectively. The average of the CPU Time and the RelErr are obtained. Some numerical results are listed in Table 2, where the IMFPPA and DFCGPM are difficult to solve the problem in our computer when $n\geq 10,000$ since our computer configuration constraints, and it is also drawn in Figure 2. The numerical results in Table 2 and Figure 2 indicates that: The CPU Time and RelErr of Algorithm 3.1 are less than that of the other two tested methods, which shows that Algorithm 3.1 is more effective for large scale problem. Thus, Algorithm 3.1 is very suitable for solving large-scale problems.

5.   Discussion

The method proposed in this work has several possible extensions. Firstly, it could be numerically beneficial to tune the parameter, and thus it is meaningful to investigate the global convergence of the proposed method with adaptively adjusted parameter. Secondly, we may establish global error bound for (1.1) just as was done for generalized linear complementarity problem in ^[16,17,18], and may use the error bound estimation to establish quick convergence rate of the new Algorithm 3.1 for solving (1.1). This is a topic for future research.

Since the RNNM model is a convex program, we explore the possibility of the proposed algorithm developed for BPDN model to solve the RNNM model from theoretical results and numerical experiments. This will be our further research direction.

The Regularized Nuclear Norm Minimization (RNNM) model is defined as follows ^[19,20]:

where $\mu > 0$ is a parameter, $b\in R^m$ is an observed vector, $\mathcal{A}:R^{n_1\times n_2}\longrightarrow R^m$ is a known linear measurement map defined as

Here, $A^{(i)}$ for $i = 1, 2, \cdots, m$ is denoted as a matrix with size $n_1\times n_2$, and $tr(\cdot)$ is the trace function, the norm $\|\cdot\|_*$ denote the Euclidean nuclear norm.

6.   Conclusions

In this paper, by choosing a special iterative format, we have developed a new iterative format of proximal ADMM, which has closed-form solutions. Thus, it has fast solving speed and pinpoint accuracy when the dimension increases. It makes new algorithm very attractive for solving large-scale problems. The global convergence of new method is discussed in detail. Furthermore, the linear rate convergence result for new algorithm is established. Some numerical experiments on sparse signal recovery are given, and compared with the state-of-the-art of algorithms in ^[8,11,12,13], the method proposed in this paper is more accurate and efficient.

Acknowledgments

The authors wish to give their sincere thanks to the Editor-in-chief, the Associated Editor and the anonymous referees for their valuable suggestions and helpful comments which improved the presentation of the paper.

This study was funded by the Natural Science Foundation of China (Nos. 12071250, 11801309), and Shandong Provincial Natural Science Foundation (ZR2021MA088).

Conflict of interest

No potential conflict of interest was reported by the authors.