In many applications - such as compression, de-noising and source separation - a good and efficient signal representation is characterized by sparsity. This means that many coefficients are close to zero, while only few ones have a non-negligible amplitude. On the other hand, real-world signals - such as audio or natural images - clearly present peculiar structures. In this paper we introduce a global optimization framework that aims at respecting the sparsity criterion while decomposing a signal over an overcomplete, multi-component dictionary. We adopt a probabilistic analysis which can lead to consider the signal internal structure. As an example that fits this framework, we propose the Weighted Basis Pursuit algorithm, based on the solution of a convex, non-quadratic problem. Results show that this method can provide sparse signal representations and sparse m-terms approximations. Moreover, Weighted Basis Pursuit provides a faster convergence compared to Basis Pursuit.