Unrecoverable subsets by OMP and Basis Pursuit - Inria - Institut national de recherche en sciences et technologies du numérique Access content directly
Conference Papers Year : 2013

Unrecoverable subsets by OMP and Basis Pursuit

Abstract

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.

Domains

Automatic
Fichier principal
Vignette du fichier
unrecov.pdf (28.11 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

hal-00811641 , version 1 (25-04-2013)

Identifiers

  • HAL Id : hal-00811641 , version 1

Cite

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⟩
772 View
179 Download

Share

Gmail Facebook X LinkedIn More