Skip to Main content Skip to Navigation
Preprints, Working Papers, ...

A continuous relaxation of the constrained $L_2 − L_0$ problem

Arne Bechensteen 1 Laure Blanc-Féraud 1 Gilles Aubert 2
1 MORPHEME - Morphologie et Images
CRISAM - Inria Sophia Antipolis - Méditerranée , IBV - Institut de Biologie Valrose : U1091, Laboratoire I3S - SIS - Signal, Images et Systèmes
Abstract : We focus on the minimization of the least square loss function under a k-sparse constraint with a 0 pseudo-norm. This is a non-convex, non-continuous and NP-hard problem. Recently, for the penalized form (sum of the least square loss function and a 0 penalty term) a relaxation has been introduced which has strong results in terms of minimizers. This relaxation is continuous and does not change the global minimizers, among other favorable properties. The question that has driven this paper is the following: can a continuous relaxation of the k-sparse constraint problem be developed following the same idea and same steps from the penalized 2 − 0 problem? We calculate the convex envelope of the constrained problem when the observation matrix is orthogonal and propose a continuous non-smooth, non-convex relaxation of the k-sparse constraint functional. We give some equivalence of minimizers between the original and the relaxed problems. The subgradient is calculated as well as the proximal operator of the relaxation, and we propose an algorithm that ensures convergence to a critical point of the k-sparse constraint problem. We apply the algorithm to the problem of single-molecule localization microscopy and compare the results with well-known sparse minimization schemes. The results of the proposed algorithm are as good as the state-of-the-art results for the penalized form, while fixing the constraint constant is usually more intuitive than fixing the penalty parameter.
Document type :
Preprints, Working Papers, ...
Complete list of metadatas
Contributor : Arne Bechensteen <>
Submitted on : Tuesday, January 5, 2021 - 9:26:16 AM
Last modification on : Monday, January 11, 2021 - 11:37:38 AM


Files produced by the author(s)


  • HAL Id : hal-02556394, version 2


Arne Bechensteen, Laure Blanc-Féraud, Gilles Aubert. A continuous relaxation of the constrained $L_2 − L_0$ problem. 2021. ⟨hal-02556394v2⟩



Record views


Files downloads