Deterministic construction of sparse binary matrices via incremental integer optimization

A central problem in compressed sensing (CS) is the design of measurement matrices. Compared with the conventional random matrices, sparse binary matrices have some attractive properties, such as lower storage/encoding cost and easy hardware implementation. In this paper, we formulate the construction of sparse binary measurement matrices from an optimization standpoint. A new algorithm is presented to construct arbitrary-size sparse binary measurement matrices through relaxing the resultant optimization model to an incremental integer programming problem. The proposed method in general outputs sparse binary matrices with optimal mutual coherence. In addition, we prove that the constructed matrices can be almost completely incoherent with the conventional wavelet dictionary. Extensive simulation results show that the sparse binary matrices constructed by the proposed algorithm significantly outperform Gaussian random matrices, random sparse binary matrices and two well-performing deterministic sparse binary matrices.