Paper Info
Title
Vanishingly Sparse Matrices and Expander Graphs, With Application to Compressed Sensing
Abstract
We revisit the probabilistic construction of sparse random matrices where each column has a fixed number of nonzeros whose row indices are drawn uniformly at random with replacement. These matrices have a one-to-one correspondence with the adjacency matrices of fixed left degree expander graphs. We present formulas for the expected cardinality of the set of neighbors for these graphs, and present tail bounds on the probability that this cardinality will be less than the expected value. Deducible from these bounds are similar bounds for the expansion of the graph which is of interest in many applications. These bounds are derived through a more detailed analysis of collisions in unions of sets. Key to this analysis is a novel dyadic splitting technique. The analysis led to the derivation of better order constants that allow for quantitative theorems on existence of lossless expander graphs and hence the sparse random matrices we consider and also quantitative compressed sensing sampling theorems when using sparse nonmean-zero measurement matrices.
Year
DOI
Venue
2013
10.1109/TIT.2013.2274267
IEEE Transactions on Information Theory
Keywords
DocType
Volume
algorithms,sparse random matrices,signal processing,expected value,adjacency matrices,sparse matrices,compressed sensing,expander graphs,probabilistic construction,sparse non mean zero measurement matrices,graph theory,dyadic splitting technique,probability
Journal
59
Issue
ISSN
Citations 
11
0018-9448
15
PageRank 
References 
Authors
0.72
15
2
Name
Order
Citations
PageRank
Bubacarr Bah1766.25
Jared Tanner252542.48