Sparse Signal Reconstruction via Orthogonal Least Squares

In the field of compressed sensing, Orthogonal least Square is a well known greedy algorithm for sparse signal reconstruction. It has been proved that this algorithm gives stable and speedy recovery as compared to L-norm minimization but at the cost of computation complexity. This paper demonstrates that by dividing orthogonal least square algorithm in sub stages, its complexity can be reduced up to some extent even for the large number of measurements. Compared with the basis pursuit method, the simulation results show that exact and faster reconstruction can be obtained from the implemented greedy algorithm by sampling the k in R measurements where k is Sparsity level and R is the signal dimension. The main goal of this paper is to provide an easy way for implementation of this greedy algorithm.