This paper studies the problem of sparse signal approximation over redundant dictionaries. Our attention is focused on the minimization of a cost function where the error is measured by using the L1 norm, giving thus less importance to outliers. We show a constructive equivalence between the proposed minimization problem and Linear Programming. A recovery condition is then provided and an example illustrates the use of such a technique for denoising.