Homotopy based algorithms for $\ell_0$-regularized least-squares
This work addresses sparse signal restoration for applications like compressed sensing, but it is incremental as it builds on existing ℓ1-homotopy and greedy methods.
The paper tackles the NP-hard problem of sparse signal restoration with an ℓ0 constraint by proposing two heuristic algorithms, Continuation Single Best Replacement and ℓ0 Regularization Path Descent, for ℓ0-homotopy, which are empirically evaluated on difficult inverse problems with ill-conditioned dictionaries.
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.