A Greedy Sparse Approximation Algorithm Based On L1-Norm Selection Rules

We propose a new greedy sparse approximation algorithm, called SLS for {\it Single L1 Selection}, that addresses a least-squares optimization problem under a cardinality constraint. The specificity and the increased efficiency of SLS originates from its selection step at each iteration, based on exploiting L1-norm solutions. At each iteration, the regularization path of a least-squares criterion penalized by the L1-norm of the remaining variables is built. Then, one variable is selected according to a scoring function defined over the solution path. Simulation results on difficult sparse deconvolution problems involving a highly correlated dictionary reveal the efficiency of the method, which outperforms popular greedy algorithms when the solution is sparse.