Binary Matrices for Compressed Sensing
For an <inline-formula><tex-math notation="LaTeX">$m\times n$</tex-math></inline-formula> binary matrix with <inline-formula><tex-math notation="LaTeX">$d$</tex-math></inline-formula> nonzero elements per column, it is interesting to identify the minimal column degree <inline-formula><tex-math notation="LaTeX">$d$</tex-math> </inline-formula> 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 <italic>nonzero</italic> correlations between normalized columns. The parameter is proved to perform better than the known <italic>coherence </italic> parameter, namely the maximum correlation between normalized columns, when used to estimate the performance of binary matrices with high compression ratios <inline-formula><tex-math notation="LaTeX">$n/m$</tex-math> </inline-formula> and low column degrees <inline-formula><tex-math notation="LaTeX">$d$</tex-math></inline-formula>. By optimizing the proposed parameter, we derive an ideal column degree <inline-formula><tex-math notation="LaTeX"> $d=\lceil \sqrt{m}\rceil$</tex-math></inline-formula>, around which the best recovery performance is expected to be obtained. This is verified by simulations. Given the ideal number <inline-formula><tex-math notation="LaTeX">$d$ </tex-math></inline-formula> 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 <italic>random</italic> binary matrices.