Tight Performance Bounds for Compressed Sensing With Conventional and Group Sparsity

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.

Tight Performance Bounds for Compressed Sensing With Conventional and Group Sparsity

Shashank Ranjan; Mathukumalli Vidyasagar

In this paper, we study the problem of recovering a group sparse vector from a small number of linear measurements. In the past, the common approach has been to use various “group sparsity-inducing” norms such as the Group LASSO norm for this purpose. By using the theory of convex relaxations, we show that it is also possible to use 1 -norm minimization for group sparse recovery. We introduce a new concept called group robust null space property (GRNSP), and show that, under suitable conditions, a group version of the restricted isometry property (GRIP) implies the GRNSP, and thus leads to group sparse recovery. When all groups are of equal size, our bounds are sometimes less conservative than known bounds. Moreover, our results apply even to situations where the groups have different sizes. When specialized to conventional sparsity, our bounds reduce to one of the well-known “best possible” conditions for sparse recovery. This relationship between GRNSP and GRIP is new even for conventional sparsity, and substantially streamlines the proofs of some known results. Using this relationship, we derive bounds on the p-norm of the residual error vector for all p ∈ [1, 2], and not just when p = 2. When the measurement matrix consists of random samples of a sub-Gaussian random variable, we present bounds on the number of measurements, which are sometimes less conservative than currently known bounds. 

SPS on Twitter

  • Registration is now live for the 2020 IEEE 6th World Forum on Internet of Things! Meet attendees from industry, the… https://t.co/1T7vQhAazS
  • Early bird registration for ends on Monday, 24 February. Register today and save, and save even more with… https://t.co/dzlSXdN4y8
  • The IEEE Journal of Selected Topics in Signal Processing is now accepting original manuscripts for a Special Issue… https://t.co/mXKh41of5A
  • Join us on Tuesday, 25 February for a new webinar, “Enabling Identity-Based Integrity Auditing and Data Sharing Wit… https://t.co/rfpjVkEv09
  • The 2020 IEEE International Conference on Autonomous Systems will take place in Montréal on 12-14 August 2020 and w… https://t.co/ePFEWYagwP

SPS Videos

Signal Processing in Home Assistants


Multimedia Forensics

Careers in Signal Processing             


Under the Radar