Skip to Main content Skip to Navigation
Conference papers

Enhanced Recovery Conditions for OMP/OLS by Exploiting both Coherence and Decay

Cédric Herzet 1 Charles Soussen 2 
1 FLUMINANCE - Fluid Flow Analysis, Description and Control from Image Sequences
IRSTEA - Institut national de recherche en sciences et technologies pour l'environnement et l'agriculture, Inria Rennes – Bretagne Atlantique
Abstract : In this paper, we focus on two popular instances of greedy algorithms, namely orthogonal matching pursuit (OMP) and orthogonal least squares (OLS). The suboptimal nature of OMP and OLS has led many researchers to study conditions under which these procedures succeed in recovering the true sparse vector. This question has been widely addressed for OMP in the recent years, including worst-case uniform and probabilisticanalyses. Although OLS has been known in the literature for a few decades (under different names, exact recovery analysis for OLS have only appeared very recently. Most of the existing works deal with uniform guarantees: these conditions ensure the success of OMP/OLS for a given sparsity level (or a given support) irrespective of the magnitude of the non-zero coefficients. In contrast with these works, we derive new guarantees of success accounting for the decay of the non-zero elements of the sparse vector. Our conditions are expressed in terms of the mutual coherence of the dictionary $\mu$ and encompass, as particular cases, some well-known results of the literature.
Complete list of metadata

Cited literature [15 references]  Display  Hide  Download
Contributor : Cédric Herzet Connect in order to contact the contributor
Submitted on : Wednesday, December 17, 2014 - 10:18:44 AM
Last modification on : Thursday, January 20, 2022 - 5:27:02 PM
Long-term archiving on: : Monday, March 23, 2015 - 2:45:43 PM


Files produced by the author(s)


  • HAL Id : hal-01096266, version 1


Cédric Herzet, Charles Soussen. Enhanced Recovery Conditions for OMP/OLS by Exploiting both Coherence and Decay. international - Traveling Workshop on Interactions between Sparse models and Technology (iTwist'14), Aug 2014, Namur, Belgium. pp.36-37. ⟨hal-01096266⟩



Record views


Files downloads