  We consider the recovery of sparse signals subject to sparse interference, as
introduced in Studer et al., IEEE Trans. IT, 2012. We present novel
probabilistic recovery guarantees for this framework, covering varying degrees
of knowledge of the signal and interference support, which are relevant for a
large number of practical applications. Our results assume that the sparsifying
dictionaries are characterized by coherence parameters and we require
randomness only in the signal and/or interference. The obtained recovery
guarantees show that one can recover sparsely corrupted signals with
overwhelming probability, even if the sparsity of both the signal and
interference scale (near) linearly with the number of measurements.
