Type: Article
Publication Date: 2005-09-26
Citations: 318
DOI: https://doi.org/10.1109/tit.2005.855614
The purpose of this contribution is to extend 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 as follows: given an (n,m)-matrix A with m>n and a vector b=Ax <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">o</sub> , i.e., admitting a sparse representation x <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">o</sub> , find a sufficient condition for b to have a unique sparsest representation. The answer is a bound on the number of nonzero entries in x <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">o</sub> . We consider the case b=Ax <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">o</sub> +e where x <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">o</sub> satisfies the sparsity conditions requested in the noise-free case and e is a vector of additive noise or modeling errors, and seek conditions under which x <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">o</sub> can be recovered from b in a sense to be defined. The conditions we obtain relate the noise energy to the signal level as well as to a parameter of the quadratic program we use to recover the unknown sparsest representation. When the signal-to-noise ratio is large enough, all the components of the signal are still present when the noise is deleted; otherwise, the smallest components of the signal are themselves erased in a quite rational and predictable way