Sparse dual frames in compressed sensing

A notion of sparse dual frames for a given non-exact frame is introduced. The sparse dual frame is motivated in a study of compressed sensing problems where signal are sparse with respect to a redundant and coherent dictionary (frames). A sparse-dual-based 1-analysis is thereby proposed. We show that sparse dual frames are locally stable. An error bound ensuring the correct signal recovery is obtained. More importantly, solutions to very hard problems in compressed sensing with redundant dictionaries that are otherwise completely unsuccessful by known algorithms of 1-synthesis and the 1-analysis are seen as satisfactory, by the new sparse-dual-based approach and an alternating iterative algorithm that we propose. Examples are provided.