Recovery Conditions of Sparse Representations in the Presence of Noise.

When seeking a representation of a signal on a redundant basis one generally replaces the quest for the sparsest model by an l₁ minimization and solves thus a linear program. In the presence of noise one has in addition to replace the exact reconstruction constraint by an approximate one. We consider simultaneously several ways to allow for reconstruction errors and analyze precisely under which conditions exact recovery is possible in the absence of noise. These are then also the conditions that allow recovery in presence of noise in case of large signal to noise ratio. We illustrate the results on an example that shows that the chances of recovery do indeed depend upon the criterion