You are an expert at summarizing long articles. Proceed to summarize the following text: 
signal reconstruction is usually formulated as a linear inverse problem @xmath1 where @xmath2 is the true signal , @xmath3 is an @xmath4 real matrix , @xmath5 is the observed data and @xmath6 represents the random noise . over the last decade , sparse reconstruction has received great attentions @xcite . in general , the task of sparse reconstruction is to find a sparse @xmath7 from . obviously , the most natural measure of sparsity is the @xmath0-norm , defined at @xmath2 as @xmath8 where @xmath9 stands for the cardinality of the set @xmath10 and @xmath11 denotes the support of @xmath7 , that is @xmath12 . when the noise level of @xmath13 is known , we consider the following constrained @xmath0 regularization problem @xmath14 where @xmath15 denotes the @xmath16-norm , and @xmath17 is the noise level . specially , in the noiseless case , i.e. , when @xmath18 , problem reduces to seeking for the sparsest solutions from a linear system as follows @xmath19    finding a global minimizer of problem is known to be combinational and np - hard in general @xcite as it involves the @xmath0-norm . the number of papers dealing with the @xmath0-norm is large and several types of numerical algorithms have been adopted to approximately solve the problem . in this paper , we mainly focus on the penalty methods . before making a further discussion on the penalty methods , we briefly review other two types of approaches , greedy pursuit methods and relaxation of the @xmath0-norm . greedy pursuit methods , such as orthogonal matching pursuit @xcite and cosamp @xcite , adaptively update the support of @xmath7 by exploiting the residual and then solve a least - square problem on the support in each iteration . this type of algorithms are widely used in practice due to their relatively fast computational speed . however , only under very strict conditions , can they be shown theoretically to produce desired numerical solutions to problem . relaxation methods first replace the @xmath0-norm by other continuous cost functions , including convex functions @xcite and nonconvex functions @xcite , such as the bridge functions @xmath20 with @xmath21 @xcite , capped-@xmath22 functions @xcite , minmax concave functions @xcite and so on . then the majorization - minimization strategy is applied to the relaxation problem , which leads to solving a constrained reweighted @xmath22 or @xmath16 subproblems @xcite in each step . the cost functions of the iterates are shown to be descent @xcite , while the convergence of the iterates themselves are generally unknown . the penalty method is a classical and important approach for constrained optimization . for an overview on the penalty method , we refer the readers to the book @xcite . an extensively used penalty method for problem is to solve the following least square penalty problem @xmath23 where @xmath24 is a penalty parameter . as problem still involve the @xmath0-norm , the greedy pursuit and relaxation methods mentioned before are applicable for approximately solving the problem . however , it has relatively better structure than problem from the standpoint of algorithmic design . more precisely , the proximal operator of @xmath0-norm has a closed form , while the least square penalty term in problem is differentiable with a lipschitz continuous gradient . therefore , it can be directly and efficiently solved by proximal - gradient type algorithms @xcite or primal - dual active set methods @xcite . one specific proximal - gradient type algorithm for problem is the iterative hard thresholding ( iht ) @xcite . in general , it is shown in @xcite that for arbitrary initial point , the iterates generated by the algorithm converge to a local minimizer of problem . under certain conditions , the iht converges with an asymptotic linear rate . the structure of the least square penalty problem makes it easier to develop convergent numerical algorithms .    the penalty parameter @xmath25 balances the magnitude of the residual and the sparsity of solutions to problem . an important issue is that wether problem and share a common global minimizer for some penalty parameter @xmath25 . it seems intuitive that there exists certain connections between these two problems . however , to the best of our knowledge , there is very little theoretical results on penalty methods for problem in general . recently , chen , lu and pong study the penalty methods for a class of constrained non - lipschitz optimization @xcite . the non - lipschitz cost functions considered in @xcite does not contain the @xmath0-norm and the corresponding results can not be generalized to the constrained @xmath0 regularization problems . nikolova in @xcite gives a detailed mathematical description of optimal solutions to problem and further in @xcite establishes their connections with optimal solutions to the following optimization problem @xmath26 where @xmath27 is a given positive integer . problem also involves the @xmath0-norm and is usually called the sparsity constrained minimization problem . however , optimal solutions of problem and their connections with problem have not been studied in these works . this paper is devoted to describing global minimizers of a class of constrained @xmath0 regularization problems and the corresponding penalty methods . as in @xcite , we use `` optimal solutions '' for global minimizers and `` optimal solution set '' for the set of all global minimizers in the remaining part of this paper . the class of constrained @xmath0 regularization problems we considered has the following form @xmath28 where @xmath29 or @xmath30 . obviously , problem has two cases , the @xmath16 constrained problem and the @xmath22 constrained problem as follows @xmath31 the analysis of these two constrained problems and their penalty methods share many common points and thus we shall discuss them in a unified way . moreover , we introduce a class of scalar penalty functions @xmath32 satisfying the following blanket assumption , where @xmath33 . [ hypo:1 ] the function @xmath34 is continuous , nondecreasing with @xmath35 . then the penalty problems for can be in general formulated as @xmath36 where @xmath24 is a penalty parameter . in the case of @xmath37 , when we set the penalty function @xmath38 for @xmath39 , the general penalty problem reduces to the specific problem . we shall give a comprehensive study on connections between optimal solutions of problem and problem . our main contributions are summarized below . * we study in depth the existence , stability and cardinality of solutions to problems and . in particular , we prove that the optimal solution set of problem is piecewise constant with respect to @xmath25 . more precisely , we present a sequence of real number @xmath40 where @xmath41 . we claim that for all @xmath42 , problems with different @xmath43 share completely the same optimal solution set . * we clarify the relationship between optimal solutions of problem and those of problem . we find that , when @xmath44 problem probably * never * has a common optimal solution with problem for any @xmath24 . this means that the penalty problem may fail to be an exact penalty formulation of problem . a numerical example is presented to illustrate this fact in section [ sec : exp ] . * we show that under a mild condition on the penalty function @xmath45 , problem has exactly the same optimal solution set as that of problem once @xmath46 for some @xmath47 . in particular , for @xmath37 we present a penalty function @xmath45 with which the penalty term in problem is differentiable with a lipschitz continuous gradient . this penalty function enables us to design innovative numerical algorithms for problem . the remaining part of this paper is organized as follows . in section [ sec : exist ] we show the existence of optimal solutions to problems and . the stability for problems and are discussed in section [ sec : sta ] . we analyze in section [ sec : relation ] the relationship between optimal solutions of problems and . section [ sec : equal ] establishes a sufficient condition on @xmath45 , which ensures problems and have completely the same optimal solution set when the parameter @xmath25 is sufficiently large . we further investigate the cardinality and strictness of optimal solutions to problems and in section [ sec : minimizer ] . the theoretical results are illustrated by numerical experiments in section [ sec : exp ] . we conclude this paper in section [ sec : con ] . this section is devoted to the existence of optimal solutions to problems and . the former issue is trivial , while the latter issue requires careful analysis . after a brief discussion on the existence of optimal solutions to problem , we shall focus on a constructive proof of the existence of optimal solutions to problem . since the objective function of problem is proper , lower semi - continuous and has finite values , it is clear that problem has optimal solutions as long as the feasible region is nonempty . we present the result in the following theorem . for simplicity , we denote by @xmath48 the feasible region of problem , that is @xmath49    [ thm : existconst ] the optimal solution set of problem is nonempty if and only if @xmath50 , where @xmath48 is defined by .    in the rest of this section , we dedicate to discussing the existence of optimal solutions to problem . since the objective function of consists of two terms , we begin with defining several notations by alternating minimizing each term . to this end , for any positive integer @xmath51 , we define @xmath52    [ def : srhoomega ] given @xmath45 satisfying h[hypo:1 ] and @xmath53 , the integer @xmath54 , the sets @xmath55 , @xmath56 , @xmath57 are defined by the following iteration @xmath58    we first show that definition [ def : srhoomega ] is well defined . it suffices to prove both the following two optimization problems @xmath59 and @xmath60 have optimal solutions for any @xmath61 and @xmath62 . clearly , problem has an optimal solution since the objective function is piecewise constant and has finite values . the next lemma tells us that the optimal solution set of problem is always nonempty for any @xmath63 . we denote by @xmath64 the @xmath65-dimensional vector with @xmath66 as its components . for an @xmath4 matrix @xmath67 and @xmath68 , let @xmath69 formed by the columns of @xmath67 with indexes in @xmath70 . similarly , for any @xmath2 and @xmath68 , we denote by @xmath71 the vector formed by the components of @xmath7 with indexes in @xmath70 . [ lema : l0constsolu ] given @xmath45 satisfying h[hypo:1 ] and @xmath53 , for any @xmath63 , the optimal solution set of problem is nonempty .    as function @xmath45 is nondecreasing in @xmath72 , it suffices to show that the optimization problem @xmath73 has an optimal solution . we first prove that for any @xmath68 , the optimization problem @xmath74 has an optimal solution . obviously , @xmath75 is an optimal solution to problem if and only if @xmath76 and @xmath77 in the case of @xmath37 , it is well - known that @xmath78 is an optimal solution to problem , where @xmath79 is the pseudo - inverse matrix of the matrix @xmath80 . when @xmath29 , the optimal solution set of problem is nonempty since @xmath81 is a piecewise linear function and bounded below , see proposition 3.3.3 and 3.4.2 in @xcite . therefore , problem has an optimal solution for any @xmath68 . with the help of problem , problem can be equivalently written as @xmath82 clearly , the optimal solution set of problem is nonempty , therefore , problem has an optimal solution . we then complete the proof .    by lemma [ lema : l0constsolu ] , definition [ def : srhoomega ] is well defined . we present this result in the following proposition . given @xmath45 satisfying h[hypo:1 ] and @xmath53 , the integer @xmath54 and @xmath83 for @xmath84 can be well defined by definition [ def : srhoomega ] . we then provide some properties of @xmath54 and @xmath83 for @xmath85 defined by definition [ def : srhoomega ] in the following proposition . [ prop : rhosomega ] given @xmath45 satisfying h[hypo:1 ] and @xmath53 , let @xmath54 and @xmath83 for @xmath84 be defined by definition [ def : srhoomega ] . then the following statements hold :    * @xmath86 and @xmath87 , where @xmath88 denotes the rank of @xmath3 . * @xmath89 . * @xmath90 . * @xmath91 , @xmath92 and @xmath93 , for @xmath94 , @xmath95 . * @xmath96 for @xmath97 . items ( ii ) , ( iii ) , ( iv ) and ( v ) are clear by definition [ def : srhoomega ] . we dedicate to proving item ( i ) following . let @xmath98 . from the proof of lemma [ lema : l0constsolu ] , since @xmath45 is nondecreasing , @xmath100 for any @xmath101 . let @xmath102 , then @xmath103 . let @xmath104 denote the @xmath105th column of @xmath3 , @xmath106 . since the rank of @xmath3 is @xmath88 , without loss of generality , we assume @xmath107 is the maximal linearly independent group of @xmath108 . then there exists @xmath109 such that @xmath110 . we define @xmath111 as @xmath112 for @xmath113 and @xmath114 for @xmath115 . it is obvious that @xmath116 and @xmath117 , implying @xmath118 . therefore @xmath119 . then by the definition of @xmath120 , we have @xmath121 . from the procedure of the iteration in definition [ def : srhoomega ] and @xmath122 , we obtain @xmath123 .    with the help of definition [ def : srhoomega ] , the euclid space @xmath124 can be partitioned into @xmath125 sets : @xmath126 , @xmath127 , @xmath128 . therefore , in order to establish the existence of optimal solutions to problem , it suffices to prove the existence of optimal solutions to problem @xmath129 and @xmath130 for all @xmath131 . we present these desired results in the following lemma . [ lema : partitionsolution ] given @xmath45 satisfying h[hypo:1 ] and @xmath53 , let @xmath54 and @xmath83 for @xmath84 be defined by definition [ def : srhoomega ] . then for any @xmath24 , the following statements hold :    * the optimal solution sets of problems and for @xmath128 are not empty . * the optimal value of problem is @xmath132 and the optimal solution set to problem is @xmath133 . * the optimal value of problem is @xmath134 and the optimal solution set of problem is @xmath135 , for @xmath128 .    we only need to prove items ( ii ) and ( iii ) since they imply item ( i ) . we first prove item ( ii ) . it is obvious that restricted to the set @xmath126 , the minimal value of the first term @xmath136 is @xmath120 and can be attained at any @xmath137 . by definition [ def : srhoomega ] , the minimal value of @xmath138 is @xmath139 and can be attained at any @xmath137 . therefore , the optimal value of problem is @xmath132 . let @xmath140 be the optimal solution set of problem . clearly , @xmath141 . we then try to prove @xmath142 . it suffices to prove @xmath143 for any @xmath101 . if not , there exists @xmath102 and @xmath144 , then @xmath145 . then the objective function value at @xmath146 is no less than @xmath147 due to the definition of @xmath139 , contradicting the fact that @xmath146 is an optimal solution of problem . then we get item ( ii ) . item ( iii ) can be obtained similarly , we omit the details here .    for convenient presentation , we define @xmath148 , for @xmath97 , at @xmath149 as @xmath150 now , we are ready to show the existence of optimal solutions to problem . [ thm : exist ] given @xmath45 satisfying h[hypo:1 ] and @xmath53 , let @xmath54 and @xmath83 for @xmath84 be defined by definition [ def : srhoomega ] . let @xmath151 for @xmath152 be defined by . then , the optimal solution set of problem is nonempty for any @xmath24 . furthermore , the following statements hold for any fixed @xmath24 :    * the optimal value of problem is @xmath153 . * @xmath154 is the optimal solution set of problem , where @xmath155 . we omit the proof here since it is a direct result of the fact that @xmath156 and lemma [ lema : partitionsolution ] .    [ remark : l=0 ] according to definition [ def : srhoomega ] , if @xmath157 , then @xmath158 and @xmath159 . then , by theorem [ thm : exist ] , if @xmath157 , the optimal value and the optimal solution set of problem are @xmath160 and @xmath161 respectively for any @xmath24 . in this section , we study the stability for problems and , including behaviors of the optimal values and optimal solution sets with respect to changes in the corresponding parameters . we prove that , the optimal value of problem and that of problem change piecewise constantly and piecewise linearly respectively as the corresponding parameters vary . moreover , we prove that the optimal solution set of problem is piecewise constant with respect to the parameter @xmath25 . we begin with introducing the notion of marginal functions , which plays an important role in optimization theory , see for example @xcite . set @xmath162 where @xmath53 . by lemma [ lema : l0constsolu ] , we have @xmath163 is well defined . let @xmath164 defined at @xmath165 as @xmath166 where @xmath48 is defined by . clearly , for a fixed @xmath165 , @xmath167 is the optimal value of problem . thus @xmath168 is well defined due to theorem [ thm : existconst ] . the function @xmath168 is also called the marginal function of problem . similarly , we can define the marginal function of problem . given @xmath45 satisfying h[hypo:1 ] and @xmath53 , we define @xmath169 at @xmath24 as @xmath170 clearly , @xmath171 is well defined due to theorem [ thm : exist ] .    in order to study the stability of the optimal solution sets of problems and , we define @xmath172 at @xmath165 as the optimal solution set of the constrained problem , that is , @xmath173 where @xmath48 is defined by and @xmath174 collects all the subsets of @xmath124 . by theorem [ thm : existconst ] , @xmath175 is well defined . we also define @xmath176 at @xmath24 as @xmath177 for a fixed @xmath24 , @xmath178 is the optimal solution set of problem , therefore , is also well defined due to theorem [ thm : exist ] . then , our task in this section is establishing the properties of functions @xmath168 and @xmath171 as well as properties of mappings @xmath175 and @xmath179 . this subsection is devoted to the stability for problem . we explore the behaviors of the marginal function @xmath168 and optimal solution set @xmath175 with respect to @xmath180 . we begin with a lemma which is crucial in our discussion . [ lemma : lambdastrict ] given @xmath45 satisfying h[hypo:1 ] and @xmath53 , let @xmath54 and @xmath83 for @xmath84 be defined by definition [ def : srhoomega ] . for any @xmath181 , @xmath97 , let @xmath182 . then the following hold :    * @xmath80 has full column rank . * if @xmath183 , then @xmath71 is the unique minimizer of @xmath184 , that is for any @xmath185 , @xmath186 . we first prove item ( i ) . we prove it by contradiction . if not , there exists @xmath187 such that @xmath188 and @xmath189 such that @xmath190 . therefore , @xmath191 . this contradicts the definition of @xmath192 . then we get item ( i ) . we next prove item ( ii ) . since @xmath183 and @xmath45 is nondecreasing , it follows that @xmath193 . thus , @xmath194 for any @xmath181 . the problem @xmath184 is equivalent to the problem @xmath195 then from item ( i ) , the objective function of the convex optimization problem is strictly convex . therefore , we obtain item ( ii ) . we next show an important proposition which reveals the relationship between @xmath196 and the optimal solution set of problem . clearly , when @xmath197 , @xmath198 . thus , we only discuss cases as @xmath199 . [ prop : partialeauvalence ] given @xmath45 satisfying h[hypo:1 ] and @xmath53 , let @xmath54 and @xmath83 for @xmath84 be defined by definition [ def : srhoomega ] . let @xmath175 , @xmath48 and @xmath200 be defined by , and respectively . suppose @xmath45 is strictly increasing . then , the following statements hold :    * for any @xmath201 , there must exist @xmath202 such that @xmath203 , and @xmath204 is a subset of @xmath205 , that is @xmath206 moreover , @xmath207 for any @xmath208 . * particularly , if the @xmath51 in item ( i ) satisfies @xmath209 , then @xmath205 is equal to @xmath204 , that is @xmath210 * further , if @xmath37 and the @xmath51 in item ( i ) satisfies @xmath211 , then @xmath204 is a real subset of @xmath205 , that is @xmath212    we first prove item ( i ) . since @xmath45 is strictly increasing , @xmath213 and @xmath214 , there must exist @xmath202 such that @xmath203 due to item ( iii ) of proposition [ prop : rhosomega ] . we then prove @xmath215 . let @xmath216 , we will show @xmath217 . since @xmath218 , @xmath219 and @xmath45 is strictly increasing , we have @xmath220 . in order to prove @xmath217 , we need to show that for any @xmath221 there holds @xmath222 . if not , there exists @xmath221 such that @xmath223 . by the definition of @xmath224 , we have @xmath225 , which contradicts the fact that @xmath226 . therefore , @xmath216 implies @xmath217 . moreover , since @xmath227 we have @xmath228 , where @xmath168 is the marginal function of problem , defined by . therefore , we have @xmath229 for any @xmath208 . we then get item ( i ) . next , we try to prove item ( ii ) . by item ( i ) of this proposition , we have @xmath207 for any @xmath208 . in order to prove , we only need to show @xmath230 for any @xmath208 due to item ( v ) of proposition [ prop : rhosomega ] . we next show it by contradiction . if there exists @xmath231 such that @xmath232 , then @xmath233 due to @xmath234 , the strictly increasing property of @xmath45 and @xmath209 . since @xmath235 , by the definition of @xmath236 , we have @xmath237 , contradicting . thus we get item ( ii ) of this proposition . finally , we prove item ( iii ) . we only need to show that there exists @xmath208 such that @xmath238 . let @xmath216 , we have @xmath239 . let @xmath182 . since @xmath45 is continuous and @xmath240 , there exists @xmath241 such that as long as @xmath242 , @xmath243 . let @xmath244 . then @xmath245 . set @xmath246 . set @xmath247 . obviously , @xmath248 , @xmath249 and @xmath250 . since @xmath45 is strictly increasing , we have @xmath221 . by item ( i ) of this proposition , @xmath208 due to @xmath207 and @xmath221 . we then show @xmath238 . it amounts to showing @xmath251 by item ( v ) of proposition [ prop : rhosomega ] . by item ( ii ) of lemma [ lemma : lambdastrict ] , we have @xmath252 since @xmath253 and @xmath7 share the same support @xmath70 . then by the strictly increasing property of @xmath45 we get @xmath238 . then item ( iii ) of this proposition follows . [ remark : same ] one can easily check that definition [ def : srhoomega ] produces the same @xmath54 and @xmath254 for @xmath84 for different choices of @xmath45 once they are all strictly increasing . therefore , it is reasonable that @xmath205 has connections with @xmath196 for @xmath84 , as shown in proposition [ prop : partialeauvalence ] . now , we are ready to establish the main results of this subsection . [ thm : staconst ] given @xmath255 defined at @xmath256 as @xmath257 and @xmath53 , let @xmath54 and @xmath83 for @xmath84 be defined by definition [ def : srhoomega ] . let @xmath168 and @xmath175 be defined by and respectively . then the following statements hold :    * @xmath258 * @xmath259 in particular , if @xmath37 , we have @xmath260 for @xmath261 , @xmath262 . * @xmath168 is a piecewise constant function and has at most @xmath263 values . further , @xmath168 is lower semicontinuous , right - continuous and nonincreasing . * @xmath264 for any @xmath265 satisfying @xmath266 , @xmath262 .    items ( i ) and ( ii ) follow from proposition [ prop : partialeauvalence ] . then item ( iii ) of this theorem follows immediately . by item ( i ) and @xmath267 for any @xmath265 satisfying @xmath266 , we obtain item ( iv ) . this subsection is for the stability of problem . we shall study the behaviors of the marginal function @xmath171 and optimal solution set @xmath268 with respect to @xmath25 . according to theorem [ thm : exist ] , @xmath269 with @xmath270 defined by . obviously , each @xmath270 for @xmath97 is a line with slop @xmath271 and intercept @xmath192 . therefore , by items ( ii ) and ( iii ) of proposition [ prop : rhosomega ] , it is easy to deduce that @xmath171 is continuous , piecewise linear and nondecreasing . next we propose an iteration procedure to find the minimal value of @xmath270 for @xmath97 , i.e. , the marginal function @xmath272 , for @xmath273 . [ def : lambda_i ] given @xmath45 satisfying h[hypo:1 ] and @xmath53 , let @xmath54 and @xmath83 for @xmath84 be defined by definition [ def : srhoomega ] . then the integer @xmath274 , @xmath275 are defined by the following iteration @xmath276    we present an example to illustrate the iterative procedure in definition [ def : lambda_i ] .    [ exam:3.6 ] in this example , we set @xmath277 . by proposition , we set @xmath278 and @xmath279 . then @xmath270 for @xmath280 can be obtained by equation [ def : fi ] . we depict the plots of @xmath270 for @xmath280 in figure [ fig : ex1 ] . we observe from figure [ fig : ex1 ] that , when @xmath281 , @xmath282 . further , the first and largest critical parameter @xmath283 can be obtained by the largest intersection point of @xmath284 and @xmath270 for all @xmath285 . here , we have that @xmath286 , which collects all the indexes that @xmath287 except @xmath288 . in order to search for the second critical parameter value @xmath289 , we first find that on the second interval @xmath290 , @xmath291 , where @xmath292 . thus , @xmath289 can be obtained by the largest intersection point of @xmath293 and @xmath294 for @xmath295 . then @xmath296 . thus , in this case , @xmath297 , @xmath298 . on interval @xmath299 , we have @xmath300 . in this example , @xmath301 for any @xmath24 .    [ fig : ex1 ]    the following proposition provides some basic properties of @xmath274 , @xmath302 and @xmath303 for @xmath304 by definition [ def : lambda_i ] . [ prop : lambda_i ] given @xmath45 satisfying h[hypo:1 ] and @xmath53 , let @xmath54 and @xmath83 for @xmath84 be defined by definition [ def : srhoomega ] . let @xmath274 , @xmath302 and @xmath303 for @xmath304 be defined by definition [ def : lambda_i ] . then the following statements hold :    * @xmath305 , in particular , if @xmath306 then @xmath307 . * @xmath308 . * @xmath309 . * @xmath310 and @xmath311 , for all @xmath94 , @xmath312 . the proof is outlined in appendix 8.1 .    the main results of this subsection are presented in the following theorem .    [ thm : stability ] given @xmath45 satisfying h[hypo:1 ] and @xmath53 , let @xmath54 and @xmath83 for @xmath84 be defined by definition [ def : srhoomega ] . let @xmath274 , @xmath302 and @xmath303 for @xmath304 be defined by definition [ def : lambda_i ] . let @xmath270 for @xmath97 , @xmath171 and @xmath268 be defined by , and respectively . by remark [ remark : l=0 ] , if @xmath157 , then @xmath313 and @xmath314 . if @xmath306 , then the following statements hold :    * @xmath315,\\ f_{t_i } , & \mathrm{~~if~~}\lambda\in ( \lambda_i , \lambda_{i-1 } ] , i\in\mathbb{n}_{k-1},\\ f_0(\lambda ) , & \mathrm{~~if~~}\lambda\in(\lambda_0 , + \infty ) . \end{cases}\ ] ] * @xmath316 * @xmath171 is continuous , piecewise linear and nondecreasing , particularly , @xmath171 is strictly increasing in @xmath317 .    to improve readability , the proof of theorem [ thm : stability ] and two auxiliary lemma and proposition are given in appendix 8.2 . a direct consequence of theorem [ thm : stability ] is stated below . [ crol : stability ] under the assumptions of theorem [ thm : stability ] , the following statements hold :    * if @xmath318 or @xmath319 , @xmath320 , then @xmath321 and @xmath322 hold for any @xmath323 and any @xmath324 . * if @xmath325 , then @xmath222 and @xmath326 hold for any @xmath323 and any @xmath324 .    item ( i ) can be obtained by item ( ii ) of theorem [ thm : stability ] as well as item ( v ) of proposition [ prop : rhosomega ] . similarly , item ( ii ) follows from item ( ii ) of theorem [ thm : stability ] , items ( ii ) , ( iii ) , ( v ) of proposition [ prop : rhosomega ] as well as item ( ii ) of proposition [ prop : lambda_i ] .    from theorem [ thm : stability ] , the optimal value of problem changes piecewise linearly while the optimal solution set of problem changes piecewise constantly as the parameter @xmath25 varies . in addition , by corollary [ crol : stability ] , the optimal values of both the first and second terms of are piecewise constant with respect to changes in the parameter @xmath25 .    we observe from theorem [ thm : staconst ] and [ thm : stability ] that , when @xmath197 , problem share the same optimal solution set @xmath161 as problem if @xmath25 is chosen to be small enough . thus , in the remaining part of this paper , we only focus on the nontrivial case when @xmath327 , where @xmath200 is defined by . in this section we explore the relationship between the constrained problem with @xmath328 and a corresponding special penalty problem . in the case of @xmath37 we shall study the relationship between problem and the least square penalty problem . in the case of @xmath29 , we shall discuss the connections between problem and the following @xmath22-penalty problem @xmath329 in fact , both problems and can be cast into the general penalty problem with @xmath45 defined at @xmath256 , for @xmath53 , as @xmath330    we exhibit the main results of this section in the following theorem . [ thm : leasequv ] for @xmath45 defined by and @xmath328 , let @xmath54 and @xmath83 for @xmath84 be defined by definition [ def : srhoomega ] . let @xmath274 , @xmath302 and @xmath303 for @xmath304 be defined by definition [ def : lambda_i ] . let @xmath331 and @xmath332 . let @xmath200 , @xmath268 and @xmath175 be defined by , and respectively . for @xmath333 , let @xmath334 be the integer such that @xmath335 .    * if @xmath336 and suppose @xmath337 , then @xmath338 further , if @xmath339 , we have @xmath340 for @xmath341 and @xmath342 for @xmath343 . * if @xmath344 , and suppose @xmath345 , then @xmath346 * if @xmath347 , then @xmath348 for any @xmath24 . we first prove item ( i ) . from item ( ii ) of theorem [ thm : stability ] , we have @xmath349 for @xmath341 . by item ( i ) of proposition [ prop : partialeauvalence ] , we get that @xmath350 as @xmath341 . we also obtain that if @xmath339 , @xmath351 for @xmath341 from item ( ii ) of proposition [ prop : partialeauvalence ] . when @xmath352 or @xmath353 , by item ( ii ) of theorem [ thm : stability ] and @xmath354 , we have @xmath355 and @xmath356 for any @xmath357 . since @xmath358 and @xmath227 for all @xmath359 , we get @xmath360 for @xmath352 or @xmath353 . clearly , if @xmath339 , then @xmath361 for @xmath352 or @xmath353 . when @xmath362 $ ] , @xmath356 for @xmath363 and thus @xmath364 . we then prove item ( ii ) . by item ( i ) of proposition [ prop : partialeauvalence ] , @xmath227 for any @xmath217 . from item ( ii ) of theorem [ thm : stability ] , we have @xmath365 due to @xmath345 . then we get item ( ii ) by the fact that @xmath356 for any @xmath366 and for any @xmath367 as @xmath368 . we finally prove item ( iii ) . similarly , we have @xmath227 for any @xmath217 . however , by theorem [ thm : stability ] @xmath356 for any @xmath363 and @xmath24 since @xmath369 . thus we get item ( iii ) . [ remark : p=2 ] in the case of @xmath37 , by proposition [ prop : partialeauvalence ] , if @xmath211 and @xmath336 , then we have @xmath370 when @xmath341 . if @xmath371 , then we have @xmath336 . in such case , item ( i ) of theorem [ thm : leasequv ] holds clearly .    according to item ( iii ) of theorem [ thm : leasequv ] , in general it is possible that problem has * no * common optimal solutions with problem for any @xmath24 . this means that in general problem may not be an exact penalty method for problem . however , in the noiseless case , we show in the next corollary that problem has the same optimal solution set as problem if @xmath25 is large enough . [ coro : least ] let @xmath45 be defined by and @xmath328 . assume the feasible region of problem is nonempty . then , there exists @xmath47 such that problems and with @xmath46 have the same optimal solution set . since the feasible region of problem is nonempty , @xmath372 by definition [ def : srhoomega ] . clearly , problem is exactly problem with @xmath18 . then , @xmath373 in this case . let @xmath274 and @xmath374 , @xmath375 for @xmath376 be defined by definition [ def : lambda_i ] . from item ( ii ) of proposition [ prop : lambda_i ] , @xmath288 and thus @xmath377 . according to item ( i ) of theorem [ thm : leasequv ] , problems and have the same optimal solution set when @xmath378 . set @xmath379 , we then obtain the desired results . in this section , we first establish exact penalty conditions under which problem have the same optimal solution set as problem , provided that @xmath46 for some @xmath47 . based on the conditions developed , we propose several exact penalty formulations for problem .    according to the definition of @xmath139 and @xmath133 in definition [ def : srhoomega ] , the penalty term @xmath380 attains its minimal value at any @xmath137 . we also know that @xmath381 attains its minimal value at any @xmath363 when @xmath281 by item ( ii ) of theorem [ thm : stability ] , where @xmath283 is defined by definition [ def : lambda_i ] . since @xmath45 is nondecreasing , we have @xmath382 for any @xmath220 . then we obtain the following theorem . [ thm : equivalence ] let @xmath45 satisfy h[hypo:1 ] and @xmath53 . suppose the feasible region of problem is nonempty , that is @xmath50 , where @xmath48 is defined by . if @xmath383 then there exists @xmath47 such that problems and with @xmath46 have the same optimal solution set .    since holds , by the definition of @xmath139 and @xmath133 in definition [ def : srhoomega ] , @xmath384 . thus @xmath133 is the optimal solution set of problem . let @xmath379 , where @xmath283 is defined in definition [ def : lambda_i ] . then , from item ( ii ) of theorem [ thm : stability ] , @xmath133 is also the optimal solution set of problem with @xmath46 . then we have that problems and with @xmath46 have the same optimal solution set .    in general , it is not easy to verify condition . the next corollary states a simple and useful condition which also ensures the exact penalty property once @xmath25 is large enough . [ crol : equv ] let @xmath45 satisfy h[hypo:1 ] and @xmath53 . assume that the feasible region of problem is nonempty . if @xmath45 satisfies @xmath385 then there exists @xmath47 such that problems and with @xmath46 have the same optimal solution set . the desired results follows from the fact that condition implies condition . next we present several examples of @xmath45 satisfying condition . for @xmath386 , we denote by @xmath387 the positive part of @xmath388 , that is , @xmath389    given @xmath328 . let scalar function @xmath390 be defined at @xmath256 as @xmath391 . then @xmath392 satisfies h1 and condition . with the choice of @xmath393 , the penalty term in problem becomes @xmath394    the penalty term with @xmath37 is well exploited in penalty method for quadratically constrained @xmath395 minimization with @xmath21 in @xcite . one can easily check that the penalty term is convex but non - differentiable for @xmath328 .    given @xmath328 . let @xmath396 be defined at @xmath256 as @xmath397 then @xmath398 satisfies h1 and condition . with the choice of @xmath399 , the penalty term in problem becomes @xmath400    by choosing @xmath399 , for @xmath37 problem reads as @xmath401 according to corollary [ crol : equv ] , the following proposition concerning the exact penalization of problem holds . [ prop : env ] suppose that the feasible region of problem is nonempty , then the penalty problem shares the same optimal solution set with the constrained problem , provided that @xmath46 for some @xmath47 . in particular , when @xmath18 , problem reduces to the least square penalty problem . from proposition [ prop : env ] , we deduce that has the same optimal solution set as the linear constrained problem when @xmath25 is sufficiently large . this result coincides with that obtained in corollary [ coro : least ] . in addition to the advantage of exact penalization , we prove in the next proposition that the penalty term in is differentiable with a lipschitz continuous gradient . for simplicity , we define @xmath402 at @xmath2 as @xmath403 we denote by @xmath404 the largest singular value of @xmath405 . we also need to recall the notion of firmly nonexpansive . operator @xmath406 is called firmly nonexpansive ( resp . , nonexpansive ) if for all @xmath407 @xmath408 obviously , a firmly nonexpansive operator is nonexpansive . now , we are ready to show @xmath409 is differentiable with a lipshitz continuous gradient .    [ prop : diff ] let @xmath402 be defined by . then function @xmath409 is differentiable with a lipschitz continuous gradient . in particular , for @xmath2    * @xmath410 * @xmath411 is lipschitz continuous with the lipschitz constant @xmath412 . we define @xmath413 , at @xmath414 as @xmath415 obviously , @xmath416 for any @xmath2 . one can check that for any @xmath414 , @xmath417 thus @xmath418 and item ( i ) follows . we next prove item ( ii ) . we first show @xmath419 is nonexpansive . let @xmath420 be the projection operator onto the set @xmath421 . we have @xmath422 . since the set @xmath421 is nonempty closed convex , operator @xmath423 is firmly nonexpansive , by proposition 12.27 in @xcite . thus , @xmath419 is nonexpansive . for any @xmath424 , we have that @xmath425 the above inequality leads to item ( ii ) . as mentioned in the introduction , the differentiability of the penalty term has important effect on the algorithmic design for problem . according to proposition [ prop : diff ] , by choosing @xmath399 , the penalty term is differentiable with a lipschitz continuous gradient in problem for @xmath37 . as a result , we are able to develop efficient numerical algorithms with theoretical convergence guarantee for solving this problem , e.g. , proximal - gradient type algorithms . in this section , we investigate the cardinality of optimal solution sets of problems and . we also discuss the strictness of their optimal solutions as a byproduct . as it is shown in section [ sec : sta ] , optimal solution sets of these two problems are closely related to @xmath204 , for @xmath426 , defined by definition [ def : srhoomega ] . therefore , we shall first consider the cardinality of @xmath204 . the cases of @xmath29 and @xmath37 are discussed in separate subsections , since the analysis and results are different for these two cases .      for the case of @xmath37 , we have the following proposition concerning the cardinality of @xmath204 . [ prop : cardip2 ] for @xmath45 satisfying h[hypo:1 ] and @xmath37 , let @xmath54 and @xmath83 for @xmath84 be defined by definition [ def : srhoomega ] . for @xmath427 , if @xmath428 , then we have @xmath429    by the definition of @xmath204 , we have @xmath227 for any @xmath216 . let @xmath430 . we will first prove that for any @xmath431 , @xmath432 , where @xmath433 .    for @xmath431 , if there doest not exist @xmath216 such that @xmath434 , then we have @xmath435 , that is @xmath436 . otherwise , if there exists @xmath216 such that @xmath434 , we then prove @xmath437 . by the definition of @xmath204 we have @xmath438 for any @xmath439 . by item ( ii ) of lemma [ lemma : lambdastrict ] , we have that @xmath440 for all @xmath441 . then , we get @xmath442 for all @xmath441 due to @xmath443 . thus , @xmath444 , that is @xmath445 . therefore , we get @xmath432 for any @xmath431 . further , since @xmath446 and @xmath447 , we get of this proposition . the next corollary is obtained immediately . [ coro : cardip2 ] for @xmath45 satisfying h[hypo:1 ] and @xmath37 , let @xmath54 and @xmath83 for @xmath84 be defined by definition [ def : srhoomega ] . if @xmath45 is strictly increasing , then @xmath448 for any @xmath427 . we first present an important lemma . to this end , we define , for any @xmath449 and @xmath450 , @xmath451 . for convenience , we adopt an assumption for a vector in @xmath452 . [ hypo:2 ] for a vector @xmath453 , there holds @xmath454 for all @xmath455 . [ lema : l1 ] let @xmath67 an @xmath456 real matrix and @xmath5 . let @xmath457 satisfy @xmath458 . then    * if @xmath459 and @xmath67 satisfies h[hypo:2 ] , then @xmath460 , where @xmath461 ; * if @xmath462 and @xmath463 , then for any @xmath450 , there exists @xmath464 such that @xmath465 .    for simplicity , we set @xmath466 . we first prove item ( i ) . let @xmath467 . obviously @xmath468 . then for any @xmath469 , we set @xmath470 . it is clear that @xmath471 due to h[hypo:2 ] . then we have @xmath472 . therefore , @xmath460 . we get item ( i ) . we next prove item ( ii ) . since @xmath463 , we set @xmath473 , where @xmath474 is the component - wise signum function ( @xmath66 is assigned to @xmath66 ) . set @xmath475 . we have @xmath476 . then there exists @xmath241 such that for any @xmath477 , there holds @xmath478 for any @xmath479 . let @xmath480 and @xmath481 . clearly , @xmath482 . therefore , we have @xmath483 . obviously , @xmath484 is an euclid linear space with dimension no less then @xmath485 . thus , for any @xmath450 , there exists @xmath486 such that @xmath487 . set @xmath488 . then , we have @xmath489 , @xmath478 for @xmath479 and @xmath490 . thus , we have @xmath491 . then , we get this lemma .    now , we are ready to present a proposition on the cardinality of @xmath204 for @xmath29 .    [ prop : cardip1 ] for @xmath45 satisfying h[hypo:1 ] and @xmath29 , let @xmath54 and @xmath83 for @xmath84 be defined by definition [ def : srhoomega ] . for @xmath427 , the following statements hold :    * for @xmath492 , @xmath493 . * for @xmath494 , if @xmath495 , all the columns of @xmath3 satisfy h[hypo:2 ] and @xmath496 , then @xmath497 . * for @xmath494 with @xmath498 or @xmath499 , if there exists @xmath216 such that @xmath500 , then for any @xmath450 there exists @xmath501 such that @xmath439 , therefore , @xmath502 .    item ( i ) follows from the fact that @xmath503 . we next prove item ( ii ) . by the definition of @xmath504 and @xmath495 , we have @xmath505 and @xmath506 for any @xmath507 . since @xmath508 , then we assume @xmath509 satisfies @xmath510 . let @xmath511 for @xmath106 . then @xmath512 . by item ( i ) of lemma [ lema : l1 ] , we have @xmath513 for @xmath106 . then we get item ( ii ) of this proposition . we finally prove item ( iii ) . let @xmath182 and @xmath514 . since @xmath216 , we have @xmath227 and @xmath515 . set @xmath516 . for any @xmath450 , set @xmath517 . then by item ( ii ) of lemma [ lema : l1 ] , there exists @xmath518 such that @xmath519 and @xmath520 . then we have @xmath521 and @xmath522 by the definition of @xmath204 . thus @xmath523 . item ( iii ) follows . this subsection is devoted to the cardinality of the optimal solution set of problem when @xmath37 . we begin with recalling the notion of strict minimizers .    for a function @xmath524 and a set @xmath525 , @xmath526 is a strict minimizer of the problem @xmath527 if there exists @xmath450 such that for any @xmath528 there holds @xmath529 . it is clear that as @xmath530 , @xmath531 and @xmath64 is the unique minimizer of problem . we next only consider the case when @xmath532 . [ thm : strictp2 ] for @xmath533 defined at @xmath39 as @xmath257 and @xmath37 , let @xmath54 and @xmath83 for @xmath84 be defined by definition [ def : srhoomega ] . let @xmath534 , where @xmath200 is defined by . let @xmath535 be defined by . then the following statements are equivalent :    * there exits @xmath202 such that @xmath536 . * @xmath537 for any @xmath217 . * any @xmath359 is a strict minimizer of problem . * @xmath538 is finite . we first prove item ( i ) implies item ( iv ) . by item ( ii ) of theorem [ thm : staconst ] , we have @xmath539 since @xmath536 . then we have @xmath538 is finite due to corollary [ coro : cardip2 ] . thus , we get item ( iv ) . it is obvious that item ( iv ) implies item ( iii ) . we next prove item ( iii ) implies item ( ii ) by contradiction . suppose there exists @xmath540 such that @xmath541 . we will show @xmath146 is not a strict minimizer of problem . let @xmath542 . then there exists @xmath241 such that for any @xmath543 there holds @xmath544 . let @xmath545 . set @xmath546 . then for any @xmath547 we have @xmath548 for @xmath479 and @xmath549 . thus , @xmath550 for any @xmath551 . clearly , @xmath552 . then , for any @xmath450 , there exists @xmath553 , such that @xmath554 , contradicting the fact that @xmath146 is a strict minimizer of problem . therefore , we obtain that item ( iii ) implies item ( ii ) . we finally show that item ( ii ) implies item ( i ) . we also prove it by contradiction . suppose item ( i ) doest not hold . then by item ( i ) of proposition [ prop : partialeauvalence ] , there exists @xmath555 , where @xmath556 and @xmath557 due to item ( iii ) of proposition [ prop : partialeauvalence ] . by item ( ii ) , @xmath558 for any @xmath559 , contradicting the fact that @xmath560 due to the definition of @xmath561 . thus we get item ( ii ) implies item ( i ) . then we complete the proof . the next corollary follows from theorem [ thm : strictp2 ] .    for @xmath533 defined at @xmath39 as @xmath257 and @xmath37 , let @xmath54 and @xmath83 for @xmath84 be defined by definition [ def : srhoomega ] . for @xmath562 , @xmath334 , the following hold :    * there exits @xmath217 such that @xmath7 is not a strict minimizer of problem . * @xmath563 .      in this subsection , we discuss cardinality of optimal solution set of problem when @xmath37 . we state the main results in the following theorem . [ thm : penacarp2 ] for @xmath45 satisfying h[hypo:1 ] and @xmath37 , let @xmath54 and @xmath83 for @xmath84 be defined by definition [ def : srhoomega ] . let @xmath274 , @xmath302 and @xmath303 for @xmath304 be defined by definition [ def : lambda_i ] . let @xmath564 , @xmath565 for @xmath97 and @xmath268 defined by . then for @xmath566 , the following statements hold :    * if @xmath567 , then for any @xmath568 , @xmath569 is finite and any @xmath363 is a strict minimizer of problem . * if @xmath570 and @xmath571 for all @xmath572 , then @xmath573 is finite and any @xmath574 is a strict minimizer of problem . we first prove item ( i ) . since @xmath567 , @xmath575 is finite . by ( ii ) of theorem [ thm : stability ] , we have @xmath576 for any @xmath577 . then we get item ( i ) . we then prove item ( ii ) . since @xmath571 for all @xmath578 , @xmath579 is finite for all @xmath578 . then , by item ( ii ) of theorem [ thm : stability ] , @xmath573 is finite . then we get item ( ii ) of this theorem . a direct and useful consequence of theorem [ thm : penacarp2 ] is presented below . [ coro : penacarp2 ] let @xmath45 satisfy h1 and @xmath37 . if @xmath45 is strictly increasing , then @xmath580 is finite and every @xmath363 is a strict minimizer of problem for any @xmath24 .    with the help of the above corollary , we characterize the cardinality of optimal solution set of problem in the next proposition . our result coincides with that obtained in @xcite . the cardinality of the optimal solution set of problem is finite for any @xmath24 and every optimal solution is a strict minimizer . problem is a special case of problem with @xmath581 for @xmath39 . since in this case @xmath45 is strictly increasing , we obtain the conclusions by corollary [ coro : penacarp2 ] . this subsection provides results on cardinality of optimal solution sets of problems and when @xmath29 . [ thm : probcarp1 ] for @xmath45 satisfying h[hypo:1 ] and @xmath29 , let @xmath54 and @xmath83 for @xmath84 be defined by definition [ def : srhoomega ] . let @xmath274 , @xmath302 and @xmath303 for @xmath304 be defined by definition [ def : lambda_i ] . let @xmath564 . let @xmath268 and @xmath535 be defined by and respectively . then the following statements hold :    * @xmath582 for @xmath583 and @xmath584 . * for @xmath585 with @xmath586 or @xmath587 , if there exists @xmath588 such that @xmath589 , then we have @xmath590 for any @xmath591 and @xmath146 is not a strict minimizer of problem . * suppose @xmath257 for @xmath39 , then @xmath592 for all @xmath562 , @xmath334 ; further , for @xmath593 and @xmath51 satisfying @xmath585 with @xmath594 or @xmath587 , if there exists @xmath595 such that @xmath596 , then we have @xmath597 , and @xmath146 is not a strict minimizer of problem .    by item ( ii ) of theorem [ thm : stability ] and the definition of @xmath598 , item ( i ) follows immediately . by theorem [ thm : stability ] , @xmath599 for @xmath591 . then we have item ( ii ) due to item ( iii ) of proposition [ prop : cardip1 ] . for @xmath562 , @xmath334 , from item ( ii ) of theorem [ thm : staconst ] , @xmath600 . then any @xmath601 satisfies @xmath602 let @xmath603 . similar to the proofs of theorem [ thm : strictp2 ] , for any @xmath450 , there exits @xmath604 such that @xmath605 and @xmath606 . thus , @xmath607 . therefore , @xmath597 for @xmath562 . for @xmath593 , we have @xmath608 . then by item ( iii ) of proposition [ prop : cardip1 ] we obtain item ( iii ) of this theorem . in this section , we provide numerical illustrations for some of our main theoretical findings , including :    * the marginal function of problem is piecewise constant , while that of problem is piecewise linear ; * it is possible that the least square penalty problem has no common optimal solutions with the constrained problem for any @xmath24 ; * there exists @xmath47 such that problem is an exact penalty formulation of the constrained problem for @xmath46 . all the @xmath0 optimization problems involved are solved by an exhaustive combinational search . for better readability , all numerical digits are round to four decimal places . we present in detail a concrete example for sparse signal recovery with @xmath609 as follows @xmath610,\\ \label{eq : x } x^*=\left [ \begin{array}{ccccc } 0 & 1 & 1 & 0 & 0\\ \end{array } \right]^\top,\\ \label{eq : b } b = ax+\eta= \left[\begin{array}{ccccc } 14.43 & 7.21 & 4.49 & 13.02 \end{array}\right]^\top,\end{aligned}\ ] ] where @xmath611 denotes random noise following a nearly normal distribution . the coefficients of @xmath3 , @xmath146 , and @xmath612 in , , and are exact . the noise level of @xmath13 is @xmath613 . as @xmath146 is sparse , we naturally expect recovering @xmath146 by solving problem with @xmath3 , @xmath612 in , and @xmath614 . to this end , we shall first verify that @xmath146 is an optimal solution to problem . let @xmath257 , @xmath615 and @xmath37 . then according to definition [ def : srhoomega ] , we have that @xmath616 , @xmath617 and @xmath618 by theorem [ thm : staconst ] , the marginal function of problem has the form of @xmath619 specially , we find that @xmath620 when @xmath621 . this together with @xmath622 implies that @xmath146 is an optimal solution to problem with @xmath614 . next we consider the least square penalty problem with @xmath3 , @xmath612 in and . by remark [ remark : same ] , in this case the marginal function of problem is @xmath623 where @xmath277 , @xmath192 , @xmath271 , @xmath624 are given in and . then , @xmath274 , @xmath303 for @xmath376 , and @xmath625 for @xmath626 are produced by the iterative procedure in definition [ def : lambda_i ] . we obtain that @xmath627 , @xmath628 @xmath629 @xmath630 the plots of @xmath631 for @xmath280 and their intersection points are depicted in figure [ fig : ex2 ] .    by theorem [ thm : stability ] , @xmath272 in reads as @xmath632 we note that @xmath633 for any @xmath24 . by theorem [ thm : stability ] , we deduce that @xmath634 for any @xmath363 and any @xmath24 . therefore , given @xmath3 , @xmath612 in , , problem has no common optimal solution as problem with @xmath614 for any @xmath24 . in other words , problem fails to recover or approximate the true signal @xmath146 .    in the next numerical test , we discuss penalty problem with @xmath3 , @xmath612 in , and @xmath614 . as shown in section [ sec : equal ] , problem has the same optimal solution set with problem , provided that @xmath46 for some @xmath47 . we shall find the exact numerical value of @xmath635 . set @xmath399 as in . from the iteration in definition [ def : srhoomega ] , we have that @xmath636 , @xmath637 @xmath638 according to the proof of theorem [ thm : equivalence ] , @xmath635 actually equals to @xmath639 produced by the iteration procedure in definition [ def : lambda_i ] . given @xmath640 , @xmath641 in , , @xmath642 , it holds that @xmath643 therefore , we conclude that for @xmath3 , @xmath612 in , and @xmath614 , penalty problem share the same optimal solution set as constrained problem when the penalty parameter @xmath644 . the quadratically constrained @xmath0 regularization problem arises in many applications where sparse solutions are desired . the least square penalty method has been widely used for solving this problem . there is little results regarding properties of optimal solutions to problems and , although these two problems have been well studied mainly from a numerical perspective . in this paper , we aim at investigating optimal solutions of a more general constrained @xmath0 regularization problem and the corresponding penalty problem . we first discuss the optimal solutions of these two problems in detail , including existence , stability with respect to parameter , cardinality and strictness . in particular , we show that the optimal solution set of the penalty problem is piecewise constant with respect to the penalty parameter . then we clarify the relationship between optimal solutions of the two problems . it is proven that , when the noise level @xmath44 there does not always exist a penalty parameter , such that problem and the constrained @xmath0 problem share a common optimal solution . under mild conditions on the penalty function , we prove that problem has the same optimal solution set with problem if the penalty parameter is large enough . with the help of the conditions , we further propose exact penalty problems for the constrained problem . we expect our theoretical findings can offer motivations for the design of innovative numerical schemes for solving constrained @xmath0 regularization problems . [ lemma : lam ] given @xmath45 satisfying h[hypo:1 ] and @xmath53 , let @xmath54 and @xmath83 for @xmath84 be defined by definition [ def : srhoomega ] . let @xmath274 , @xmath302 and @xmath303 for @xmath304 be defined by definition [ def : lambda_i ] . then @xmath645      conversely , for any @xmath652 , @xmath653 for @xmath650 . by the definition of @xmath375 , @xmath654 for @xmath650 and there exists @xmath655 such that @xmath656 . thus , @xmath657 and @xmath658 for @xmath650 . by the definition of @xmath625 , one has @xmath646 . we then prove item ( iii ) . from the definition of @xmath664 , @xmath665 for @xmath659 . then by lemma [ lemma : lam ] , it follows that @xmath666 for any @xmath648 due to @xmath667 . then we have @xmath668 for @xmath648 . according to the definition of @xmath669 , @xmath670 for @xmath659 . item ( iii ) follows immediately . [ lema : lambdai ] given @xmath45 satisfying h[hypo:1 ] and @xmath53 , let @xmath54 and @xmath83 for @xmath84 be defined by definition [ def : srhoomega ] . let @xmath274 , @xmath302 and @xmath303 for @xmath304 be defined by definition [ def : lambda_i ] . for @xmath659 , next we prove item ( iii ) . since @xmath681 , @xmath682 and @xmath683 , it holds that @xmath684 this means that holds for @xmath685 . we assume for @xmath686 , holds when @xmath687 . then we try to show holds as @xmath688 , that is @xmath689 one finds that @xmath690 then follows . therefore , we obtain item ( iii ) immediately .     next , we prove item ( iv ) . item ( ii ) implies that @xmath676 for all @xmath691 . thus , we only need to prove @xmath678 for @xmath692 , which is equivalent to @xmath693 for @xmath692 . by item ( ii ) , for @xmath694 , it holds that @xmath695 for @xmath696 . from the fact that @xmath697 and @xmath698 , we obtain @xmath699 holds for @xmath696 . by items ( i ) and ( iii ) , @xmath700 for @xmath694 . this together with and item ( i ) implies that holds for @xmath679 . [ prop : fi ] given @xmath45 satisfying h[hypo:1 ] and @xmath53 , let @xmath54 and @xmath83 for @xmath84 be defined by definition [ def : srhoomega ] . let @xmath274 , @xmath302 and @xmath303 for @xmath304 be defined by definition [ def : lambda_i ] . let @xmath270 for @xmath97 . then the following statements hold :    * for @xmath701 , @xmath702 for all @xmath703 . * @xmath704 for @xmath701 . * @xmath705 for any @xmath378 and any @xmath706 . * @xmath707 for any @xmath708 and any @xmath709 . * for @xmath710 , there holds @xmath711 for any @xmath712 and any @xmath713 . we first prove items ( i ) and ( ii ) . from the definition of @xmath714 and @xmath715 , for any @xmath703 @xmath716 . item ( i ) is obtained immediately by the definition of @xmath294 for @xmath717 in . item ( ii ) follows from @xmath718 . we next prove item ( iii ) . thanks to items ( ii ) and ( iii ) of proposition [ prop : rhosomega ] , item ( iii ) amounts to @xmath719 for all @xmath720 . it is clear that holds by the definition of @xmath721 in definition [ def : lambda_i ] and @xmath288 .      finally , we prove item ( v ) . by item ( iv ) of lemma [ lema : lambdai ] , @xmath725 for @xmath726 and @xmath727 . thus , @xmath711 for any @xmath728 and any @xmath727 . by the definition of @xmath714 , we have @xmath729 for @xmath730 and @xmath731 . then , it follows that @xmath711 for any @xmath732 and any @xmath733 .        by item ( ii ) of theorem [ thm : exist ] and item ( i ) of proposition [ prop : fi ] , @xmath736 . using this fact , it suffices to show @xmath737 for any @xmath738 . from items ( i ) and ( iv ) of lemma [ lema : lambdai ] , @xmath739 for @xmath740 . by the definition of @xmath625 and @xmath375 , we have @xmath741 for @xmath742 , which implies @xmath737 for @xmath742 . hence @xmath737 for any @xmath738 .      , _ convergence of descent methods for semi - algebraic and tame problems : proximal algorithms , forward - backward splitting , and regularized gauss - seidel methods _ , mathematical programming , 137 ( 2013 ) , pp . 91129 .                                              height 2pt depth -1.6pt width 23pt , _ relationship between the optimal solutions of least squares regularized with @xmath0-norm and constrained by k - sparsity _ , applied and computational harmonic analysis , ( 2016 ) .
the constrained @xmath0 regularization plays an important role in sparse reconstruction . 
 a widely used approach for solving this problem is the penalty method , of which the least square penalty problem is a special case . 
 however , the connections between global minimizers of the constrained @xmath0 problem and its penalty problem have never been studied in a systematic way . 
 this work provides a comprehensive investigation on optimal solutions of these two problems and their connections . 
 we give detailed descriptions of optimal solutions of the two problems , including existence , stability with respect to the parameter , cardinality and strictness . 
 in particular , we find that the optimal solution set of the penalty problem is piecewise constant with respect to the penalty parameter 
 . then we analyze in - depth the relationship between optimal solutions of the two problems . 
 it is shown that , in the noisy case the least square penalty problem probably has no common optimal solutions with the constrained @xmath0 problem for any penalty parameter . under a mild condition on the penalty function 
 , we establish that the penalty problem has the same optimal solution set as the constrained @xmath0 problem when the penalty parameter is sufficiently large . 
 based on the conditions , we further propose exact penalty problems for the constrained @xmath0 problem . 
 finally , we present a numerical example to illustrate our main theoretical results .    optimal solutions , constrained @xmath0 regularization , penalty methods , stability