A simpler approach to weighted ℓ_1 minimization

Abstract

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.

Additional details