Matching Pursuit with Block Incoherent Dictionaries

There has been an intense activity recently in the field of sparse approximations with redundant dictionaries, largely motivated by the practical performances of algorithms such as Matching Pursuit and Basis Pursuit. However, most of the theoretical results obtained so far are valid only for the restricted class of incoherent dictionaries. This paper investigates a new class of overcomplete dictionaries, called block incoherent dictionaries, where coherence can be arbitrarily big. We show that a simple greedy algorithm can correctly identify stable subdictionaries (called blocks) and demonstrate how one can use the extra coherence freedom for approximation purposes.