Expander Recovery Performance of Bipartite Graphs With Girth Greater Than 4

You are here

Top Reasons to Join SPS Today!

1. IEEE Signal Processing Magazine
2. Signal Processing Digital Library*
3. Inside Signal Processing Newsletter
4. SPS Resource Center
5. Career advancement & recognition
6. Discounts on conferences and publications
7. Professional networking
8. Communities for students, young professionals, and women
9. Volunteer opportunities
10. Coming soon! PDH/CEU credits
Click here to learn more.

Expander Recovery Performance of Bipartite Graphs With Girth Greater Than 4

By: 
Weizhi Lu; Weiyu Li; Wei Zhang; Shu-Tao Xia

Expander recovery is an iterative algorithm designed to recover sparse signals measured with 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 a 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(n log k) times to exactly k times in serial recovery, and from O(log k) times to exactly one time in parallel recovery.

SPS on Twitter

  • Join SPS President Ahmed Tewfik on Wednesday, 22 September for the IEEE Signal Processing Society Town Hall in conj… https://t.co/31AOCWXvam
  • DEADLINE EXTENDED: The deadline to apply to PROGRESS at ICIP 2021 has been extended to this Thursday, 16 September!… https://t.co/8V2O4lpXr9
  • Voting is now live for the 5-Minute Video Clip Contest! Support SPS students by watching their videos on this year'… https://t.co/PTXiUzRI1u
  • Our newly-formed Synthetic Aperture Standards Committee is now recruiting new members for its initial roster! Check… https://t.co/RcMuQB86kR
  • PROGRESS returns in conjunction with ICIP 2021! Join us 17-18 September for an exciting new program and plenary spe… https://t.co/yJ9rMG73uu

SPS Videos


Signal Processing in Home Assistants

 


Multimedia Forensics


Careers in Signal Processing             

 


Under the Radar