Universal Measurement Bounds for Structured Sparse Signal Recovery

Nikhil Rao, Ben Recht, Robert Nowak
Proceedings of the Fifteenth International Conference on Artificial Intelligence and Statistics, PMLR 22:942-950, 2012.

Abstract

Standard compressive sensing results state that to exactly recover an s sparse signal in Rp, one requires O(s log p) measurements. While this bound is extremely useful in practice, often real world signals are not only sparse, but also exhibit structure in the sparsity pattern. We focus on group-structured patterns in this paper. Under this model, groups of signal coefficients are active (or inactive) together. The groups are prede- fined, but the particular set of groups that are active (i.e., in the signal support) must be learned from measurements. We show that exploiting knowledge of groups can further reduce the number of measurements required for exact signal recovery, and derive universal bounds for the number of measurements needed. The bound is universal in the sense that it only depends on the number of groups under consideration, and not the particulars of the groups (e.g., compositions, sizes, ex- tents, overlaps, etc.). Experiments show that our result holds for a variety of overlapping group configurations.

Cite this Paper

BibTeX
@InProceedings{pmlr-v22-rao12, title = {Universal Measurement Bounds for Structured Sparse Signal Recovery}, author = {Rao, Nikhil and Recht, Ben and Nowak, Robert}, booktitle = {Proceedings of the Fifteenth International Conference on Artificial Intelligence and Statistics}, pages = {942--950}, year = {2012}, editor = {Lawrence, Neil D. and Girolami, Mark}, volume = {22}, series = {Proceedings of Machine Learning Research}, address = {La Palma, Canary Islands}, month = {21--23 Apr}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v22/rao12/rao12.pdf}, url = {https://proceedings.mlr.press/v22/rao12.html}, abstract = {Standard compressive sensing results state that to exactly recover an s sparse signal in Rp, one requires O(s log p) measurements. While this bound is extremely useful in practice, often real world signals are not only sparse, but also exhibit structure in the sparsity pattern. We focus on group-structured patterns in this paper. Under this model, groups of signal coefficients are active (or inactive) together. The groups are prede- fined, but the particular set of groups that are active (i.e., in the signal support) must be learned from measurements. We show that exploiting knowledge of groups can further reduce the number of measurements required for exact signal recovery, and derive universal bounds for the number of measurements needed. The bound is universal in the sense that it only depends on the number of groups under consideration, and not the particulars of the groups (e.g., compositions, sizes, ex- tents, overlaps, etc.). Experiments show that our result holds for a variety of overlapping group configurations.} }
Endnote
%0 Conference Paper %T Universal Measurement Bounds for Structured Sparse Signal Recovery %A Nikhil Rao %A Ben Recht %A Robert Nowak %B Proceedings of the Fifteenth International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2012 %E Neil D. Lawrence %E Mark Girolami %F pmlr-v22-rao12 %I PMLR %P 942--950 %U https://proceedings.mlr.press/v22/rao12.html %V 22 %X Standard compressive sensing results state that to exactly recover an s sparse signal in Rp, one requires O(s log p) measurements. While this bound is extremely useful in practice, often real world signals are not only sparse, but also exhibit structure in the sparsity pattern. We focus on group-structured patterns in this paper. Under this model, groups of signal coefficients are active (or inactive) together. The groups are prede- fined, but the particular set of groups that are active (i.e., in the signal support) must be learned from measurements. We show that exploiting knowledge of groups can further reduce the number of measurements required for exact signal recovery, and derive universal bounds for the number of measurements needed. The bound is universal in the sense that it only depends on the number of groups under consideration, and not the particulars of the groups (e.g., compositions, sizes, ex- tents, overlaps, etc.). Experiments show that our result holds for a variety of overlapping group configurations.
RIS
TY - CPAPER TI - Universal Measurement Bounds for Structured Sparse Signal Recovery AU - Nikhil Rao AU - Ben Recht AU - Robert Nowak BT - Proceedings of the Fifteenth International Conference on Artificial Intelligence and Statistics DA - 2012/03/21 ED - Neil D. Lawrence ED - Mark Girolami ID - pmlr-v22-rao12 PB - PMLR DP - Proceedings of Machine Learning Research VL - 22 SP - 942 EP - 950 L1 - http://proceedings.mlr.press/v22/rao12/rao12.pdf UR - https://proceedings.mlr.press/v22/rao12.html AB - Standard compressive sensing results state that to exactly recover an s sparse signal in Rp, one requires O(s log p) measurements. While this bound is extremely useful in practice, often real world signals are not only sparse, but also exhibit structure in the sparsity pattern. We focus on group-structured patterns in this paper. Under this model, groups of signal coefficients are active (or inactive) together. The groups are prede- fined, but the particular set of groups that are active (i.e., in the signal support) must be learned from measurements. We show that exploiting knowledge of groups can further reduce the number of measurements required for exact signal recovery, and derive universal bounds for the number of measurements needed. The bound is universal in the sense that it only depends on the number of groups under consideration, and not the particulars of the groups (e.g., compositions, sizes, ex- tents, overlaps, etc.). Experiments show that our result holds for a variety of overlapping group configurations. ER -
APA
Rao, N., Recht, B. & Nowak, R.. (2012). Universal Measurement Bounds for Structured Sparse Signal Recovery. Proceedings of the Fifteenth International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 22:942-950 Available from https://proceedings.mlr.press/v22/rao12.html.

Related Material