Binary Matrices for Compressed Sensing

For an $m\times n$ binary matrix with $d$ nonzero elements per column, it is interesting to identify the minimal column degree $d$ that corresponds to the best recovery performance. Consider this problem is hard to be addressed with currently known performance parameters, we propose a new performance parameter, the average of nonzero correlations between normalized columns. The parameter is proved to perform better than the known coherence parameter, namely the maximum correlation between normalized columns, when used to estimate the performance of binary matrices with high compression ratios $n/m$ and low column degrees $d$ . By optimizing the proposed parameter, we derive an ideal column degree $d=\lceil \sqrt{m}\rceil$ , around which the best recovery performance is expected to be obtained. This is verified by simulations. Given the ideal number $d$ of nonzero elements in each column, we further determine their specific distribution by minimizing the coherence with a greedy method. The resulting binary matrices achieve comparable or even better recovery performance than random binary matrices.