Homotopy based algorithms for _0-regularized least-squares

Abstract

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 _0 constraint leads to an NP-hard minimization problem. The convex relaxation approach has received considerable attention, where the _0-norm is replaced by the _1-norm. Among the many efficient _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 _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 _0-homotopy. Continuation Single Best Replacement is a forward-backward greedy strategy extending the Single Best Replacement algorithm, previously proposed for _0-minimization at a given . The adaptive search of the -values is inspired by _1-homotopy. _0 Regularization Path Descent is a more complex algorithm exploiting the structural properties of the _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.

Tasks

Reproductions