Skip to Main content Skip to Navigation
Journal articles

New Insights on the Optimality Conditions of the l2-l0 Minimization Problem

Emmanuel Soubies 1, 2, 3 Laure Blanc-Féraud 4 Gilles Aubert 5
1 IRIT-SC - Signal et Communications
IRIT - Institut de recherche en informatique de Toulouse
4 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 : This paper is devoted to the analysis of necessary (not sufficient) optimality conditions for the l0-regularized least-squares minimization problem. Such conditions are the roots of the plethora of algorithms that have been designed to cope with this NP-hard problem. Indeed, as global optimality is, in general, intractable, these algorithms only ensure the convergence to suboptimal points that verify some necessary optimality conditions. The degree of restrictiveness of these conditions is thus directly related to the performance of the algorithms. Within this context, our first goal is to provide a comprehensive review of commonly used necessary optimality conditions as well as known relationships between them. Then, we complete this hierarchy of conditions by proving new inclusion properties between the sets of candidate solutions associated to them. Moreover, we go one step further by providing a quantitative analysis of these sets. Finally, we report the results of a numerical experiment dedicated to the comparison of several algorithms with different optimality guaranties. In particular, this illustrates the fact that the performance of an algorithm is related to the restrictiveness of the optimality condition verified by the point it converges to.
Complete list of metadatas

Cited literature [52 references]  Display  Hide  Download
Contributor : Emmanuel Soubies <>
Submitted on : Saturday, October 5, 2019 - 5:59:06 PM
Last modification on : Wednesday, October 14, 2020 - 3:39:04 AM


Files produced by the author(s)



Emmanuel Soubies, Laure Blanc-Féraud, Gilles Aubert. New Insights on the Optimality Conditions of the l2-l0 Minimization Problem. Journal of Mathematical Imaging and Vision, Springer Verlag, 2020, Special Issue on Memory of Mila Nikolova, 62, pp.808-824. ⟨10.1007/s10851-019-00917-9⟩. ⟨hal-02144528v2⟩



Record views


Files downloads