EQUIVALENCE BETWEEN NONNEGATIVE SOLUTIONS TO PARTIAL SPARSE AND WEIGHTED l1-NORM MINIMIZATIONS??

Xiuqin Tian,Zhengshan Dong,Wenxing Zhu

(Center for Discrete Math.and Theoretical Computer Science, Fuzhou University,Fuzhou 350116,Fujian,PR China)

EQUIVALENCE BETWEEN NONNEGATIVE SOLUTIONS TO PARTIAL SPARSE AND WEIGHTED l1-NORM MINIMIZATIONS??

Xiuqin Tian,Zhengshan Dong,Wenxing Zhu?

(Center for Discrete Math.and Theoretical Computer Science, Fuzhou University,Fuzhou 350116,Fujian,PR China)

Based on the range space property(RSP),the equivalent conditions between nonnegative solutions to the partial sparse and the corresponding weighted l1-norm minimization problem are studied in this paper.Different from other conditions based on the spark property,the mutual coherence,the null space property(NSP)and the restricted isometry property(RIP),the RSP-based conditions are easier to be verified.Moreover,the proposed conditions guarantee not only the strong equivalence,but also the equivalence between the two problems.First,according to the foundation of the strict complementarity theorem of linear programming,a sufficient and necessary condition, satisfying the RSP of the sensing matrix and the full column rank property of the corresponding sub-matrix,is presented for the unique nonnegative solution to the weighted l1-norm minimization problem.Then,based on this condition, the equivalence conditions between the two problems are proposed.Finally, this paper shows that the matrix with the RSP of order k can guarantee the strong equivalence of the two problems.

compressed sensing;sparse optimization;range space property;equivalent condition;l0-norm minimization;weighted l1-norm minimization

2000 Mathematics Subject Classification 94A12;15A29;90C25

Ann.of Appl.Math.

32:4(2016),380-395

1　Introduction

In this paper,we consider the following partial sparse minimization problem

where x=(x1,x2,···,xn1)T∈?n1,y∈?n2.|xi|0=0 if xi=0;otherwise|xi|0=1.wi∈R is the weight on|xi|0,i=1,2,···,n1.a∈?n2,A∈?m×n1,B∈?m×n2, and b∈?m(m ＜n1+n2)are the problem datas.Let∥x∥0be the number of nonzero components of x,that is,Although∥x∥0is not a norm,we still call it l0-norm for simplicity.

By relaxing|xi|0as|xi|,and taking into accountwe get the following linear program

where w=(w1,w2,···,wn1)T.We are interested in what conditions can ensure the equivalence of problems(1)and(2).

In recent years,l0-norm minimization problems have been widely researched, and have been successfully applied to signal processing[1],pattern recognition[2], machine learning[3],computational biology[4],medical imaging[5],and other fields [6-9].Recent research indicates that l1-norm relaxation can promote sparsity[11]. This is based on equivalence between the l0-norm and l1-norm minimization problems.

Up to now,the study of the equivalence between l0-norm and l1-norm minimization problems is mainly for the following two problems:

It has been proved that,all k-sparse solutions to problem(3)can be found by solving problem(4),if the spark of the sensing matrix A is greater than 2k[19],or the order of the null space property(NSP)[21]or the restricted isometry property(RIP)of A is 2k or above[25].However,these conditions remain restrictive and are hard to be verified.From geometric perspective,Donoho and Tanner[30]showed that the outward k-neighborliness of A could also guarantee the equivalence of problems(3) and(4).Donoho and Romberg[11]also analysed the equivalence from probabilistic perspective.

Based on the RSP,Zhao[26,27]presented equivalent conditions for problems(3) and(4),no matter whether the nonnegative constraints exist or not.The conditions guarantee not only the strong equivalence but also the equivalence between the l0-norm and l1-norm minimization problems.Moreover,Zhao presented an RSP which could be verified easily,by solving a linear programming problem[26].

In this paper,we consider the equivalence between problems(1)and(2).The definition of equivalence is similar to that in[26],which is as follows.

Definition 1.1[26](i)Problems(1)and(2)are said to be equivalent if there exists a solution to problem(1)that coincides with the unique solution to problem (2);

(ii)problems(1)and(2)are said to be strongly equivalent if the unique solution to problem(1)coincides with the unique solution to problem(2).

We consider only nonnegative solution throughout this paper.The case without nonnegative constrains can be reduced to that one,by replacing(x,y)with(x+? x?,y+?y?),whereMoreover,when there exist inequality constraints,by introducing slack variables,they can be written as the form of(1).Some more details can refer to Section 5.

The rest of this paper is organized as follows.Section 2 shows the existence of the unique nonnegative solution to the weighted l1-norm minimization problem(2). The equivalent and strongly equivalent conditions are described in Sections 3 and 4 respectively.In Section 5,we present several variants of problem(1).Conclusions are given in Section 6.

2　Uniqueness of Weighted l1-norm Minimization

From Definition 1.1,the existence of a unique solution to the weighted l1-norm minimization problem(2)is necessary for the equivalence between the partial sparse and the weighted l1-norm minimizations.Hence,we first consider some properties of the unique solution to problem(2)in this section.

2.1Range space property

In this subsection,we first reformulate problem(2)as a linear program.Then based on the duality theory,we present a necessary condition for a unique solution to problem(2).

Suppose that problem(2)admits a unique solution(x?,y?).Then for its any feasible solution(x,y)≠(x?,y?),there is wTx+aTy＞wTx?+aTy?.In other words,

{(x,y):Ax+By=b,wTx+aTy≤wTx?+aTy?,(x,y)≥0}={(x?,y?)}.

Now consider the following linear optimization problem:

It is easy to verify that problem(5)has a feasible solution(x?,y?),and its optimal value is finite(always equals zero).By introducing slack variable t≥0,the aboveproblem(5)is equivalent to:

Before proceeding,we can obviously obtain the following lemma,which will be used below.

Lemma 2.1 The following three statements are equivalent:

(i)(x?,y?)is the unique solution to the weighted l1-norm minimization problem (2).

(ii)(x?,y?)is the unique solution to problem(5).

(iii)(x,y,t)=(x?,y?,0)is the unique solution to problem(6).

The dual of problem(6)is given by:

where z∈?m,c∈? are the dual variables.Assume that α,β∈?m,γ∈?+are slack variables of problem(7),then we have

Next,if problem(2)admits a unique solution,then(A,B)Tsatisfies the range space property at this point,which is given by the following lemma.

Lemma 2.2 If(x?,y?)is the unique solution to problem(2),then there exists a z∈?msatisfying

Proof First,it is easy to check that problem(6)and its duality(7)have feasible solutions.Then by the complementary slackness theory[31],there exists a pair of strictly complementary optimal solution((x,y,t),(z1,c1))to problems(6)and(7). Let(α,β,γ)=(?ATz1?c1w,?BTz1?c1a,?c1).Then we have

and

Since(x?,y?)is the unique solution,by Lemma 2.1,(x?,y?,0)is the unique solution to problem(6).Then we obtain

which together with x?≥0,y?≥0 implies that

From(9)-(11),we have

By the definitions of these slack variables,we obtain

which is

This completes the proof of Lemma 2.2.

Hence,the inequality system(8)is necessary for(x?,y?)to be the unique solution to the weighted l1-norm minimization problem(2).And throughout this paper,the inequality system(8)is called the range space property(RSP)of(A,B)Tat(x?,y?).

2.2Full column rank condition

In this subsection,we present another necessary condition for the existence of a unique solution to the weighted l1-norm minimization problem(2),which is given by the following lemma.

Lemma 2.3 Let(x?,y?)be the unique solution to problem(2),then the matrix

is of full column rank,where

Proof Suppose that the columns of M are linear dependent.Then there exists a vectorsatisfying

Let us define a vector(x,y,t)as

Hence,problem(6)has at least two solutions,which contradicts the assumption of Lemma 2.3.We have thus proved the lemma.

2.3Sufficient condition

Combing the above two necessary conditions,we obtain the following sufficient condition for the existence of a unique solution to problem(2).

Lemma 2.4Let(x?,y?)be a feasible solution to problem(2).If the RSP of(A,B)Tholds at(x?,y?),and the matrixis of full column rank,then(x?,y?)is the unique solution to problem(2),where

Proof According to Lemma 2.1,it suffices to prove that(x?,y?,0)is the unique solution to problem(6).Since(A,B)Tsatisfies the RSP at(x?,y?),there exists a z∈?msatisfying

Combing(14)with c=?1,it is easy to verify that,if(z,c)satisfies(14)then it is a feasible solution to problem(7).Now we prove that(z,c)is also an optimal solution to problem(7).Substituting such(z,c)into the objective function of(7),we have

On the other hand,the optimal value of its primal problem(6)is 0,which together with the strong duality theorem implies that problem(7)has an optimal value 0 and(z,c)is its optimal solution.

Next,we prove that such(x?,y?,0)is the unique solution to problem(6).Let (x′,y′,t′)be its any optimal solution.Since(z,c)satisfying(14)is an optimal solution to problem(7),((x′,y′,t′),(z,c))is a pair of optimal solutions to problems (6)and(7).Assume that α,β,γ are slack variables of(7)and defined by

According to(14),we have

On the other hand,by the complementary slackness conditions,(x′,y′,t′)and(α,β,γ) satisfy

which together with(15)implies that

Substituting(17)into the constraints of(6),we get

which is

2.4Sufficient and necessary condition

In this subsection,we present a sufficient and necessary condition for the unique solution to problem(2).This condition is the foundation of the equivalence between the partial sparse and the weighted l1-norm minimization problems with nonnegative constrains in this paper.

Theorem 2.1 Let(x?,y?)be a feasible solution to problem(2).Then(x?,y?) is the unique solution if and only if the RSP of(A,B)Tholds at(x?,y?),and the matrixis of full column rank,where,

The proof of Theorem 2.1 is evident from Lemmas 2.2,2.3 and 2.4.Furthermore, ifis of full column rank,then so is the matrix

Unfortunately,its converse does not hold.For example,for

it is obvious that

is of full column rank,but the columns of

are linear dependent.

However,if the RSP of(A,B)Tholds at(x?,y?),thenis of full column rank if and only ifis of full column rank,which directly produces the following theorem from Theorem 2.1.

Theorem 2.2 Let(x?,y?)be a feasible solution to problem(2).Then(x?,y?) is the unique solution if and only if the RSP of(A,B)Tholds at(x?,y?),and the submatrixis of full column rank,where J+={i:xi＞0},S+={i: yi＞0}.

Theorems 2.1 and 2.2 adequately characterize the condition for the existence of a unique solution to problem(2).Next we present an example to show that it is easy to verify the sufficient and necessary condition.

Example 2.1 Consider the following linear system Ax+By=b,where

If let w=(1,1,1)T,a=(0,0)T,it is easy to verify thatis a feasible solution to problem(2).Denote

Then the submatrix

corresponding to(x?,y?)is of full column rank.Moreover,there exists a z=such thatThen the RSP of the matrix(A,B)Tholds at(x?,y?).According to Theorem 2.2,we know that(x?,y?) is the unique solution to the weighted l1-norm minimization problem.

3　Equivalent Condition

In this section,we study the equivalence between problems(1)and(2).From the sufficient and necessary conditions given by Theorems 2.1 and 2.2,if(x?,y?)is the unique solution to problem(2),then(AJ+,BS+)must be of full column rank. Hence,

which shows that,if(x?,y?)is the unique solution,it must be m-sparse,and that any nonnegative vector(x,y),whose sparsity is greater than m,must not be an optimal solution to problem(2).

As we know,Gaussian elimination can easily obtain an m-sparse solution.However,it cannot guarantee that the obtained solution is the sparsest.In fact,problem (1)is an NP-hard combinatorial optimization problem.And many relaxation methods have been proposed,such as relaxing the problem to the weighted l1-norm minimization problem.Hence,we must find out that,under what condition problems(1) and(2)have the same sparse solutions.The following theorem provides somewhat an answer according to the sufficient and necessary conditions in Theorems 2.1 and 2.2.

Theorem 3.1 Let(x?,y?)be an optimal solution to the l0-norm minimization problem(1).Then it also is a solution to the weighted l1-norm minimization problem (2)if and only if the RSP of the matrix(A,B)Tholds at(x?,y?),and(AJ+,BS+) is of full column rank,where

ProofIf problems(1)and(2)are equivalent,then there exists an optimal solution(x?,y?)to problem(1),which is also the unique optimal solution to problem (2).LetDue to Theorem 2.2,the RSP of the matrix (A,B)Tholds at(x?,y?),and(AJ+,BS+)is of full column rank.

On the other hand,if the RSP of the matrix(A,B)Tholds at(x?,y?),and (AJ+,BS+)is of full column rank,then by Theorem 2.2,(x?,y?)is also a solution to problem(2).The proof is completed.

Next,we present an example to show that,when the l0-norm minimization problem has several sparsest solutions,the weighted l1-minimization problem could still has one of the sparsest solutions.

Example 3.1 Consider the linear system Ax+By=b,where

It is easy to verify that if,thenis the unique solution to the weighted l1-norm minimization problem.

Theorem 2.1 and Example 3.1 show that the existence of a unique solution to l0-norm minimization is not necessary for the equivalence between the l0-norm and weighted l1-norm minimization problems.

4　Strongly Equivalent Condition

In practice,the matrices A and B should be suitable such that we can find all k-sparse solutions.In this section,we will discuss the RSP of order k,which guarantees finding all k-sparse vectors.First,we present the definition of the RSP of order k as follows.

Definition 4.1 Let A∈?m×n1,B∈?m×n2with m＜n1+n2.The matrix (A,B)Tis said to satisfy the RSP of order k,if for any subset S1of{1,2,···,n1} and subset S2of{1,2,···,n2}with|S1|≤k and|S1|+|S2|≤m,(AS1,AS2)is of full column rank,and there exists a z∈?msatisfying

Now we give an example to show the existence of the matrix satisfying the RSP of order k.It is easy to verify that:

If S1=?,S2={1},then there existssatisfying,BTz=

if S1= ?,S2={2},then there exists asatisfying,

if S1=?,S2={1,2},then there exists a z=(0,0)Tsatisfying ATz=0, BTz=(0,0);

if S1={1},S2=?,then there exists asatisfying ATz=1,

if S1={1},S2={1},then there exists asatisfying ATz=1,

if S1={1},S2={2},then there exists a z=(?1,0)Tsatisfying ATz=1, BTz=(?1,0).

Hence,for any S1,S2with|S1|≤1,|S1|+|S2|≤2,there exists a z∈R2such that (A,B)Tsatisfies the RSP,that is,the matrix(A,B)Tsatisfies the RSP of order k.

Next,we claim that if the matrix(A,B)Tsatisfies the RSP of order k,then we can find all k-sparse solutions,which is presented as follows.

Theorem 4.1 Weighted l1-norm minimization could find any nonnegative solution(x,y)with∥x∥0≤k,∥(x,y)∥0≤m if and only if the matrix(A,B)Tsatisfies the RSP of order k.

Proof Assume that any vector(x,y)with∥x∥0≤k,∥(x,y)∥0≤m can be found by weighted l1-norm minimization.Then(x,y)is the unique solution to

Denote S1={i:xi＞0},S2={i:yi＞0}.By Theorem 2.2,the matrix(AS1,BS2) is of full column rank,and there exists a z∈Rmsatisfying

Since(x,y)is arbitrary and satisfies∥x∥0≤k,∥(x,y)∥0≤m,the corresponding sets S1,S2are also arbitrary subsets of{1,2,···,n1},{1,2,···,n2}respectively and satisfy|S1|≤k,|S1|+|S2|≤m,and there exists a z∈Rmsatisfying(18).Hence, the matrix(A,B)Tsatisfies the RSP of order k.

On the contrary,assume the matrix(A,B)Tsatisfies the RSP of order k.Then for any vector(x,y)with∥x∥0≤k,∥(x,y)∥0≤m,the corresponding submatrix (AS1,BS2)is of full column rank satisfying the RSP at(x,y),where S1={i:xi＞0}, S2={i:yi＞0}.According to Theorem 2.2,we claim that(x,y)is the unique solution to the weighted l1-norm minimization problem.The proof is completed.

Theorem 4.2Assume that(A,B)Tsatisfies the RSP of order k.Then any nonnegative vector(x,y)with∥x∥0≤k and∥(x,y)∥0≤m is the unique solution to both the l0-norm and weighted l1-norm minimization problems.

Proof By Theorem 4.1,any nonnegative vector(x,y)with∥x∥0≤k,∥(x,y)∥0≤m can be found by weighted l1-norm minimization.Hence,such(x,y)is the unique solution to the weighted l1-norm minimization problem.Now we prove that it is alsothe unique solution to the l0-norm minimization problem.Suppose(x1,y1)is an optimal solution to the l0-norm minimization problem and satisfies∥x1∥0≤∥x∥0. DenoteThen|S1|=∥x1∥0≤∥x∥0≤k, |S1|+|S2|≤m,which together with the RSP of order k of(A,B)Timply that (AS1,BS2)is of full column rank and satisfies the RSP at(x1,y1).By Theorem 2.4, (x1,y1)is the unique solution to the weighted l1-norm minimization problem.Hence, (x,y)=(x1,y1).Then by arbitrariness of(x1,y1),(x,y)is the unique solution to the l0-norm minimization problem.The proof is completed.

Theorem 4.2 shows that if the matrix(A,B)Tsatisfies the RSP of order k,then the l0-norm and weighted l1-norm minimization problems are strongly equivalent. However,Theorem 3.1 states that,when the RSP of the matrix(A,B)Tholds at one sparsest solution to the l0-norm minimization problem,the l0-norm and weighted l1-norm minimization problems are equivalent.Hence,the RSP of order k is stronger then the RSP at a solution.This may be also explained that the RSP is a local property,which only requires to be satisfied at one special solution,while the RSP of order k is a global property,which requires to be satisfied for all(x,y)with∥x∥0≤k,∥(x,y)∥0≤m.

5　Several Variants

In this section,we discuss several variants of problem(1).Fortunately,all these variants can be rewritten as the form of(1).

No nonnegative constraints In this case,the variables x∈?n1,y∈?n2are not nonnegative.The problem is

To obtain the form of(1),for a given(x,y),we define

Then x=x+?x?,y=y+?y?.And the equality constraint can be rewritten as

and∥x∥0=∥x+?x?∥0=∥x+∥0+∥x?∥0.Therefore,problem(19)can be reformulated as

Inequality constraints When the constraints are inequalities,the problem is

By introducing slack variablesthe above problem can be rewritten as

where I is the identity matrix of m-dimensions.

Noisy caseIn many practical problems,the measurement data b always is noisy.Then the optimization problem is

where σ≥0 controls the error between Ax+By and b.In this case,the constraint can be written as

which is

Then this case can be reduced to the second case.

6　Conclusions

In this paper,we have considered the equivalence conditions between the partial sparse optimization problem and its relaxation,that is,the weighted l1-norm minimization problem.The proposed conditions are based on the RSP,and guarantee not only the strong equivalence,but also the equivalence between the two problems. The considered problem is more general than the problems considered in literatures.

References

[1]M.Davenport,P.Boufounos,and M.Wakin.Signal processing with compressive measurements,IEEE Journal of Selected Topics in Signal Processing,4:2(2010),445-460.

[2]J.Wright,A.Y.Yang,A.Ganesh,and S.S.Sastryand Y.Ma,Robust face recognition via sparse representation,IEEE Transactions on Pattern Analysis and Machine Intelligence,31:2(2009),210-227.

[3]R.He,W.Zheng,B.Hu,and X.Kong,Nonnegative sparse coding for discriminative semi-supervised learning,IEEE Conference on Computer Vision and Pattern Recognition(CVPR),pages 2849-2856,2011.

[4]M.Sheikh,S.Sarvotham,and O.Milenkovic,DNA array decodin from nonlinear measurements by belief propagation,IEEE Workshop on Statistical Signal Processing (SSP),Madison,Wisconsin,2007.

[5]M.Lustig,D.Donoho,and J.M.Pauly,Sparse MRI:The application of compressed sensing for rapid mr imaging,Magnetic Resonance in Medicine,58:6(2007),1182-1195.

[6]W.U.Bajwa,J.D.Haupt,A.M.Sayeed,and R.D.Nowak,Joint source-channel communication for distributed estimation in sensor networks,IEEE Transactions on Information Theory,53:10(2007),3629-3653.

[7]S.D.Cabrera and T.W.Parks,Extrapolation and spectral estimation with iterative weighted norm modification,IEEE Transactions on Signal Processing,39:4(1991),842-851.

[8]M.Elad,M.A.T.Figueiredo,and Y.Ma,On the role of sparse and redundant representations in image processing,Proceedings of the IEEE,98:6(2010),972-982.

[9]X.Zhan,R.Zhang,D.Yin,and C.Huo,SAR image compression using multiscale dictionary learning and sparse representation,IEEE Geoscience and Remote Sensing Letters,10:5(2013),1090-1094.

[10]B.K.Natara jan,Sparse approximate solutions to linear systems,SIAM Journal on Computing,24:2(1995),227-234.

[11]E.Cand`es,J.Romberg,and T.Tao,Robust uncertainty principles:exact signal reconstruction from highly incomplete frequency information,IEEE Transactions on Information Theory,52:2(2006),489-509.

[12]X.Chen and W.Zhou,Convergence of reweighted l1minimization algorithms for l2-lpminimization,Computational Optimization and Applications,59:2(2014),47-61.

[13]I.Daubechies,R.DeVore,M.Fornasier,and C.S.Güntürk,Iteratively reweighted least squares minimization for sparse recovery,Communications on Pure and Applied Mathematics,63:1(2010),1-38.

[14]S.Foucart and M.Lai,Sparsest solutions of undertermined linear systems via lpminimization for 0＜p≤1,Applied and Computational Harmonic Analysis,26(2009), 395-407.

[15]M.Lai and J.Wang,An unconstrainted lpminimization with 0＜q≤1 for sparse solution of underdetermined linear systems,SIAM Journal on Optimination,21(2010),82-101.

[16]P.Combettes and J.Pesquet,Proximal thresholding algorithm for minimization over orthonormal bases,SIAM Journal on Optimination,18:4(2007),1351-1376.

[17]R.Chartrand,Nonconvex compressed sensing and error correction,International Conference on Acoustics Speech and Signal Processing(ICASSP),pages 889-892,2007.

[18]J.Darbon and M.Sigelle,Image restoration with discrete constrained total variation part i:Fast and exact optimization,Journal of Mathematical Imaging and Vision, 26:3(2006),261-276.

[19]D.L.Donoho and M.Elad Optimally sparse representation in general(nonorthogonal)dictionaries vis l1minimization,Proceedings of the National Academy of Sciences, 100:5(2003),2197-2202.

[20]R.Gribonval and M.Nielsen,Sparse representations in unions of bases,IEEE Transactions on Information Theory,49:12(2003),3320-3325.

[21]A.Cohen,W.Dahmen,and R.DeVore,Compressed sensing and best k-term approximation,J.Amer.Math.Soc.,22(2009),211-231.

[22]Y.Zhang,A simple proof for recoverability of l1-minimization(ii):the nonnegative case,Rice University,Technical Report,2005.

[23]E.Cand`es,Compressive sampling,International Congress of Mathematicians,Madrid, Spain,pages 1433-1452,2006.

[24]E.Cand`es and T.Tao,Decoding by linear programming,IEEE Transactions on Information Theory,51:12(2005),4203C4215.

[25]E.Cand`es,The restricted isometry property and its implications for compressed sensing,Comptes Rendus Mathematique,346:10(2008),589-592.

[26]Y.B.Zhao,RSP-based analysis for sparsest and least l1-norm solutions to underdetermined linear systems,IEEE Transactions on Signal Processing,61:22(2013),5777-5788.

[27]Y.B.Zhao.Equivalence and strong equivalence between sparsest and least l1-norm nonnegative solutions to linear systems and their applications,Journal of the Operations Research Society of China,2:2(2014),171-193.

[28]S.Foucart and H.Rauhut,A Mathematical Introduction to Compressive Sensing,NY: Birkh? user,New York,2013.

[29]M.Elad and A.Bruckstein,A generalized uncertainty principle and sparse representation in pairs of bases,IEEE Transactions on Information Theory,48:9(2002),2558-2567.

[30]D.L.Donoho and J.Tanner,Sparse nonnegative solutions of underdetermined linear equations by linear programming,Proceeding of the National Academy of sciences USA, 102:27(2005),9446-9451.

[31]A.Schrijver,Theory of Linear and Integer Programming,Wiley,New York,1986.

(edited by Liangwei Huang)

?Research supported by the National Natural Science Foundation of China under Grant 61672005.

?Manuscript May 23,2016;Revised September 18,2016

?.E-mail:wxzhu@fzu.edu.cn