Sparse recovery conditions for Orthogonal Least Squares

Charles Soussen (1) , Rémi Gribonval (2) , Jérôme Idier (3) , Cédric Herzet (4)

1 CRAN - Centre de Recherche en Automatique de Nancy
2 METISS - Speech and sound data modeling and processing
3 IRCCyN - Institut de Recherche en Communications et en Cybernétique de Nantes
4 FLUMINANCE - Fluid Flow Analysis, Description and Control from Image Sequences

We extend Tropp's analysis of Orthogonal Matching Pursuit (OMP) using the Exact Recovery Condition (ERC) to a first exact recovery analysis of Orthogonal Least Squares (OLS). We show that when ERC is met, OLS is guaranteed to exactly recover the unknown support. Moreover, we provide a closer look at the analysis of both OMP and OLS when ERC is not fulfilled. We show that there exist dictionaries for which some subsets are never recovered with OMP. This phenomenon, which also appears with $\ell_1$ minimization, does not occur for OLS. Finally, numerical experiments based on our theoretical analysis show that none of the considered algorithms is uniformly better than the other.

Mots clés: ERC exact recovery condition; Orthogonal Matching Pursuit; Orthogonal Least Squares; Order Recursive Matching Pursuit; Optimized Orthogonal Matching Pursuit; forward selection

Domaines: Automatique / Robotique

Charles Soussen, Rémi Gribonval, Jérôme Idier, Cédric Herzet. Sparse recovery conditions for Orthogonal Least Squares. 2011. ⟨hal-00637003v1⟩