Deterministic Compressed Sensing Using Binary Measurement Matrices

The fundamental objective of compressed sensing is to recover a high dimensional but low complexity vector or matrix from only a few linear measurements. In most of the initial publications in the field of compressed sensing, the emphasis is on using random matrices such as Gaussian, Bernoulli, etc. The limitations of this framework include high memory requirements, and CPU time. This dissertation mainly focuses on binary measurement matrices and highlights the superiority of binary matrices in terms of CPU time, complexity, and the required memory compared to the random measurement matrices. In the first part of the dissertation (Chapter 2), we present a new recovery algorithm for compressed sensing that makes use of binary measurement matrices and achieves exact recovery of ultra sparse vectors, in a single pass and without any iterations. Due to its non-iterative nature, our algorithm is hundreds of times faster than iterative algorithms such as 1-norm minimization, and methods based on expander graphs. Our algorithm can accommodate nearly sparse vectors, in which case it recovers the index set of the largest components, and can also accommodate shot noise measurements. In the second part of the dissertation (Chapter 3), we focus on using binary measurement matrices to solve the problem of compressed sensing while 1-norm minimization (basis pursuit) is considered as the recovery algorithm. We derive new upper and lower bounds on the number of measurements to achieve robust sparse recovery with binary matrices. We prove sufficient conditions for a column-regular binary matrix to satisfy the robust null space property (RNSP) and derive universal lower bounds on the number of measurements that any binary matrix needs to have in order to satisfy the weaker sufficient condition based on the RNSP. Then we show that binary matrices that are bi-adjacency matrices of bipartite graphs of girth six are optimal. Two classes of binary matrices, namely parity check matrices of array codes, and the matrices based on Euler Squares, have girth six and are nearly optimal in the sense of almost satisfying the lower bound. In principle randomly generated Gaussian measurement matrices are “order-optimal”; however in practice, Gaussian matrices require more measurements than binary matrices when n < 106 . We then compare the phase transition behavior of the `1-norm minimization formulation using binary parity check matrix of the array code and the Gaussian matrices, and show that the phase transitions of both matrices are almost the same and the recovery using basis pursuit with binary matrices is hundreds of times faster than with Gaussian matrices. In addition, the required memory is less than when using Gaussian matrices. This suggests that binary matrices are a viable alternative to Gaussian matrices for compressed sensing using basis pursuit. This study can be extended to other recovery algorithms using binary matrices.