Stable restoration and separation of approximately sparse signals

This paper develops new theory and algorithms to recover signals that are approximately sparse in some general (i.e., basis, frame, over-complete, or in-complete) dictionary but corrupted by a combination of measurement noise and interference having a sparse representation in a second general dictionary. Particular applications covered by our framework include the restoration of signals impaired by impulse noise, narrowband interference, or saturation, as well as image in-painting, super-resolution, and signal separation. We develop efficient recovery algorithms and deterministic conditions that guarantee stable restoration and separation. Two application examples demonstrate the efficacy of our approach.