Sparse Expander-like Real-valued Projection (SERP) matrices for compressed sensing

Sparse binary projection matrices are arguably the most commonly used sensing matrices in combinatorial approaches to Compressed Sensing (CS). In this paper, we are interested in properties of Sparse Expander-like Real-valued Projection (SERP) matrices that are constructed by replacing the non-zero entries of sparse binary projection matrices by Gaussian random variables. We prove that these sparse real-valued matrices have a “weak” form of Restricted Isometery Property (RIP). We show that such weak RIP enables this class of matrices to be utilized in all three approaches to the problem of Compressed Sensing, i.e. greedy, geometrical and combinatorial.