In this talk, we will discuss the relationships between necessary 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 (not sufficient) optimality conditions. The degree of restrictiveness of these conditions is thus directly related to the performance of the algorithms. Within this context, we will first review the commonly used necessary optimality conditions as well as known relationships between them. Then, we will complete this hierarchy of conditions by proving new inclusion properties between the sets of candidate solutions associated to them. Moreover, we will provide a quantitative analysis of these sets. Finally, we will present numerical experiments that illustrates the fact that the performance of an algorithm is related to the restrictiveness of the optimality condition veried by the point it converges to.

Joint work with Laure Blanc-Féraud and Gilles Aubert.