Maximin Analysis of Message Passing Algorithms for Recovering Block Sparse Signals

2013/03/10 by Armeen Taeb, Taeb, Armeen, Arian Maleki +6
Computer Science · Engineering · Mathematics · #FOS: Computer and information sciences #Geophysical Methods and Applications #Information Theory (cs.IT) #Microwave Imaging and Scattering Analysis #Sparse and Compressive Sensing Techniques #cs.IT #math.IT

paper · pdf · doi:10.48550/arxiv.1303.2389

arxiv created 2013/03/10 · openalex publication_date 2013/03/10 · arxiv updated 2013/03/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We consider the problem of recovering a block (or group) sparse signal from an underdetermined set of random linear measurements, which appear in compressed sensing applications such as radar and imaging. Recent results of Donoho, Johnstone, and Montanari have shown that approximate message passing (AMP) in combination with Stein's shrinkage outperforms group LASSO for large block sizes. In this paper, we prove that, for a fixed block size and in the strong undersampling regime (i.e., having very few measurements compared to the ambient dimension), AMP cannot improve upon group LASSO, thereby complementing the results of Donoho et al.

Citations

• Block-length dependent thresholds in block-sparse compressed sensing
• The Group Lasso for Logistic Regression
• Consistency of the group Lasso and multiple kernel learning

Related

• Message Passing Algorithms for Compressed Sensing: I. Motivation and Construction
• Message Passing Algorithms for Compressed Sensing: II. Analysis and Validation
• Compressed Sensing for Block-Sparse Smooth Signals
• Bayesian Optimal Approximate Message Passing to Recover Structured Sparse Signals
• Asymptotic Analysis of LASSOs Solution Path with Implications for Approximate Message Passing