Recent results have underlined the importance of incoherence in redundant dictionaries for a good behavior of decomposition algorithms like Matching and Basis Pursuits. However, appropriate dictionaries for a given application may not necessarily be able to meet the incoherence condition. In such case, decomposition algorithms may completely fail in the retrieval of the sparsest approximation. This paper studies the effect of introducing a priori knowledge when recovering sparse approximations over redundant dictionaries. Theoretical results show how the use of reliable a priori information (which in this work appears under the form of weights) can improve the performances of standard approaches such as greedy algorithms and relaxation methods. Our results reduce to the classical case when no a priori information is available. Examples validate and illustrate our theoretical statements.