[hal-00948313] Homotopy based algorithms for L0-regularized least-squares

Sparse signal restoration is usually formulated as the minimization of a quadratic cost function y-Ax2^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-Ax2^2+lambda x1 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-Ax2^2+lambda x0 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



from HAL : Dernières publications http://ift.tt/12YLAWB