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