Novel Iterative Reweighted ℓ1 Minimization for Sparse Recovery

Data acquisition and high-dimensional signal processing often require the recovery of sparse representations of signals to minimize the resources needed for data collection. ℓp quasi-norm minimization excels in exactly reconstructing sparse signals from fewer measurements, but it is NP-hard and challenging to solve. In this paper, we propose two distinct Iteratively Re-weighted ℓ1 Minimization (IRℓ1) formulations for solving this non-convex sparse recovery problem by introducing two novel reweighting strategies. These strategies ensure that the ϵ-regularizations adjust dynamically based on the magnitudes of the solution components, leading to more effective approximations of the non-convex sparsity penalty. The resulting IRℓ1 formulations provide first-order approximations of tighter surrogates for the original ℓp quasi-norm objective. We prove that both algorithms converge to the true sparse solution under appropriate conditions on the sensing matrix. Our numerical experiments demonstrate that the proposed IRℓ1 algorithms outperform the conventional approach in enhancing recovery success rate and computational efficiency, especially in cases with small values of p.