IRLS for Sparse Recovery Revisited: Examples of Failure and a Remedy

Compressed sensing is a central topic in signal processing with myriad applications, where the goal is to recover a signal from as few observations as possible. Iterative re-weighting is one of the fundamental tools to achieve this goal. This paper re-examines the iteratively reweighted least squares (IRLS) algorithm for sparse recovery proposed by Daubechies, Devore, Fornasier, and G"unt"urk in Iteratively reweighted least squares minimization for sparse recovery, sf Communications on Pure and Applied Mathematics, bf 63(2010) 1--38. Under the null space property of order K, the authors show that their algorithm converges to the unique k-sparse solution for k strictly bounded above by a value strictly less than K, and this k-sparse solution coincides with the unique ℓ1 solution. On the other hand, it is known that, for k less than or equal to K, the k-sparse and ℓ1 solutions are unique and coincide. The authors emphasize that their proof method does not apply for k sufficiently close to K, and remark that they were unsuccessful in finding an example where the algorithm fails for these values of k. In this note we construct a family of examples where the Daubechies-Devore-Fornasier-G"unt"urk IRLS algorithm fails for k=K, and provide a modification to their algorithm that provably converges to the unique k-sparse solution for k less than or equal to K while preserving the local linear rate. The paper includes numerical studies of this family as well as the modified IRLS algorithm, testing their robustness under perturbations and to parameter selection.