On the construction of sparse matrices from expander graphs

We revisit the asymptotic analysis of probabilistic construction of adjacency matrices of expander graphs proposed in [4]. With better bounds we derived a new reduced sample complexity for the number of nonzeros per column of these matrices, precisely $d=\mathcal{O}({\log }_s(N\mathrm{/}s))$; as opposed to the standard $d=\mathcal{O}(\log (N\mathrm{/}s))$. This gives insights into why using small $d$ performed well in numerical experiments involving such matrices. Furthermore, we derive quantitative sampling theorems for our constructions which show our construction outperforming the existing state-of-the-art. We also used our results to compare performance of sparse recovery algorithms where these matrices are used for linear sketching.