Compressed Sensing of Memoryless Sources : A Deterministic Hadamard Construction

Compressed sensing is a new trend in signal processing for efficient sampling and signal acquisition. The idea is that most real-world signals have a sparse representation in an appropriate basis and this can be exploited to capture the sparse signal by taking only a few linear projections. The recovery is possible by running appropriate low-complexity algorithms that exploit the sparsity (prior information) to reconstruct the signal from the linear projections (posterior information). The main benefit is that the required number of measurements is much smaller than the dimension of the signal. This results in a huge gain in sensor cost (in measurement devices) or a dramatic saving in data acquisition time. However, some difficulties naturally arise in applying the compressed sensing to real-world applications such as robustness issues in taking the linear projections and computational complexity of the recovery algorithm. In this thesis, we design structured matrices for compressed sensing. In particular, we claim that some of the practical difficulties can be reasonably solved by imposing some structure on the measurement matrices. The thesis evolves around the Hadamard matrices which are $\{+1,-1\}$-valued matrices with many applications in signal processing, coding, optics and mathematics. As the title of the thesis implies, there are two main ingredients to this thesis. First, we use a memoryless assumption for the source, i.e., we assume that the nonzero components of the sparse signal are independently generated by a given probability distribution and their position is completely random. This allows us to use tools from probability, information theory and coding theory to rigorously assess the achievable performance. Second, using the mathematical properties of the Hadamard matrices, we design measurement matrices by selecting specific rows of a Hadamard matrix according to a deterministic criterion. We call the resulting matrices ``partial Hadamard matrices''. We design partial Hadamard matrices for three signal models: memoryless discrete signals and sparse signals with linear or sub-linear sparsity. A signal has linear sparsity if the number $k$ of its nonzero components is proportional to $n$, the dimension of signal, whereas it has a sub-linear sparsity if $k$ scales like $O(n^\alpha)$ for some $\alpha \in (0,1)$. We develop tools to rigorously analyze the performance of the proposed constructions by borrowing ideas from information theory and coding theory. We also extend our construction to distributed (multi-terminal) signals. Distributed compressed sensing is a ubiquitous problem in distributed data acquisition systems such as ad-hoc sensor networks. From both a theoretical and an engineering point of view, it is important to know how many measurement per dimension are necessary from different terminals in order to have a reliable estimate of the distributed data. We theoretically analyze this problem for a very simple setup where