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 bah2013vanishingly. With better bounds we derived a new reduced sample complexity for the number of nonzeros per column of these matrices, precisely d = O(_s(N/s) ); as opposed to the standard d = O((N/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.
READ FULL TEXT