Efficient Circulant Matrix Construction and Implementation for Compressed Sensing

The design of measurement matrices is an important part in compressed sensing (CS). Random matrices superior to incoherence are considered to be optimal measurement matrices to achieve successful recovery. However, they are deficient in memory cost. Structure matrices like circulant matrices are preferred for low-memory cost. Nevertheless, their recovery performance is greatly damaged because of element coherence. In this paper, a new method called different-spaced selection & different-spaced flipping (DSS & DSF) is proposed to modify structure matrices. Based on circulant matrices, regular extraction and symbol flipping imposed on columns of measurement matrices can increase randomness to a large scale. As a result, not only near optimal recovery but also much less memory cost can be achieved. Compared with Gaussian random matrices, the memory cost can be reduced to 4% when measurement matrices based on circulant matrices are in 128 × 512 dimensions. An efficient hardware design and VLSI implementation are also presented at the end of this paper.