1 Introduction

In this paper,we consider the well-known basis pursuit denoise (BPDN) problem ^[1] , minimize kxk

where A is a given M × N matrix,b ∈ ^M is an observed vector,x ∈ ^N is an unknown vector,and δ > 0 is a parameter reflecting the noise level. This problem arises from many applications,such as quantum mechanics ^[1] and compressed sensing ^[2,3] ,and has a quite long research history. We suggest that the interested readers refer to the original papers ^[2,3] for better understanding. Recently,sparse recovery and compressed sensing,which were led by Cand`es et al. ^[4,5] ,Donoho ^[6] ,Yin et al. ^[7] ,Cai et al. ^[8] ,and Osher et al. ^[9] ,are greatly boosting the research of solving the BPDN problem efficiently when the required size of problem is very large. In the literature,the most famous way to turn the constrained optimization (1) into an unconstrained version is the penalty method,by which the BPDN problem becomes min where µ > 0 is the penalty parameter. Although the unconstrained optimization (2) is a convex programming which can be solved based on its first-order optimality condition and by the fixed point iteration method ^[10] ,the penalty parameter is unknown and needs to be carefully chosen for fast convergence. In this paper,by studying the primal-dual relationship of the problem (1) under the Lagrangian dual analysis framework,we derive a new first-order optimality condition for the BPDN problem. This condition provides a new approach to choose the penalty parameters adaptively in the fixed point iteration algorithm. Meanwhile,we extend this result to matrix completion ^{[11,12,13,14,15]} which is a new field on the heel of the compressed sensing. The numerical experiments of sparse vector recovery and low-rank matrix completion show validity of the theoretic results. 2 Main results

We begin by introducing some notations used throughout the paper. The l1,l2 ,and l∞ norms of a vector x are denoted by respectively. Define the signum multifunction of a scalar t ∈ as

Then,for a vector x ∈ ⁿ and its sub-differential,we have SGN(x)

In order not to burden the presentation with too much details,we sometimes shall not explicitly mention the dimensions of variables when without confusion. To build the first-order optimality condition,we need to build two lemmas firstly.

Lemma 1 For every fixed parameter λ > 0,there holds

and Proof We only prove the first statement. The second one can be validated with the similar arguments. Denote f (u,x) = hu,xi − λkxk 1. We need to show that for every fixed vector u satisfying ||u||_∞ 6 λ,it holds . In fact,by the Cauchy-Schwartz inequality, we have hu,xi 6 kuk∞kxk 1. Thus,f (u,x) 6 (kuk∞ − λ)kxk 1 ,which implies . Moreover,we have f (u,0) = 0. Therefore,.

Lemma 2 The dual problem of BPDN is

Proof By introducing an auxiliary variable r,we can rewrite the BPDN problem in the following equivalent form:

Note that

Therefore,the BPDN problem can be equivalently written as a minimax problem,that is, By the well-known inequality of convex function ,we can deduce the primal-dual relationship ^[16] for (7) as follows: To maximize the objective function in (10),we have to impose a constrained condition on the variable y from Lemma 1 and avoid the case of taking the value of −∞. More clearly,the variable needs to satisfy such that Therefore,the objective function in (10) becomes b T_y − λσ,which completes the proof.

Now,we can establish our main results as follows.

Theorem 1 For every fixed parameter σ > 0,any solution x^* to the BPDN problem satisfies the following necessary conditions:

with

Proof Let x^* be a solution to the BPDN problem and y^* be the dual solution,i.e.,solution to the problem (6). Then,from the preceding arguments,they must satisfy the firstorder optimality conditions of (11) and (12),i.e.,0 There holds

Together with 0 ∈ AT_y−SGN(x^* ),we have Denote By the Slater condition ^[17,18] ,there is no duality gap between the primal problem (7) and its problem (6). Therefore,we have Thus,it holds Canceling the variable y^* by (14) and (17),we get or equivalently Substituting this expression into (15) and canceling the factor ||Ax^* − b||₂,we finish the proof of this theorem.

Now,let us extend this result to the matrix completion with noise (MCN) ^[11]

which is on the heel of compressed sensing. Before stating a similar result for the MCN,we need three types of norm of a matrix with its singular values {σ_k }. The spectral norm is denoted by kXk and is the largest singular value of X. The Euclidean inner product between two matrices is hX,Y i := trace(X^* Y ). The corresponding Euclidean norm is called the Frobenius norm and denoted by ,that is,=. The nuclear norm is denoted by and is the sum of singular values. With these notations,we have the following theorem.

Theorem 2 For every fixed parameter σ > 0,any solution X^* to the MCN problem satisfies the following necessary condition:

with

Proof The proof is similar to that of Theorem 1. 3 Adaptive algorithm 3.1 Fixed point iteration algorithm

The fixed point iteration was proposed in Ref. ^[10] for the unconstrained minimization (2). The idea behind this iteration is an operator splitting technique. Here,we briefly introduce this iteration for (2). Let us first focus on the first-order necessary condition of (2). Denote y = x − τA^T(Ax − b). Then,the condition is equivalent to

for any τ > 0. Note that (22) is a necessary condition for a variable to be an optimality solution to the following convex problem: with v = τ/µ. This problem has a closed form optimal solution given by x = s_v (y),where s_v (y) is the shrinkage operator given by Thus,the fixed point iteration for (2) is We list the fixed point continuation (FPC) algorithm for (1) as Algorithm 1. Algorithm 1 FPC algorithm

Step (i) Given x⁰,µ > 0,select µ₁ < µ₂ < · · · < µ_L = µ.

Step (ii) Select τ ,and set v = τ/µ_i and x⁰ = x_i−1.

Step (iii) Compute y^k+1 and x^k+1 by the iteration formula (25).

Step (iv) Terminate if the stopping criterion is satisfied.

Step (v) Output x_i. 3.2 Adaptively fixed point (AFP) iteration algorithm

The continuous technique was adopted in the fixed point iteration algorithm for increasing the penalty parameter µ in Ref. ^[10] for sparse vector recovery,that is,µ_i+1 = min{µ_i η_µ,µ},i =1,2,· · ·,L−1. This updated rule is simple. The penalty parameter at next step is obtained by multiplying a fixed constant η_µ,which is determined by the researchers subjectively,at each outloop. Here,by the first-order optimality condition (13),we design a dynamically updated rule described as follows:

Here,the only difference with the old updated rule lies in that the penalty factor µi η_µ at each outloop has been replaced by µ(x_i ) which arises in the new first-order optimality condition. Notice that both the numerator and denominator of µ(x_i) decrease as x_i tends to the true solution. We modify the dynamically updated rule as ,where R is an approximation of the 1-norm of the true solution.

We list the AFP iteration algorithm for (1) as Algorithm 2. Algorithm 2 AFP iteration algorithm

Step (i) x⁰,µ > 0 and the constant R are given as the initial condition.

Step (ii) Compute µi by the updated formula (26).

Step (iii) Select τ ,and set v = τ/µ_i and x⁰ = x_i−1.

Step (iv) Compute y^k+1 and x^k+1 by the iteration formula (25).

Step (v) Terminate if the stopping criterion is satisfied.

Step (vi) Output x_i.

Finally,we extend this type of algorithm to the MCN. In order to derive a similar iteration, one only needs to know that the following convex problem:

also has a closed form optimal solution ^[19,20,21] ,which is X = Sv (y),where Sv (y) is the matrix shrinkage operator defined as follows. Given a matrix Y and its reduced singular value decomposition (SVD) given by Y = U diag()V^T,Sv (Y ) = U diag()V^T with σ = s_v (σ). Thus,the fixed point iteration for the corresponding unconstrained version of (20) is The remainder computing procedure for the MCN is the same as that for the BPDN problem. 4 Numerical experiments

In this part,two simulation experiments are tested to show the potential of the dynamically updated rule. One is the sparse vector recovery,and the other is the matrix completion problem. The codes of the FPC algorithm for the sparse vector recovery and the matrix completion problem are available. Here,we take comparison between the FPC algorithm and the proposed AFP algorithm. All the simulations are conducted and timed on a personal computer with an Intel Pentium-IV CPU 3.06 GHZ and 512 MB memory,running in MA TLAB (version 7.01). In the first experiment,we test two different scales,1 024 and 2 048,with different η_µ . The other parameters are referred to Ref. ^[22]. From Table 1,one can see that different values of η_µ have great effects on the CPU time,and our method is comparable to the best result among them. In the modified dynamically updated rule,we need to estimate the 1-norm of the true solution x^* . If it is known,we take . Otherwise,we set R = 10³ for sparse vector recovery and R = 10⁴ for matrix completion in our simulations.

In the second experiment,we use the default value of η_µ = 2.0. The scalars,the ranks,the stop rules,the setting of µ,and the sampling ratios are referred to Ref. ^[20]. We create random matrices M ∈ ^n×m with rank r by the following procedures. We firstly generate random matrices ML ∈ ^n×r and MR ∈ ^m×r with independent and identically distributed Guassian entries through the MATLAB function randn(·),and then set M = MLM^*_R . We sample a subset Ω through the MATLAB function randsample(·),and the sampled number is cardinality of Ω,denoted by |Ω|. We test the noiseless case and the noisy case,respectively . In the noisy case,we corrupt the observations P_Ω (M ) by noise as the following model:

where Z is a zero-mean Gaussian white noise with standard deviation σ. The quantities of noise are controlled by the noise ratio (r_n ) defined by We set the noise ratio r_n = 0.01 for noise matrix completion. The relative error e_r is defined by In our numerical test,we repeat the experiment 100 times and report the average computational time and error to compare them. Table 2 and Table 3 are for the noiseless case and the noisy case,respectively. It can be seen that the CPU time has been reduced obviously,while the error has little change. 5 Conclusions

Under the Lagrangian dual analysis framework,we derive a new first-order optimality condition for the BPDN problem. Such a condition provides us with a new approach to choose the penalty parameter adaptively in the fixed point iteration algorithm. Meanwhile,we extend this result to matrix completion. Finally,numerical experiments show validity of the theoretic results.