Deterministic construction of sparse binary matrices via incremental integer optimization

作者：Zhang, Jun; Yu, Zhu Liang^*; Cen, Ling; Gu, Zhenghui; Lin, Zhiping; Li, Yuanqing

来源：Information Sciences, 2018, 430: 504-518.

DOI：10.1016/j.ins.2017.11.056

• Sparse binary measurement matrices
• Deterministic construction
• Integer optimization
• Mutual coherence

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.

• 出版日期2018-3
• 单位广东工业大学; 华南理工大学