Recovery of exact sparse representations in the presence of noise

The paper extends some recent results on sparse representations of signals in redundant bases developed in the noise-free case to the case of noisy observations. The type of question addressed so far is: given a (n,m)-matrix A with m>n and a vector b=Ax, find a sufficient condition for b to have a unique sparsest representation as a linear combination of the columns of A. The answer is a bound on the number of nonzero entries of, say, x_o, that guarantees that x_o is the unique and sparsest solution of Ax=b with b=Ax_o. We consider the case b=Ax_o+e where x_o satisfies the sparsity conditions requested in the noise-free case and seek conditions on e, a vector of additive noise or modeling errors, under which x_o can be recovered from b in a sense to be defined.