Expander Recovery Performance of Bipartite Graphs With Girth Greater Than 4
- 21 December 2018
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Signal and Information Processing over Networks
- Vol. 5 (3) , 418-427
Abstract
Expander recovery is an iterative algorithm de- signed to recover sparse signals measured with 0-1 binary matrices with linear complexity. In the paper, we study the expander recovery performance of the bipartite graph with girth greater than 4, which can be associated with a binary matrix with column correlations equal to either 0 or 1. For such graph, expander recovery is proved to achieve the same performance as the traditional basis pursuit recovery, as the signal is dissociated. Compared to random graphs widely used for expander recovery, the graph we study tends to present better empirical performance. Furthermore, its special structure enables reducing the iteration number of expander recovery from O(nlogk) times to exactly k times in serial recovery, and from O(logk) times to exactly one time in parallel recovery.Keywords
Funding Information
- National Natural Science Foundation of China (61801264, 61771273, 61573222)
- Basic Research Program of Shenzhen (JCYJ20170307153635551)
- National Key Research and Development Plan of China (2017YFB1300205)
- Major Research Program of Shandong Province (2018CXGC1503)
- Shandong University
This publication has 44 references indexed in Scilit:
- Explicit constructions of RIP matrices and related problemsDuke Mathematical Journal, 2011
- Precise Undersampling TheoremsProceedings of the IEEE, 2010
- On compressive sensing applied to radarSignal Processing, 2010
- Iterative hard thresholding for compressed sensingApplied and Computational Harmonic Analysis, 2009
- CoSaMP: Iterative signal recovery from incomplete and inaccurate samplesApplied and Computational Harmonic Analysis, 2009
- Deterministic constructions of compressed sensing matricesJournal of Complexity, 2007
- Decoding by Linear ProgrammingIEEE Transactions on Information Theory, 2005
- Explicit Construction of Families of LDPC Codes With No$4$-CyclesIEEE Transactions on Information Theory, 2004
- Sparse representations in unions of basesIEEE Transactions on Information Theory, 2003
- Optimally sparse representation in general (nonorthogonal) dictionaries via ℓ 1 minimizationProceedings of the National Academy of Sciences, 2003