A Signal Dependent Analysis of Orthogonal Least Squares Based on the Restricted Isometry Property

The Orthogonal Least Squares (OLS) is a widespread greedy algorithm for sparse signal approximation or reconstruction. We here address the problem of sufficient condition for exact signal support recovery via OLS. Based on the generalized Wielandt inequality, new bounds on the OLS selection rule are provided that enable a simple approach of the Restricted Isometry Property based analysis of OLS. Since these new bounds naturally take the signal magnitude distribution into account, they allow a derivation of a new relaxed exact support recovery condition in the noise-free case. Moreover, we study their influence on the design of such new conditions in bounded noise and Gaussian noise cases.