Homotopy based algorithms for ${\ell }_0$-regularized least-squares

Abstract

Sparse signal restoration is usually formulated as the minimization of a quadratic cost function $\Vert y-Ax{\Vert }_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 $\Vert y-Ax{\Vert }_2^2+\lambda \Vert x{\Vert }_1$ with respect to x for a continuum of $\lambda$'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 $\Vert y-Ax{\Vert }_2^2+\lambda \Vert x{\Vert }_0$ for a continuum of $\lambda$'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 $\lambda$. The adaptive search of the $\lambda$-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 $\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.

38 pages

References in corpus (1)

• A fast approach for overcomplete sparse decomposition based on smoothed L0 norm

Cited by in corpus (8)

• Sparse Regularization via Convex Analysis
• The Sliding Frank-Wolfe Algorithm and its Application to Super-Resolution Microscopy
• Enhanced Sparsity by Non-Separable Regularization
• Newton method for ${\ell }_0$-regularized optimization
• Bayesian $l_0$-regularized Least Squares
• Constraint matrix factorization for space variant PSFs field restoration
• Sparse and Imperceptible Adversarial Attack via a Homotopy Algorithm
• Greedy Signal Space Recovery Algorithm with Overcomplete Dictionaries in Compressive Sensing