2012/07/12 by Bubacarr Bah, Jared Tanner, Bah, Bubacarr +1 · 1 citation
Computer Science · Engineering · Materials Science · Mathematics · Medicine · #05C80 #15B52 #42A61 #60F10 (Primary) 94A12 #65F50 #94A20 (Secondary) #Adjacency list #Adjacency matrix #Advanced MRI Techniques and Applications #Algorithm #Cardinality (data modeling) #Combinatorics #Compressed sensing #Computer science #Data compression #Discrete mathematics #Distributed Sensor Networks and Detection Algorithms #Expander graph #FOS: Computer and information sciences #FOS: Mathematics #Graph #Information Theory (cs.IT) #Lanthanide and Transition Metal Complexes #Lossless compression #Mathematics #Numerical Analysis (math.NA) #Probability (math.PR) #Random graph #Sparse and Compressive Sensing Techniques
paper · pdf · doi:10.48550/arxiv.1207.3094
published in arXiv (Cornell University) (Cornell University)
openalex publication_date 2012/07/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We revisit the probabilistic construction of sparse random matrices where\neach column has a fixed number of nonzeros whose row indices are drawn\nuniformly at random with replacement. These matrices have a one-to-one\ncorrespondence with the adjacency matrices of fixed left degree expander\ngraphs. We present formulae for the expected cardinality of the set of\nneighbors for these graphs, and present tail bounds on the probability that\nthis cardinality will be less than the expected value. Deducible from these\nbounds are similar bounds for the expansion of the graph which is of interest\nin many applications. These bounds are derived through a more detailed analysis\nof collisions in unions of sets. Key to this analysis is a novel em dyadic\nsplitting technique. The analysis led to the derivation of better order\nconstants that allow for quantitative theorems on existence of lossless\nexpander graphs and hence the sparse random matrices we consider and also\nquantitative compressed sensing sampling theorems when using sparse non\nmean-zero measurement matrices.\n