Recovery guarantees for restoration and separation of approximately sparse signals

In this paper, we present performance guarantees for the recovery and separation of signals that are approximately sparse in some general (i.e., basis, frame, over-complete, or incomplete) dictionary but corrupted by a combination of measurement noise and interference that is sparse in a second general dictionary. Applications covered by this 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 computationally efficient algorithms for signal restoration and signal separation and present deterministic conditions that guarantee their stability. A simple in-painting example demonstrates the efficacy of our approach.