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

https://hal.inria.fr/hal-01096266
Contributor : Cédric Herzet <>
Submitted on : Wednesday, December 17, 2014 - 10:18:44 AM
Last modification on : Monday, May 18, 2020 - 2:33:52 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⟩

Share

Metrics

Record views

245

Files downloads

143