Sparsity optimization and RRSP-based theory far l-bit compressive sensing

Due to the fact that only a few significant components can capture the key information of the signal, acquiring a sparse representation of the signal can be interpreted as finding a sparsest solution to an underdetermined system of linear equations. Theoretical results obtained from studying the sparsest solution to a system of linear equations provide the foundation for many practical problems in signal and image processing, sample theory, statistical and machine learning, and error correction. The first contribution of this thesis is the development of sufficient conditions for the uniqueness of solutions of the partial l\(_0\)-minimization, where only a part of the solution is sparse. In particular, l\(_0\)-minimization is a special case of the partial l\(_0\)-minimization. To study and develop uniqueness conditions for the partial sparsest solution, some concepts, such as l\(_p\)-induced quasi-norm, maximal scaled spark and maximal scaled mutual coherence, are introduced. The main contribution of this thesis is the development of a framework for l-bit compressive sensing and the restricted range space property based support recovery theories. The l-bit compressive sensing is an extreme case of compressive sensing. We show that such a l-bit framework can be reformulated equivalently as an l\(_0\)-minimization with linear equality and inequality constraints. We establish a decoding method, so-called l-bit basis pursuit, to possibly attack this l-bit l\(_0\)-minimization problem. The support recovery theories via l-bit basis pursuit have been developed through the restricted range space property of transposed sensing matrices. In the last part of this thesis, we study the numerical performance of l-bit basis pursuit. We present simulation results to demonstrate that l-bit basis pursuit achieves support recovery, approximate sparse recovery and cardinality recovery with Gaussian matrices and Bernoulli matrices. It is not necessary to require that the sensing matrix be underdetermined due to the single-bit per measurement assumption. Furthermore, we introduce the truncated l-bit measurements method and the reweighted l-bit l\(_1\)-minimization method to further enhance the numerical performance of l-bit basis pursuit