Sparse recovery decaying signals based on $\ell^{0}$ regularization via PDASC

One of the main tasks for sparse recovery is to develop and analyze computationally tractable algorithms for obtaining sparse solutions of underdetermined linear systems. Jiao et al. (2015) proposed a primal-dual active set with a continuation (PDASC) algorithm for the $\ell^0$-regularized least-squares problem and established finite step global convergence and obtained a sharp estimation error under a certain restricted isometry property (RIP) condition. In this paper, we relax the condition on the RIP constant to be independent of the sparsity level $T$ for a class of signals with a strong decay property. Furthermore, we propose a novel data-driven regularization parameter selection rule. Several numerical examples are presented to verify the efficiency and accuracy of the PDASC algorithm and the data-driven parameter choice rule.