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

Terms of use


Views and Downloads






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

TO TOP