CoSaMP with redundant dictionaries

In this paper we describe a variant of the iterative reconstruction algorithm CoSaMP for the setting where the signal is not sparse in an orthonormal basis but in a truly redundant or overcomplete dictionary. We utilize the D-RIP, a condition on the sensing matrix analogous to the well-known restricted isometry property. In contrast to prior work, the method and analysis are “signal-focused”; that is, they are oriented around recovering the signal rather than its dictionary coefficients. Under the assumption that we have a near-optimal scheme for projecting vectors in signal space onto the model family of candidate sparse signals, we provide provable recovery guarantees. We also provide a discussion of practical examples and empirical results.