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

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

https://hal.inria.fr/hal-02144528
Contributor : Emmanuel Soubies <>
Submitted on : Saturday, October 5, 2019 - 5:59:06 PM
Last modification on : Thursday, October 24, 2019 - 2:44:13 PM

File

Soubies_JMIV_19.pdf
Files produced by the author(s)

Identifiers

Citation

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, In press, ⟨10.1007/s10851-019-00917-9⟩. ⟨hal-02144528v2⟩

Share

Metrics

Record views

54

Files downloads

263