A simpler approach to weighted â„“ <inf>1</inf> minimization

In this paper, we analyze the performance of weighted ℓ 1 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 ℓ 1 minimization is substantially better than regular ℓ 1 minimization and provide an easy way to calculate the optimal weights. © 2012 IEEE.