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

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.
Document type :
Conference papers
Domain :

Cited literature [15 references]

https://hal.inria.fr/hal-01096266
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

### File

itwist14_paper_v3.pdf
Files produced by the author(s)

### Identifiers

• HAL Id : hal-01096266, version 1

### Citation

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