Homotopy Based Algorithms for $\ell _{\scriptscriptstyle 0}$-Regularized Least-Squares
Sparse signal restoration is usually formulated as the minimization of a quadratic cost function |y-Ax ||2<sup>2</sup> where \mbi A is a dictionary and \mbi x is an unknown sparse vector. It is well-known that imposing an ℓ<sub>0</sub> constraint leads to an NP-hard minimization problem. The convex relaxation approach has received considerable attention, where the ℓ<sub>0</sub>-norm is replaced by the ℓ<sub>1</sub>-norm. Among the many effective ℓ<sub>1</sub> solvers, the homotopy algorithm minimizes ||y-Ax ||2<sup>2</sup>+λ||x||<sub>1</sub> with respect to x for a continuum of λ's. It is inspired by the piecewise regularity of the ℓ<sub>1</sub>-regularization path, also referred to as the homotopy path. In this paper, we address the minimization problem ||y-Ax||2<sup>2</sup>+λ||x||<sub>0</sub> for a continuum of λ's and propose two heuristic search algorithms for ℓ<sub>0</sub>-homotopy. Continuation Single Best Replacement is a forward-backward greedy strategy extending the Single Best Replacement algorithm, previously proposed for ℓ<sub>0</sub>-minimization at a given λ. The adaptive search of the λ-values is inspired by ℓ<sub>1</sub>-homotopy. ℓ<sub>0</sub> Regularization Path Descent is a more complex algorithm exploiting the structural properties of the ℓ<sub>0</sub>-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.