New Insights on the Optimality Conditions of the l2-l0 Minimization Problem - Archive ouverte HAL Access content directly
Journal Articles Journal of Mathematical Imaging and Vision Year : 2020

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

(1, 2, 3) , (4) , (5)
1
2
3
4
5

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.
Fichier principal
Vignette du fichier
Soubies_JMIV_19.pdf (480.82 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

hal-02144528 , version 1 (30-05-2019)
hal-02144528 , version 2 (05-10-2019)

Identifiers

Cite

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, 2020, Special Issue on Memory of Mila Nikolova, 62, pp.808-824. ⟨10.1007/s10851-019-00917-9⟩. ⟨hal-02144528v2⟩
566 View
540 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More