Compressive sensing theory based on edge expander graphs

It is a new research direction to explore expander graphs for compressive sensing (CS). Using expander graphs for compressive sensing has several advantages, such as incorporating 0-1 deterministic structure measurement matrices, and fast and accurate recovery of sparse signals by leveraging prior knowledge. In this paper, we extend the notion of expanders with irregular left vertices degrees for non-uniform sampling. Through analyzing the relationship between adjacent matrices in edge expander graph and restricted isometry property (RIP), we obtain the upper limit of the coherence of the adjacent matrices. Based on these results, we design two algorithms for non-uniform sampling and corresponding sparse signal recovery. We evaluate the algorithms with numerical experiments. Finally, the experimental results demonstrate that the proposed non-uniform sampling pattern together with the algorithms have better performances on recovering sparse signals with known support set, as compared to the previous approaches.