Unrecoverable subsets by OMP and Basis Pursuit

Charles Soussen (1) , Cédric Herzet (2) , Jérôme Idier (3) , Rémi Gribonval (4)

1 CRAN - Centre de Recherche en Automatique de Nancy
2 FLUMINANCE - Fluid Flow Analysis, Description and Control from Image Sequences
3 IRCCyN - Institut de Recherche en Communications et en Cybernétique de Nantes
4 PANAMA - Parcimonie et Nouveaux Algorithmes pour le Signal et la Modélisation Audio

There is an extensive literature dedicated to the exact recovery of a given subset by Orthogonal Matching Pursuit (OMP) and Basis Pursuit (BP). We consider Tropp's exact recovery condition (ERC) for OMP and the null-space property for BP. Under these conditions, any sparse representation indexed by the subset can be recovered. We address the bad recovery issue, i.e., the opposite extreme situation where the subset cannot be recovered for any amplitude values. We elaborate the bad recovery conditions (BRC) recently sketched in [Soussen et al, 2013]. The BRC dedicated to BP is a direct consequence of the null-space property. It does not depend on the amplitudes, but only on the sign pattern. For OMP, this is not the case, and the BRC condition is not directly related to the ERC. The BRC conditions are tested for deterministic dictionaries corresponding to low pass filtering operators. We stress that the BRC of OMP may be frequently met for supports of low cardinality.

Domaines: Automatique / Robotique

Charles Soussen, Cédric Herzet, Jérôme Idier, Rémi Gribonval. Unrecoverable subsets by OMP and Basis Pursuit. Signal Processing with Adaptive Sparse Structured Representations, SPARS 2013, Jul 2013, Lausanne, Switzerland. ⟨hal-00811641⟩