Introduction
In the field of compressed sensing, recovering a high-dimensional signal from a limited number of linear measurements is a fundamental challenge. Many real-world signals exhibit "block-sparsity," where non-zero entries are clustered into specific groups. Traditionally, Group LASSO has been the go-to optimization method for such problems. More recently, Approximate Message Passing (AMP) has emerged as a powerful iterative alternative, often outperforming Group LASSO when block sizes are large. This paper investigates whether AMP maintains this superiority in the "strong undersampling" regime—where measurements are extremely scarce—and when block sizes are small and fixed.
The "No Free Lunch" Theorem in Strong Undersampling
The core contribution of this work is a rigorous mathematical proof showing that in the limit of strong undersampling ($\delta = n/N \to 0$), AMP cannot outperform Group LASSO for fixed block sizes. The researchers utilized Phase Transition (PT) analysis to map the boundary between successful signal recovery and failure.
Key Analytical Results
The study provides two primary theorems defining the phase transition $\rho(\delta)$, which represents the maximum sparsity rate for successful recovery:
- AMP Limit: The optimal phase transition $\rho^*(\delta)$ for AMP scales as $\frac{B}{2 \log(1/\delta)}$ as $\delta \to 0$.
- Group LASSO Limit: The phase transition for Group LASSO $\rho^L(\delta)$ follows the exact same scaling: $\frac{B}{2 \log(1/\delta)}$.
These results imply that for high undersampling, the block soft-thresholding function used in Group LASSO is not merely a heuristic but is actually the optimal choice for the thresholding step within the AMP framework.
Methodology and Insights
The authors employed several sophisticated techniques to reach these conclusions:
- State Evolution (SE): Used to analytically predict the mean-square error of AMP at each iteration.
- Maximin Analysis: The researchers sought the "optimal" thresholding function by identifying the one that performs best against the "least favorable" signal distribution.
- Bayes Estimators: By analyzing a worst-case signal distribution (uniform on a sphere with infinite radius), they established a theoretical ceiling on performance.
A key insight is that the "worst-case" signal distribution for these algorithms is spherical. Under these conditions, the Bayes estimator—the theoretically best way to denoise—begins to behave like a hard-thresholding function, which explains why the performance of various algorithms converges.
Practical Implications
The findings reconcile a gap in existing literature. While previous work showed AMP's superiority as block sizes approach infinity, this paper highlights that the advantage vanishes if the block size $B$ is held constant while the number of measurements drops. For practitioners, this means that in regimes of extreme data scarcity, the added complexity of AMP may not provide a significant recovery advantage over the more traditional Group LASSO, unless the underlying signal structure allows for very large block sizes.
Limitations and Future Directions
The analysis specifically targets the $\delta \to 0$ regime and assumes i.i.d. Gaussian measurement matrices. While these are standard benchmarks in information theory, real-world sensing matrices (such as those in MRI) often possess more structure. Future research could aim to characterize the exact "crossover point"—the specific block size or measurement rate at which AMP begins to significantly pull away from Group LASSO.
Summary updated