The inefficiency of the classical signal acquisition systems where a signal is sampled at the Nyquist rate and then compressed, raises the question that without knowing any prior, can't we directly sense a compressed version of the signal? In a series of papers, it has been shown that under certain conditions for the sensing operation and the signal of interest, a non-adaptive linear sampling scheme called Compressed Sensing (CS) can achieve such objective. Consequently a number of decoders have been proposed to recover a signal from it compressive samples. Two extreme approaches for those decoders are convex relaxation and combinatorial methods. The former approach requires the least number of samples for an exact reconstruction at the price of high complexities while the latter approach has low complexities but requires a higher number of samples for recovery. This thesis targets to design a CS approach which keeps only the best properties of convex relaxation and combinatorial approaches. In particular, we plan to show that, under our proposed sensing operator, a fast combinatorial approach would be an instance of the convex relaxation and thus it inherits all good properties of convex relaxation approaches, namely optimality in sample requirement and robustness in the presence of noise.
Read
