Joint k-step analysis of Orthogonal Matching Pursuit and Orthogonal Least Squares

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.

39 pages

References in corpus (2)

• Message Passing Algorithms for Compressed Sensing
• Beyond convergence rates: Exact recovery with Tikhonov regularization with sparsity constraints

Cited by in corpus (10)

• The Sliding Frank-Wolfe Algorithm and its Application to Super-Resolution Microscopy
• Support Recovery with Orthogonal Matching Pursuit in the Presence of Noise: A New Analysis
• Recovery Conditions of Sparse Signals Using Orthogonal Least Squares-Type Algorithms
• Block-Sparse Tensor Recovery
• From State Estimation to Network Reconstruction
• When does OMP achieve exact recovery with continuous dictionaries?
• Blind Orthogonal Least Squares based Compressive Spectrum Sensing
• Efficient Least Residual Greedy Algorithms for Sparse Recovery
• On the Optimality of Backward Regression: Sparse Recovery and Subset Selection
• Matrix-wise ${\ell }_0$-constrained Sparse Nonnegative Least Squares