Skip to Main content Skip to Navigation
Preprints, Working Papers, ...

Coherence-based Partial Exact Recovery Condition for OMP/OLS

Cedric Herzet 1 Charles Soussen 2 Jérôme Idier 3 Rémi Gribonval 4 
1 FLUMINANCE - Fluid Flow Analysis, Description and Control from Image Sequences
CEMAGREF - Centre national du machinisme agricole, du génie rural, des eaux et forêts, Inria Rennes – Bretagne Atlantique
4 METISS - Speech and sound data modeling and processing
IRISA - Institut de Recherche en Informatique et Systèmes Aléatoires, Inria Rennes – Bretagne Atlantique
Abstract : We address the exact recovery of the support of a k-sparse vector with Orthogonal Matching Pursuit (OMP) and Orthogonal Least Squares (OLS) in a noiseless setting. We consider the scenario where OMP/OLS have selected good atoms during the first l iterations (l < k) and derive a new sufficient and worst-case necessary condition for their success in k steps. Our result is based on the coherence of the dictionary and relaxes Tropp's well-known condition < 1=(2k 1) to the case where OMP/OLS have a partial knowledge of the support.
Complete list of metadata

Cited literature [31 references]  Display  Hide  Download
Contributor : Cédric Herzet Connect in order to contact the contributor
Submitted on : Friday, November 30, 2012 - 3:57:06 PM
Last modification on : Wednesday, April 27, 2022 - 3:49:07 AM
Long-term archiving on: : Friday, March 1, 2013 - 3:56:34 AM


Files produced by the author(s)


  • HAL Id : hal-00759433, version 1


Cedric Herzet, Charles Soussen, Jérôme Idier, Rémi Gribonval. Coherence-based Partial Exact Recovery Condition for OMP/OLS. 2012. ⟨hal-00759433⟩



Record views


Files downloads