The simplest measurement matrix for compressed sensing of natural images

There exist two main problems in currently existing measurement matrices for compressed sensing of natural images, the difficulty of hardware implementation and low sensing efficiency. In this paper, we present a novel simple and efficient measurement matrix, Binary Permuted Block Diagonal (BPBD) matrix. The BPBD matrix is binary and highly sparse (all but one or several “1”s in each column are “0”s). Therefore, it can simplify the compressed sensing procedure dramatically. The proposed measurement matrix has the following advantages, which cannot be entirely satisfied by existing measurement matrices. (1) It has easy hardware implementation because of the binary elements; (2) It has high sensing efficiency because of the highly sparse structure; (3) It is incoherent with different popular sparsity basis' like wavelet basis and gradient basis; (4) It provides fast and nearly optimal reconstructions. Moreover, the simulation results demonstrate the advantages of the proposed measurement matrix.