Homotopy based algorithms for L0-regularized least-squares

International audienceSparse 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 L0 constraint leads to an NP-hard minimization problem. The convex relaxation approach has received considerable attention, where the L0-norm is replaced by the L1-norm. Among the many efficient L1 solvers, the homotopy algorithm minimizes ||y-Ax||_2^2+lambda ||x||_1 with respect to x for a continuum of lambda's. It is inspired by the piecewise regularity of the L1-regularization path, also referred to as the homotopy path. In this paper, we address the minimization problem ||y-Ax||_2^2+lambda ||x||_0 for a continuum of lambda's and propose two heuristic search algorithms for L0-homotopy. Continuation Single Best Replacement is a forward-backward greedy strategy extending the Single Best Replacement algorithm, previously proposed for L0-minimization at a given lambda. The adaptive search of the lambda-values is inspired by L1-homotopy. L0 Regularization Path Descent is a more complex algorithm exploiting the structural properties of the L0-regularization path, which is piecewise constant with respect to lambda. 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