Improvement of greedy algorithms for compressive sensing

Compressive Sampling or Compressive Sensing (CS) uses fewer measurements or samples than the Nyquist rate to recover signals or images if they are represented as sparse or compressible. Recovering sparse signals using various greedy algorithms are studied previously. In this thesis, four new greedy pursuit algorithms; Least Support Orthogonal Matching (LS-OMP), Split Signal for Least Support OMP (SS-LSOMP), Multiple Supports of Matching Pursuit (MSMP) and Partially Known Least Support OMP (PKLS-OMP) are introduced to improve the performance of the greedy algorithms. Each algorithm is mathematically proved and confirmed according to its own stop condition. The LS-OMP achieves a correct support recovery without requiring sparse knowledge. For ideal and perfect reconstruction of K-sparse signal, the restricted isometric constant (RIC) of sensing matrix is improved and the upper bound of RIC is relaxed to the new value. Proposed stop condition for Subspace Pursuit (SP) method overcomes best result produced by earlier algorithms. Additionally, the inclusion of partially known support improves the performance of the proposed algorithms and requires fewer samples to achieve reconstruction. Experimental results are presented to demonstrate the performance of the proposed greedy algorithms. Results show that the new algorithms significantly outperform commonly employed reconstruction techniques in both clear and noisy environments.