Homotopy based algorithms for $\ell_0$-regularized least-squares

Sparse signal restoration is usually formulated as the minimization of a quadratic cost function |y-Ax|_2^2, where A is a dictionary and x is an unknown sparse vector. It is well-known that imposing an \ell_0 constraint leads to an NP-hard minimization problem. The convex relaxation approach has received considerable attention, where the \ell_0-norm is replaced by the \ell_1-norm. Among the many efficient \ell_1 solvers, the homotopy algorithm minimizes |y-Ax|_2^2+λ|x|_1 with respect to x for a continuum of λ's. It is inspired by the piecewise regularity of the \ell_1-regularization path, also referred to as the homotopy path. In this paper, we address the minimization problem |y-Ax|_2^2+λ|x|_0 for a continuum of λ's and propose two heuristic search algorithms for \ell_0-homotopy. Continuation Single Best Replacement is a forward-backward greedy strategy extending the Single Best Replacement algorithm, previously proposed for \ell_0-minimization at a given λ. The adaptive search of the λ-values is inspired by \ell_1-homotopy. \ell_0 Regularization Path Descent is a more complex algorithm exploiting the structural properties of the \ell_0-regularization path, which is piecewise constant with respect to λ. Both algorithms are empirically evaluated for difficult inverse problems involving ill-conditioned dictionaries. Finally, we show that they can be easily coupled with usual methods of model order selection.