On the construction of sparse matrices from expander graphs

04/24/2018
by   Bubacarr Bah, et al.
0

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

Please sign up or login with your details

Forgot password? Click here to reset