Joint <formula formulatype="inline"><tex Notation="TeX">k</tex> </formula>-Step Analysis of Orthogonal Matching Pursuit and Orthogonal Least Squares

DOI10.1109/TIT.2013.2238606zbMATH Open1364.94160arXiv1111.0522MaRDI QIDQ2989280FDOQ2989280

Authors: Charles Soussen, J. Idier, C. Herzet, Rémi Gribonval 

Publication date: 8 June 2017

Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)

Abstract: Tropp's analysis of Orthogonal Matching Pursuit (OMP) using the Exact Recovery Condition (ERC) is extended to a first exact recovery analysis of Orthogonal Least Squares (OLS). We show that when the ERC is met, OLS is guaranteed to exactly recover the unknown support in at most k iterations. Moreover, we provide a closer look at the analysis of both OMP and OLS when the ERC is not fulfilled. The existence of dictionaries for which some subsets are never recovered by OMP is proved. This phenomenon also appears with basis pursuit where support recovery depends on the sign patterns, but it does not occur for OLS. Finally, numerical experiments show that none of the considered algorithms is uniformly better than the other but for correlated dictionaries, guaranteed exact recovery may be obtained after fewer iterations for OLS than for OMP.

Full work available at URL: https://arxiv.org/abs/1111.0522

Mathematics Subject Classification ID

Signal theory (characterization, reconstruction, filtering, etc.) (94A12)

Cited In (9)

• Matrix-wise \(\ell_0\)-constrained sparse nonnegative least squares
• Perturbation Analysis of Orthogonal Least Squares
• Required Number of Iterations for Sparse Signal Recovery via Orthogonal Least Squares
• Generalized Orthogonal Matching Pursuit
• A new sufficient condition for sparse recovery with multiple orthogonal least squares
• When does OMP achieve exact recovery with continuous dictionaries?
• Orthogonal Matching Pursuit: A Brownian Motion Analysis
• The sliding Frank–Wolfe algorithm and its application to super-resolution microscopy
• Design and Generalization Analysis of Orthogonal Matching Pursuit Algorithms

This page was built for publication: Joint <formula formulatype="inline"><tex Notation="TeX">$k$</tex> </formula>-Step Analysis of Orthogonal Matching Pursuit and Orthogonal Least Squares

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2989280)