M Haddou

T Migot

A Smoothing Method for Sparse Optimization over Convex Sets

Keywords:

In this paper, we investigate a class of heuristic schemes to solve the NP-hard problem of minimizing 0-norm over a convex set. A well-known approximation is to consider the convex problem of minimizing 1-norm. We are interested in finding improved results in cases where the problem in 1-norm does not provide an optimal solution to the 0-norm problem. We consider a relaxation technique using a family of smooth concave functions depending on a parameter. Some other relaxations have already been tried in the literature and the aim of this paper is to provide a more general context. This motivation allows deriving new theoretical results that are valid for general constraint set. We use a homotopy algorithm, starting from a solution to the problem in 1-norm and ending in a solution of the problem in 0-norm. The new results are existence of the solutions of the subproblem, convergence of the scheme, a monotonicity of the solutions and an exact penalization theorem independent of the data.

Introduction

Consider a non-empty closed convex set F ⊂ R n + . One should note that the hypothesis of considering a set in the non-negative orthant is not restrictive. It is only assumed to simplify the presentation and to avoid the absolute value in the definition of the problem.

We are interested in finding the sparsest point over this set, which is equivalent to minimize the 0 -norm, i.e. (1) Note that the 0 -norm is not a norm as it does not have the homogeneity property. (P 0 ) is an NP-hard problem as shown in [START_REF] Natarajan | Sparse approximate solutions to linear systems[END_REF]. This problem has several applications and received a considerable interest recently. Sparsity is involved in several domains including signal and image processing statistics [START_REF] Friedman | The elements of statistical learning[END_REF][START_REF] Vapnik | The nature of statistical learning theory[END_REF][START_REF] Tibshirani | Regression shrinkage and selection via the lasso[END_REF], machine learning [START_REF] Bradley | Feature selection via concave minimization and support vector machines[END_REF][START_REF] Mangasarian | Machine learning via polyhedral concave minimization[END_REF][START_REF] Mangasarian | Minimum-support solutions of polyhedral concave programs[END_REF]. The compressed sensing [START_REF] Candes | Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information[END_REF][START_REF] Candès | Stable signal recovery from incomplete and inaccurate measurements[END_REF][START_REF] Candes | Decoding by linear programming[END_REF][START_REF] Chen | Atomic decomposition by basis pursuit[END_REF][START_REF] Donoho | Neighborly polytopes and sparse solutions of underdetermined linear equations[END_REF][START_REF] Donoho | Compressed sensing[END_REF][START_REF] Donoho | Stable recovery of sparse overcomplete representations in the presence of noise[END_REF] has been the most popular application involving sparsity and creating cross-disciplinary attention in recent years and stimulates a plethora of new applications of sparsity. For more details about applications in image and signal modelling as well as a review on related questions see [START_REF] Bruckstein | From sparse solutions of systems of equations to sparse modeling of signals and images[END_REF] or [START_REF] Tropp | Computational methods for sparse solution of linear inverse problems[END_REF].

The problem (P 0 ) being difficult to solve, a classical approximation consists in solving the convex problem in 1 -norm. The 1 -norm is denoted by

∀x ∈ R n , ||x|| 1 = n i=1 |x i |.
(

) 2
The convex problem in 1 -norm is defined by min x∈F ||x|| 1 .

(P 1 )

It can be seen as a convexification of (P 0 ), because the absolute value of x is the convex envelope of s(x) for x ∈ [-1, 1]. Furthermore, (P 1 ) has the benefits that it can be reformulated as a linear program. This approach has been extensively studied in [START_REF] Candes | Stable signal recovery from incomplete and inaccurate measurements[END_REF][START_REF] Candes | Decoding by linear programming[END_REF][START_REF] Chen | Atomic decomposition by basis pursuit[END_REF][START_REF] Donoho | For most large underdetermined systems of linear equations the minimal 1 -norm solution is also the sparsest solution[END_REF][START_REF] Donoho | Uncertainty principles and ideal atomic decomposition[END_REF][START_REF] Fuchs | On sparse representations in arbitrary redundant bases[END_REF][START_REF] Tropp | Just relax: Convex programming methods for identifying sparse signals in noise[END_REF] and in particular with linear inequality constraints. Moreover, several criteria have been found which guarantee that solving (P 1 ) will also solve (P 0 ) under various assumptions involving the coefficients of the matrix A. These criteria, denoted mutual coherence [START_REF] Donoho | Optimally sparse representation in general (nonorthogonal) dictionaries via 1 minimization[END_REF], restricted isometry property [START_REF] Candes | Decoding by linear programming[END_REF], null space property [START_REF] Cohen | Compressed sensing and best k-term approximation[END_REF], exact recovery condition [START_REF] Fuchs | On sparse representations in arbitrary redundant bases[END_REF][START_REF] Tropp | Greed is good: Algorithmic results for sparse approximation[END_REF], and the range space property [START_REF] Zhao | Rsp-based analysis for sparsest and least 1 -norm solutions to underdetermined linear systems[END_REF], show the efficiency of this convex approximation to solve (P 0 ).

A more sophisticated version of this convex formulation and computationally efficient approach consider a reweighted-1 problem as proposed in [START_REF] Candes | Enhancing sparsity by reweighted 1 minimization[END_REF] and later studied in several recent papers, see [START_REF] Asif | Sparse recovery of streaming signals using 1 -homotopy[END_REF][START_REF] Needell | Noisy signal recovery via iterative reweighted l1-minimization[END_REF][START_REF] Xie | Rewighted l1-minimization for sparse solutions to underdetermined linear systems[END_REF][START_REF] Wipf | Iterative reweighted 1 and 2 methods for finding sparse solutions[END_REF][START_REF] Chen | Convergence of the reweighted 1 minimization algorithm for 2p minimization[END_REF][START_REF] Zhao | A new computational method for the sparsest solutions to systems of linear equations[END_REF][START_REF] Zhao | Constructing new weighted 1 -algorithms for the sparsest points of polyhedral sets[END_REF]. It is clear from these references that the study of the convex problem (P 1 ) to solve (P 0 ) is of great importance.

However, formulation (P 1 ) does not solve all the time the initial problem. Consider for instance the following example in two dimension.

Example 0.1. Given a matrix A ∈ R n×n and a vector b ∈ R n such that

A = -0.1 -1 -10 -1 and b = -1 -10 . (3)
Geometrical observation allows to conclude that the solution of problem (P 1 ) is ( 10 11 , 10 11 ) T , while solution of problem (P 0 ) are of the form (0, 10 + ) T and (10 + , 0) T with ≥ 0.

Nonconvex optimization has been one of the main approach to tackle this problem [START_REF] Bi | Exact penalty decomposition method for zeronorm minimization based on mpec formulation[END_REF][START_REF] Feng | Complementarity formulations of l0-norm optimization problems[END_REF][START_REF] Le Thi | Dc approximation approaches for sparse optimization[END_REF][START_REF] Voronin | A new generalized thresholding algorithm for inverse problems with sparsity constraints[END_REF][START_REF] Weston | Use of the zeronorm with linear models and kernel methods[END_REF]. For instance, in [START_REF] Bi | Exact penalty decomposition method for zeronorm minimization based on mpec formulation[END_REF][START_REF] Feng | Complementarity formulations of l0-norm optimization problems[END_REF], the authors proposed a reformulation of the problem as a mathematical program with complementarity constraints. Thresholding algorithms have also some recent popularity in [START_REF] Beck | A fast iterative shrinkage-thresholding algorithm for linear inverse problems[END_REF][START_REF] Blumensath | Gradient pursuits[END_REF][START_REF] Daubechies | An iterative thresholding algorithm for linear inverse problems with a sparsity constraint[END_REF][START_REF] Malioutov | Iterative log thresholding[END_REF][START_REF] Needell | Cosamp: Iterative signal recovery from incomplete and inaccurate samples[END_REF][START_REF] Voronin | A new generalized thresholding algorithm for inverse problems with sparsity constraints[END_REF]. A Difference of Convex (DC) decomposition of the 0 -norm combined with DC Algorithm has been used in [START_REF] Le Thi | Dc approximation approaches for sparse optimization[END_REF]. We are interested here in nonconvex methods to improve the solution we get by solving (P 1 ) in the general case where this approach does not solve the initial problem. In this aim, several concave relaxations of ||.|| 0 have been tried in the literature.

An intuitive approach trying to bridge the gap between the 1 -norm and the 0 -norm has been to study homotopy methods based on the p -norm for 0 ≤ p ≤ 1. This approach has been initiated in [START_REF] Gribonval | Sparse decomposition in unions of bases[END_REF] and later analyzed in [START_REF] Chartrand | Exact reconstruction of sparse signals via nonconvex minimization[END_REF][START_REF] Foucart | Sparsest solutions of underdetermined linear systems via q -minimization for 0 < q ≤ 1[END_REF][START_REF] Fung | Equivalence of minimal 0 and p norm solutions of linear equalities, inequalities and linear programs for sufficiently small p[END_REF][START_REF] Ge | A note on the complexity of l p minimization[END_REF][START_REF] Lai | An unconstrained q minimization with 0 ≤ q ≤ 1 for sparse solution of underdetermined linear systems[END_REF], where the authors prove the link between (P 0 ) and (P 1 ) as well as conditions involving the coefficients of A to show a sufficient convergence condition, so that p does not have to decrease to 0 but only to some small value. The homotopy method considers non-convex subproblems and solving the problem in p is not a trivial task. In [START_REF] Fung | Equivalence of minimal 0 and p norm solutions of linear equalities, inequalities and linear programs for sufficiently small p[END_REF], the authors study a linearization algorithm, while in [START_REF] Ge | A note on the complexity of l p minimization[END_REF] the authors consider an interior-point method to solve the subproblems. Besides, the problem of minimizing the p -norm might lead to numerical difficulties due to the non-differentiability at the origin, in [START_REF] Lai | An unconstrained q minimization with 0 ≤ q ≤ 1 for sparse solution of underdetermined linear systems[END_REF] the authors consider a smoothing of the p -norm to circumvent this problem.

Following the progress made during the last decade in the study of reweighted 1 -norm and p -norm, we study here smooth regularizations. In [START_REF] Mohimani | A fast approach for overcomplete sparse decomposition based on smoothed norm[END_REF] and related works the authors present a general family of smoothing function including the gaussian family and propose a homotopy method starting from the 2 -norm solutions.

Approximating the 0 -norm by smooth functions through an homotopy method starting from the 1 -norm has been studied in the PhD thesis [START_REF] Rinaldi | Mathematical programming methods for minimizing the zeronorm over polyhedral sets[END_REF] and in [START_REF] Lorenzo | A concave optimization-based approach for sparse portfolio selection[END_REF][START_REF] Rinaldi | Concave programming for finding sparse solutions to problems with convex constraints[END_REF][START_REF] Rinaldi | Concave programming for minimizing the zero-norm over polyhedral sets[END_REF]. In these works, the authors consider a selection of minimization problems using smooth functions such that (t + r) p with r > 0 and 0 < p < 1, -(t + r) -p with r > 0 and 1 < p, log(t + r) with 0 < r << 1 or 1 -e -rt with r > 0 and p ∈ N. The subproblems of the homotopy algorithm are solved using a Frank and Wolfe approach [START_REF] Rinaldi | Concave programming for minimizing the zero-norm over polyhedral sets[END_REF], also called SLA in [START_REF] Fung | Equivalence of minimal 0 and p norm solutions of linear equalities, inequalities and linear programs for sufficiently small p[END_REF], and this method is further studied in [START_REF] Liuzzi | Solving \ 0-penalized problems with simple constraints via the frank-wolfe reduced dimension method[END_REF].

The aim of this paper is to pursue the study of smooth concave approximation of the 0 -norm by offering a more general theoretical context for this study. Focusing on concave functions is a logical choice considering that the pnorm is itself concave in R + for 0 ≤ p ≤ 1. The motivation here is to keep the good properties of the method from [START_REF] Rinaldi | Concave programming for minimizing the zero-norm over polyhedral sets[END_REF] and related work, a homotopy method between the 1 -norm and the 0 -norm problems, and smoothness at the origin.

In particular, such a theoretical study has not been done in the literature and allows us to derive a complete theoretical study of the method.

The method considered here is a homotopy method with a parameter r such that the method recovers the 1 -norm problem for r large and the 0 -norm problem for r small. We provide here a complete analysis of the convergence of the algorithm as well as a monotonicity study of the objective function during the iterations of the homotopy scheme. We also prove the existence of the solutions of the subproblems without any boundedness assumption on the constraints.

For the convex problem of minimizing the 1 -norm, we already pointed out that several criteria involving the coefficients of the matrix A guarantee that solving the problem is sufficient to compute a solution to (P 0 ). Such a result guarantees the good behavior of the method. Considering our homotopy algorithm, we show a similar result independently of the constraints that state that it is not necessary to tend r to zero to compute a solution of (P 0 ). It can be seen as an exact penalty result. This property is a key to ensure the interest of the method.

The theoretical results presented here are valid for any non-empty closed convex set F , which make them valid for several smoothing functions but also for several formulations of the problem. This document is organized as follows: Section 1 introduces a general formulation of the relaxation methods using concave functions. Section 2 discusses convergence and monotonicity results leading to a homotopy method. Section 3 proves error estimates and an exact penalization theorem.

A Smoothing Method

We consider a family of smooth functions designed to approximate the 0 -norm. This family has already been used in the different context of complementarity [START_REF] Abdallah | Solving absolute value equation using complementarity and smoothing functions[END_REF][START_REF] Haddou | Smoothing methods for nonlinear complementarity problems[END_REF] and image restoration [START_REF] Bergounioux | A new relaxation method for a discrete image restoration problem[END_REF]. These functions are smooth non-decreasing concave functions such that

θ : R →] -∞, 1[ with θ(t) < 0 if t < 0, θ(0) = 0 and lim t→+∞ θ(t) = 1.
One way to build θ functions is to consider non-increasing probability density functions f : R + → R + and then take the corresponding cumulative distribution function

∀t ≥ 0, θ(t) = t 0 f (x)dx and ∀t < 0, θ(t) < 0.
By definition of f we can verify that

lim t→+∞ θ(t) = +∞ 0 f (x)dx = 1 and θ(0) = 0 0 f (x)dx = 0.
The non-increasing hypothesis on f gives the concavity of θ.

Examples of this family are θ

1 (t) = t/(t + 1) if t ≥ 0 and θ 1 (t) = t if t < 0, θ 2 (t) = 1 -e -t with t ∈ R.
Then using a scaling technique similar to the perspective functions in convex analysis we define θ(t, r) := θ t r for r > 0 and we get θ(0, r) = 0 ∀r > 0 and lim r→0 θ(t, r) = 1 ∀t > 0.

For the previous examples of this family and t ≥ 0 we have θ 1 (t, r) = t/(t + r), θ 2 (t, r) = 1 -e -t/r . The function θ 1 (t, r) will be extensively used in this paper.

Throughout this paper we will consider the concave optimization problem for r > 0 min x∈F n i=1 θ(x i , r).

(P r )

Before moving to the proofs of convergence, we give a result on the existence of solutions of (P r ). The proof relies on an argument similar to the use of asymptotic cones and directions as introduced in [START_REF] Auslender | Asymptotic cones and functions in optimization and variational inequalities[END_REF].

Theorem 1.1. The optimal set of (P r ) for r > 0 is non-empty.

Proof. Since n i=1 θ(x i , r) is bounded below on the closed set F it admits an infimum. Now, assume by contradiction that there exists an unbounded sequence {x n } such that x n ∈ F, ∀n and

lim n→∞ f (x n ) = inf x∈F f (x) < f (x 0 ).
Let {d n } be the sequence defined for all n by

d n := x n -x 0 x n .
This sequence is bounded, therefore it converges, up to a subsequence, to some limit, lim n→∞ d n = lim n→∞ x n / x n = d ∈ F ∞ , where F ∞ denotes the cone of asymptotic directions of F (cf. [START_REF] Auslender | Asymptotic cones and functions in optimization and variational inequalities[END_REF]). Since F is a closed convex set, it holds for all x ∈ F that x + αd ∈ F, ∀α ≥ 0.

Then, since F ⊂ R n + , we obtain that d ≥ 0. Using component-wise monotonicity and continuity assumption on θ gives

lim n→∞ f (x + α n d n ) ≥ f (x), ∀x ∈ F
as long as α n > 0 for all n and the sequence {α n d n } admits some limit. Choosing x = x 0 , α n = x n and d n as defined above, we obtain

lim n→∞ f (x 0 + α n d n ) = lim n→∞ f (x n ) ≥ f (x 0 ),
which is a contradiction with our initial assumption. This completes the proof.

Convergence

In this section, we will show the link between problems (P 0 ), (P 1 ) and (P r ). We denote S * ||.||0 the set of solutions of (P 0 ), S * ||.||1 the set of solutions of (P 1 ) and S * r the set of solutions of (P r ).

Our aim is to illustrate that for r sufficiently large (P r ) is close to (P 1 ) (see Theorem 2.2), and for r sufficiently small (P r ) is close to (P 0 ) (see Theorem 2.1). In this way, we define an homotopy method starting from r large and decreasing r step by step. Thus, we use the convex approximation (P 1 ) and come closer and closer to the problem we want to solve. A monotonicity-kind result of the sequence computed by the homotopy scheme is proved in Theorem 2.3. Finally, Theorem 2.4 shows that this formulation may also be of interest for more complicated objective function than the one in (P 0 ). Theorem 2.1 gives convergence of (P r ) to (P 0 ) for r decreasing to 0. This result is similar to [21, Theorem 2.1], where the authors pointed out that the concavity of the function θ is not required.

Theorem 2.1 (Convergence to 0 -norm). Every limit point of any sequence {x r } r , such that x r ∈ S * r and r ↓ 0, is an optimal solution of (P 0 ). Proof. Given x the limit of the sequence {x r } r , up to a subsequence, and x * ∈ S * ||.||0 . Since F is a closed set one has x ∈ F . Furthermore we have for any r in the corresponding subsequence

i∈supp(x) θ(x r,i , r) ≤ n i=1 θ(x r,i , r) ≤ n i=1 θ(x * i , r) ≤ x * 0 . (4)
Moreover the definition of θ(., r) functions, for r > 0 and t ∈ R n give

n i=1 lim r↓0 θ(t i , r) = ||t|| 0 . (5)
Replacing into (4) we get ||x|| 0 ≤ ||x * || 0 , and the equality follows thanks to the definition of x.

We now give another convergence result from [START_REF] Fung | Equivalence of minimal 0 and p norm solutions of linear equalities, inequalities and linear programs for sufficiently small p[END_REF] and [START_REF] Rinaldi | Concave programming for minimizing the zero-norm over polyhedral sets[END_REF], which adds that the convergence appears in a finite number of iteration in the case, where the feasible set of (P 0 ) is a polyhedron. Proposition 2.1. Given a non-empty polyhedron F ⊂ R n + . Then there exists a r such that for all r ≤ r a vertex of F is an optimal solution of (P 0 ) and (P r≤r ).

Proof. (P r ) is a problem of minimizing a concave function over a polyhedron F. We can use Corollary 32.3.4 of [START_REF] Rockafellar | Convex analysis[END_REF], since there is no half-line in F such that θ(., r) is unbounded below, so the infimum over F is attained and it is attained at one of the extremal points of F .

Given that there is a finite number of extremal point, one vertex, say x , will repeatedly solve (P r ) for some increasing infinite sequence R = (r 0 , r 1 , r 2 , ...). Moreover the objective function of (P r ) is non-increasing and bounded below by the infimum of 0 -norm, so

n i=1 θ(x i , r j ) = min x∈F n i=1 θ(x i , r j ) ≤ inf x∈F ||x|| 0 .
Going through the limit in R for j → ∞ and as the concave function is continuous and x ∈ F , we have the results.

The next theorem shows that for r sufficiently large the solutions of (P r ) are the same than solutions of (P 1 ). This will be especially useful as an initialization of the homotopy scheme.

Theorem 2.2 (Convergence to 1 -norm). Every limit point of any sequence {x r } r , such that x r ∈ S * r for r ↑ ∞, is an optimal solution of (P 1 ).

Proof. As r > 0, we can use a scaling technique for S * (2) r So, it is sufficient to show that every limit point of any sequence {x r } r , such that x r ∈ S * r for r ↑ ∞, is an optimal solution of (P 1 ). Given x r ∈ S * (2) r and x ∈ S * ||.||1 . We use the first order Taylor's theorem for θ(t) in 0,

= arg min

θ(t) = tθ (0) + g(t), where lim t→0 g(t) t = 0. ( 6
)
By concavity of the functions θ, it holds that θ (0) > 0. By definition of x, we get

n i=1 rθ(x r i , r) ≤ n i=1
rθ(x i , r). Now, using (6) yields n i=1

x r i θ (0) + rg(

x r i r ) ≤ n i=1 x r i θ (0) + rg( xi r ), n i=1 x r i - n i=1 xi ≤ r θ (0) n i=1 g( xi r ) - r θ (0) n i=1 g( x r i r ), ≤ 1 θ (0) n i=1 g( xi r ) xi r xi + 1 θ (0) n i=1 g( x r i r ) x r i r x r i , ≤ 1 θ (0) n i=1 g( xi r ) xi r n i=1 xi + 1 θ (0) n i=1 g( x r i r ) x r i r n i=1 x r i , n i=1 x r i ≤ n i=1 xi 1 + 1 θ (0) n i=1 g( xi r ) xi r 1 -1 θ (0) n i=1 g( x r i r )
x r i r .

Then, we show that the right-hand side in previous equation goes to 1, when passing to the limit. It holds true that lim r→+∞ x r = 0. By definition of functions θ, it is true that θ(x, r) := θ(x/r) and θ -1 (0, r) = 0. Thus, by previous equation we obtain

lim r→+∞ x r i r = 0 ∀i. (9)
Using ( 8) and ( 9) it follows

lim r→+∞ xi r = 0 =⇒ lim r→+∞ g( xi r ) xi r = 0, lim r→+∞ x r i r = 0 =⇒ lim r→+∞ g( x r i r )
x r i r = 0.

Then going to the limit in [START_REF] Bi | Exact penalty decomposition method for zeronorm minimization based on mpec formulation[END_REF] yields

lim r→+∞ n i=1 x r i ≤ n i=1 xi . ( 10
)
However, by definition of x, it always hold that

n i=1 xi ≤ n i=1
x i for all x feasible for (P 1 ). Since, this is true for the limit point of the sequence {x r } r , the inequality in [START_REF] Bruckstein | From sparse solutions of systems of equations to sparse modeling of signals and images[END_REF] is actually an equality. So, the limit point of the sequence {x r } r is also a solution of (P 1 ). This proves the result.

The next theorem gives a monotonicity result, which illustrates the relations between the three problems (P 0 ), (P 1 ) and (P r ). By monotonicity, we mean that for a given feasible point we want a relation of monotony in r for the objective function of (P 1 ), (P r ) and (P 0 ). As the components of the 0 -norm and the θ r (t) are in [0, 1[ it is necessary to put the components of 1 -norm in a similar box, which explains the change of variable in the theorem.

Remark 2.1. In the following theorem we use the hypothesis that θ functions are convex in r. This is not so restrictive as we think several functions verify it. If we take the three examples of θ functions given in the introduction, θ 1 and

θ log := log(1 + x)/ log(1 + x + r) are convex in r but not θ 2 . Theorem 2.3 (Monotonicity of solutions). Given x ∈ F , we define y := x/(||x|| ∞ + ) where > 0, so that y ∈ [0, 1[ n . Let a function Ψ(t, r) : [0, 1[→ [0, 1[ be defined as Ψ(t, r) = θ(t, r) θ(1,

r) .

We consider here functions θ that are convex with respect to r. For r and r such that 0 < r < r < +∞, then one has

||y|| 1 ≤ n i=1 Ψ(y i , r) ≤ n i=1 Ψ ( y i , r) ≤ ||y|| 0 .
Proof. The proof is divided in three step regarding the three inequalities.

The functions θ are sub-additive functions, since they concave and θ(0) = 0. Then, it follows θ(y i , r) ≥ y i θ(1, r).

Therefore, we get

n i=1 Ψ(y i , r) -||y|| 1 = n i=1 θ(y i , r) θ(1, r) -y i , ≥ 0,
which leads to the first inequality

||y|| 1 ≤ n i=1 Ψ(y i , r).
We continue with the second inequality showing that Ψ(y, r) functions are nonincreasing in r, i.e.

n i=1 Ψ(y i , r) ≤ n i=1 Ψ(y i , r). ( 11
)
The functions Ψ(y, r) is non-increasing in r if its derivative with respect to r

∂ ∂r Ψ(y, r) = ( ∂ ∂r θ(y, r))θ(1, r) -( ∂ ∂r θ(1, r))θ(y, r) θ(1, r) 2 , (12)
is negative. Since θ(y, r) is an non-decreasing function in y we have

θ(y, r) θ(1, r) < 1,
and

∂ ∂r θ(y, r) = - 1 r 2 , ∂ ∂y θ(y, r) < 0.
So, θ(y, r) is non-increasing function in r. Using convexity of θ(y, r) in r it follows

∂ ∂r θ( y, r) ∂ ∂r θ(1, r) = ∂ ∂r θ(1, r/y) ∂ ∂r θ(1, r) ≥ 1.
Then in [START_REF] Candès | Stable signal recovery from incomplete and inaccurate measurements[END_REF] the derivative with respect to r is negative and we have [START_REF] Candes | Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information[END_REF]. Finally, since θ(y, r) is non-decreasing in y and y ∈ [0, 1[ n one has

||y|| 0 - n i=1 Ψ(y i , r) = n i=1;yi =0 1 - θ(y i , r) θ(1, r) ≥ 0,
which gives the last inequality and completes the theorem.

Remark 2.2. Both choice of scaling parameter in Theorem 2.2 and Theorem 2.3 are linked. In the former, we set that lim r→+∞ r n i=1 θ(x i , r) = n i=1 x i , so evaluating in one dimension and x = 1 we have lim r→+∞ rθ(1, r) = 1 and then we see that r and 1/θ(1, r) have the same behavior for r sufficiently large.

All these results lead us to the general behavior of the method. First, we start from one solution of (P 1 ) then by decreasing parameter r the solution of (P r ) becomes closer to a solution of (P 0 ).

Another approach would be to define a new problem which selects one solution of the possibly many optimal solutions of (P 0 ). We consider the following problem which is a selective version of (P r )

min x∈F n i=1 θ(x i , r) + n i=1 r i 2n+1 x i . (P r-sel )
We will use a lexicographic norm and we note ||y|| lex < ||x|| lex ⇐⇒ ∃i ∈ {1, ..., n}, y i < x i and ∀ 1 ≤ j < i, y j = x j .

In the next theorem we want to choose the solution of (P 0 ) which has the smallest lexicographic norm. From the previous equation it is clear that this optimal solution is unique.

Theorem 2.4 (Convergence of the selective concave problem). We use functions θ such that θ ≥ θ 1 . Given {x r } r the sequence of solutions of (P r-sel ) and x a limit point of this sequence. Then, x is the unique solution of S * ||.||0 such that ∀y ∈ S * ||.||0 , ||x|| lex ≤ ||y|| lex .

Proof. Let x * be an optimal solution of (P 0 ) such that ∀y ∈ S * ||.||0 , ||x * || lex ≤ ||y|| lex and x the limit of a sequence of {x r } r solution of (P r-sel ). So, there exists a r such that for every r < r we have x solution of (P r-sel ), up to a subsequence, and

n i=1 θ(x i , r) + n i=1 r i 2n+1 xi ≤ n i=1 θ(x * i , r) + n i=1 r i 2n+1 x * i ≤ x * 0 + n i=1 r i 2n+1 x * i .
(13) Going to the limit for r ↓ 0 we have

||x|| 0 ≤ ||x * || 0 ,
which is an equality by definition of x * and prove the first part of the theorem. Now we need to verify the selection of the solution. Using that functions θ are bounded by 1, one has

n i=1 (θ(x i , r) -1) + k + n i=1 r i 2n+1 xi ≤ k + n i=1 r i 2n+1 x * i , using that θ ≥ θ 1 n i=1 (θ 1 (x i , r) -1) + n i=1 r i 2n+1 xi ≤ n i=1 (θ(x i , r) -1) + n i=1 r i 2n+1 xi ≤ n i=1 r i 2n+1 x * i .
Now, for r sufficiently small, such that min {i|xi =0} xi ≥ √ r, we have

-k r r + √ r + n i=1 r i 2n+1 xi ≤ n i=1 r i 2n+1 x * i , (14)
where k denotes the optimal value of (P 0 ), i.e. x 0 = x * 0 = k. Dividing by r 1 2n+1 in the previous inequality yields

-k r r 1 2n+1 (r + √ r) + x 1 + n i=2 r i 2n+1 xi ≤ x * 1 + n i=2 r i 2n+1 x * i .
Therefore, going to the limit for r ↓ 0 one has This will definitely prevent us of any kind of monotonicity result such as Theorem 2.3. So, unless S * ||.||0 admits only one solution, the initial point as a solution of (P 1 ) has no chance of being a good initial point. This argument and the fact that this problem looks numerically not advisable lead us not to follow the study of this selective problem.

An Exact Penalization Result

In this section we focus on what happen when r becomes small. We denote card(I) the number of elements in a set I. This lemma gives us a theoretical stopping criterion for the decrease of r, as for r < r = min x r i =0 x r i /k, x r becomes an optimal solution. In the following lemma we look at the consequences in the evaluation of θ. Lemma 3.2. Consider θ functions where θ ≥ θ 1 . Let N k = ||x * || 0 < n be the optimal value of problem (P 0 ) and r = min

x r i =0
x r i /k.

Then one has r ≤ r ⇐⇒ θ( min

x r i =0
x r i , r) ≥ θ 1 ( min

x r i =0 x r i , r) ≥ k k + 1 . (15)
Proof. We first show the equivalence in (15) for θ 1 . Assume that θ 1 ( min

x r i =0 x r i , r) ≥ k k + 1 .
Using the expression of θ 1 , it follows θ 1 ( min

x r i =0 x r i , r) = min x r i =0 x r i min x r i =0 x r i + r ≥ k k + 1 ⇐⇒ min x r i =0 x r i (k + 1) ≥ k( min x r i =0 x r i + r) ⇐⇒ min x r i =0 x r i ≥ kr ⇐⇒ r = min x r i =0 x r i k ≥ r.
Considering the functions θ such that θ ≥ θ 1 , the equivalence follows in the exact same way. This proves the result.

Both previous lemmas lead us to the following theorem, which is an exact penalization result for our method. Theorem 3.1 (Exact Penalization Theorem). Consider θ functions where θ ≥ θ 1 . Let N k = ||x * || 0 < n be the optimal value of problem (P 0 ) and x r ∈ S * r . Then one has θ( min

x r i =0 x r i , r) ≥ k k + 1 =⇒ x r ∈ S * ||.||0 .
Proof. By Lemma 3.2 and with r = min x r i =0 x r i /k one has θ( min

x r i =0 x r i , r) ≥ k k + 1 ⇐⇒ r ≤ r.
Then by Lemma 3.1 and using x r ∈ S * r we have

x r ∈ arg min Finally, using r ≤ r and that k is the optimal value of problem in 0 -norm we have the result.

We use in the previous result the minimum non-zero component of x r , which is logical as we expect that for r sufficiently small the sequence of {min x r i =0 x r i } r should be increasing. The following lemma confirms this behavior. x * i .

Then one has ∀r ≤ r * , x r ∈ S * r =⇒ min

x r i =0
x r i ≤ min

x * i =0
x * i .

Proof. Suppose that min xi =0

x i > min

x * i =0
x * i . Since x r ∈ S * r we have n i=1 θ(x r , r) ≥ n i=1 θ(x r , r * ) > (k + 1)θ( min

x * i =0
x * i , r * ) > (k + 1) * kr * + r * = k, which is in contradiction with the definition of x r .

Conclusion and Outlook

We proposed a class of heuristic schemes to solve the NP-hard problem of minimizing the 0 -norm. These methods have the benefit that they can only improve the solution we get by solving the 1 -norm problem. We analyzed a general scheme of smooth approximation functions, which allows us to derive new results for this kind of method. We gave an existence result, convergence results, an exact penalization theorem. Further studies will investigate the special case where the 1 -norm solves the 0 -norm problem, to find an improved stopping condition. Thanks to several studies, for instance [START_REF] Donoho | Neighborly polytopes and sparse solutions of underdetermined linear equations[END_REF], we have criteria which can help us identify the cases where the solution we get by solving (P 1 ) is an optimal solution of (P 0 ). We wonder if there exists a better sufficient condition than the one presented here in the case where x r ∈ S * ||.||1 ∩ S * r .

  i |), where for t ∈ R, s(t) = {0 if t = 0 ; 1 otherwise}.

Lemma 3 . 1 .

 31 Consider θ functions where θ ≥ θ 1 . Let N k = ||x * || 0 < n be the optimal value of problem (P 0 ) and I(x, r) := {i|x i ≥ kr}. Then one hasx r ∈ arg min x∈F n i=1 θ(x i , r) ⇒ card(I(x r , r)) ≤ k.Proof. We use a proof by contradiction. Consider that card(I(x r , r)) ≥ k + 1 and we have x r ∈ arg min x∈F n i=1 θ(x i , r), then n i=1 θ(x r i , r) ≥ (k + 1)θ(kr, r) ≥ (k + 1)θ 1 (kr, r) = (k + 1)kr kr + r = k,which is a contradiction with the definition of x r .

  i , r) ⇒ card(I(x r , r)) ≤ k.

Lemma 3 . 3 .

 33 Consider θ functions where θ ≥ θ 1 . Let x * ∈ S * ||.||0 , ||x * || 0 = k and r

  If we try to get an equivalent result as in Theorem 2.2 for this selection problem, it is clear that for r sufficiently large we will solve the 1 -norm problem but with a reversed lexicographical order than the one we are looking for, i.e. for a non-decreasing sequence of r j x = lim j→∞ {x rj } rj with x rj ∈ S * rj -sel =⇒ x ∈ S * ||.||1 and x = arg max

	which is an equality by hypothesis on x * being the smallest ||.|| lex solution of
	(P 0 ). So, as x1 = x * 1 in (14) one has
	-k	r r + √	r	+	n i=2	r	i 2n+1 xi ≤	n i=2	r	i 2n+1 x * i .
	By induction we get xi = x * i , ∀i ∈ {1, ..., n} and so x = x * , because we have
	∀j ∈ {1, ..., n}, lim r→0	r	r 2n+1 (r + j	√	r)	= 0.
	Finally we have the results as x is the optimal solution which has the smallest
	lexicographic norm.
	||.|| 1 Remark 2.3. y∈S *	||y|| lex .
						x1 ≤ x * 1