Journal article

### 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. Deduci...

Publication status:
Published

### Access Document

Publisher copy:
10.1109/TIT.2013.2274267

### Authors

More by this author
Institution:
University of Oxford
Division:
MPLS
Department:
Mathematical Institute
Role:
Author
Journal:
IEEE TRANSACTIONS ON INFORMATION THEORY
Volume:
59
Issue:
11
Pages:
7491-7508
Publication date:
2013-11-01
DOI:
EISSN:
1557-9654
ISSN:
0018-9448
Source identifiers:
357784
Language:
English
Keywords:
Pubs id:
pubs:357784
UUID:
uuid:62cb604f-3d95-4244-ab17-30ec0c8904a7
Local pid:
pubs:357784
Deposit date:
2013-12-13