Wang, RongrongCompressed Sensing concerns a new class of linear data acquisition protocols that are more efficient than the classical Shannon sampling theorem when targeting at signals with sparse structures. In this thesis, we study the stability of a Statistical Restricted Isometry Property and show how this property can be further relaxed while maintaining its sufficiency for the Basis Pursuit algorithm to recover sparse signals. We then look at the dictionary extension of Compressed Sensing where signals are sparse under a redundant dictionary and reconstruction is achieved by the $\ell_1$ synthesis method. By establishing a necessary and sufficient condition for the stability of $\ell_1$ synthesis, we are able to predict this algorithm's performances under different dictionaries. Last, we construct a class of deterministic sensing matrix for the Dirac-Fourier joint dictionary.DissertationMathematicsInformation scienceCompresseddeterministicDictionaryFourierSensing