Analyses And Constructions Of Deterministic Measurement Matrices From Error-Correcting Codes

Compressed sensing is an emerging signal sampling method which overcomes the famous Nyquist-Shannon sampling theory when the signal is sparse or compressible.The measurement matrix determines how much information can be sampled and thus its construction is an important problem in compressed sensing.Random measurement matrices have been shown to have good theoretical and empirical performance with high probability.However,their performance is not stable when they have small sizes while they will cost too much storage space if they have large sizes.Therefore,it is necessary to construct measurement matrices which have deterministic performance and are convenient to implement by hardware.Coding theory focuses on how to guarantee the quality of transmitted information in communication systems and it has close relations to compressed sensing.It has been proved by Dimakis et.al.that under 1-minimization recovery,parity-check matrices of good linear codes can be used as provably good measurement matrices for compressed sensing.This paper focuses on the analyses and deterministic constructions of measurement matrices from error-correcting codes and it contains the following contents.The relation between minimum distance,which characterizes the best possible performance of linear codes,and spark,which determines the performance of 0-minimization recovery,has been given in this paper.This paper also presents the relations of minimum BSC pseudoweight and nullspace property,which influence the performance of linear programming decoding and 1-minimization recovery,respectively.The above relation between linear codes and compressed sensing extend and verify the conclusion by Dimakis et.al.In addition,it is also very helpful to the mathematical analysis of the performance of binary measurement matrices.By utilizing the structural features,the performance of binary measurement matrices under 0and 1-minimization is analyzed with the help of spark and nullspace property.The analyzing results are better than those based on coherence and can give some insights on the deterministic constructions of binary matrices.Finally,based on finite geometry and array codes,two classes of binary measurement matrices with good theoretical and empirical performance are constructed.Furthermore,by analyzing the theoretical and empirical performance of their submatrices obtained by removing some extra rows and columns,we find that the proposed matrices have very flexible sizes.Based on the common characteristics of those matrices,a general framework to construct deterministic matrices with flexible sizes has been proposed.In addition,sever examples have been given from Berlekamp-Justensen codes and Latin squares.By theoretical and empirical analyses,it is shown that this kind of deterministic matrices are very flexible in matrix sizes and therefore applicable widely.Meanwhile,most of the proposed matrices have quasi-cyclic structures,thus making the hardware realization convenient and easy.