How to Globally Solve Non-convex Optimization Problems Involving an Approximate ℓ₀ Penalization

For dealing with sparse models, a large number of continuous approximations of the ℓ₀ penalization have been proposed. However, the most accurate ones lead to non-convex opti-mization problems. In this paper, by observing that many such approximations are piecewise rational functions, we show that the original optimization problem can be recast as a multivariate polynomial problem. The latter is then globally solved by using recent optimization methods which consist of building a hierarchy of convex problems. Finally, experimental results illustrate that our method always provides a global optimum of the initial problem for standard ℓ₀ approximations. This is in contrast with existing local algorithms whose results depend on the initialization.