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 .