Compressed Sensing Using Binary Matrices of Nearly Optimal Dimensions

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.

Compressed Sensing Using Binary Matrices of Nearly Optimal Dimensions

Mahsa Lotfi; Mathukumalli Vidyasagar

In this paper, we study the problem of compressed sensing using binary measurement matrices and 1 -norm minimization (basis pursuit) as the recovery algorithm. We derive new upper and lower bounds on the number of measurements to achieve robust sparse recovery with binary matrices. We establish sufficient conditions for a column-regular binary matrix to satisfy the robust null space property (RNSP) and show that the associated sufficient conditions for robust sparse recovery obtained using the RNSP are better by a factor of (33 )/22.6  compared to the sufficient conditions obtained using the restricted isometry property (RIP). Next we derive universal lower bounds on the number of measurements that any binary matrix needs to have in order to satisfy the weaker sufficient condition based on the RNSP and show that bipartite graphs of girth six are optimal. Then we display two classes of binary matrices, namely parity check matrices of array codes and Euler squares, which have girth six and are nearly optimal in the sense of almost satisfying the lower bound. In principle, randomly generated Gaussian measurement matrices are “order-optimal.” So we compare the phase transition behavior of the basis pursuit formulation using binary array codes and Gaussian matrices and show that (i) there is essentially no difference between the phase transition boundaries in the two cases and (ii) the CPU time of basis pursuit with binary matrices is hundreds of times faster than with Gaussian matrices and the storage requirements are less. Therefore it is suggested that binary matrices are a viable alternative to Gaussian matrices for compressed sensing using basis pursuit.

SPS on Twitter

  • Join us on Friday, 21 May at 1:00 PM EST when Dr. Amir Asif (York University) shares his journey and the importance…
  • There's still time to apply for PROGRESS! Visit to connect with signal processing leaders a…
  • This Saturday, 8 May, join the SPS JSS Academy of Technical Education Noida Student Branch Chapter in collaboration…
  • The SPACE Webinar Series continues this Tuesday, 4 May at 10:00 AM Eastern when Dr. Lei Tian presents "Modeling and…
  • The second annual IEEE SIGHT Day will take place on 28 April! This year’s theme is “Celebrating 10 years of IEEE SI…

SPS Videos

Signal Processing in Home Assistants


Multimedia Forensics

Careers in Signal Processing             


Under the Radar