A simpler approach to weighted ℓ1 minimization

In this paper, we analyze the performance of weighted ℓ₁ minimization over a non-uniform sparse signal model by extending the “Gaussian width” analysis proposed in [1]. Our results are consistent with those of [7] which are currently the best known ones. However, our methods are less computationally intensive and can be easily extended to signals which have more than two sparsity classes. Finally, we also provide a heuristic for estimating the optimal weights, building on a more general model presented in [11]. Our results reinforce the fact that weighted ℓ₁ minimization is substantially better than regular ℓ₁ minimization and provide an easy way to calculate the optimal weights.