Journal article icon

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

Expand abstract
Publication status:
Published

Actions


Access Document


Publisher copy:
10.1109/TIT.2013.2274267

Authors


More by this author
Institution:
University of Oxford
Department:
Oxford, MPLS, Mathematical Inst
Journal:
IEEE TRANSACTIONS ON INFORMATION THEORY
Volume:
59
Issue:
11
Pages:
7491-7508
Publication date:
2013-11-05
DOI:
EISSN:
1557-9654
ISSN:
0018-9448
URN:
uuid:62cb604f-3d95-4244-ab17-30ec0c8904a7
Source identifiers:
357784
Local pid:
pubs:357784

Terms of use


Metrics



If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP