Relaxed recovery conditions for OMP/OLS by exploiting both coherence and decay

Cédric Herzet 1 Angélique Drémeau 2 Charles Soussen 3
1 FLUMINANCE - Fluid Flow Analysis, Description and Control from Image Sequences
IRMAR - Institut de Recherche Mathématique de Rennes, IRSTEA - Institut national de recherche en sciences et technologies pour l'environnement et l'agriculture, Inria Rennes – Bretagne Atlantique
Abstract : We propose extended coherence-based conditions for exact sparse support recovery using orthogonal matching pursuit (OMP) and orthogonal least squares (OLS). Unlike standard uniform guarantees, we embed some information about the decay of the sparse vector coefficients in our conditions. As a result, the standard condition $\mu<1/(2k-1)$ (where $\mu$ denotes the mutual coherence and $k$ the sparsity level) can be weakened as soon as the non-zero coefficients obey some decay, both in the noiseless and the bounded-noise scenarios. Furthermore, the resulting condition is approaching $\mu<1/k$ for strongly decaying sparse signals. Finally, in the noiseless setting, we prove that the proposed conditions, in particular the bound $\mu<1/k$, are the tightest achievable guarantees based on mutual coherence.
Type de document :
Article dans une revue
IEEE Transactions on Information Theory, Institute of Electrical and Electronics Engineers, 2016, 62 (1), pp.459-470. 〈10.1109/TIT.2015.2490660〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01058077
Contributeur : Cedric Herzet <>
Soumis le : mardi 26 août 2014 - 09:39:06
Dernière modification le : vendredi 7 décembre 2018 - 01:52:43

Lien texte intégral

Identifiants

Citation

Cédric Herzet, Angélique Drémeau, Charles Soussen. Relaxed recovery conditions for OMP/OLS by exploiting both coherence and decay. IEEE Transactions on Information Theory, Institute of Electrical and Electronics Engineers, 2016, 62 (1), pp.459-470. 〈10.1109/TIT.2015.2490660〉. 〈hal-01058077〉

Partager

Métriques

Consultations de la notice

543