LAUSR

In this paper, we investigate a class of heuristic schemes to solve the NP-hard problem of minimizing $$\ell _0$$ ℓ 0 -norm over a convex set. A well-known approximation is to consider the convex problem of minimizing $$\ell _1$$ ℓ 1 -norm. We are interested in finding improved results in cases where the problem in $$\ell _1$$ ℓ 1 -norm does not provide an optimal solution to the $$\ell _0$$ ℓ 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 $$\ell _1$$ ℓ 1 -norm and ending in a solution of the problem in $$\ell _0$$ ℓ 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.