Maximin Analysis of Message Passing Algorithms for Recovering Block Sparse Signals

Armeen Taeb, Arian Maleki, Christoph Studer, Richard G. BaraniukarXiv 2013 · arXiv

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:

  1. AMP Limit: The optimal phase transition $\rho^*(\delta)$ for AMP scales as $\frac{B}{2 \log(1/\delta)}$ as $\delta \to 0$.
  2. 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.

Phase transition curves for different block sizes compared to the information-theoretic limit.

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

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.
BibTeX
@misc{taeb2013maximin,
  author = {Armeen Taeb and Arian Maleki and Christoph Studer and Richard G. Baraniuk},
  title = {{Maximin Analysis of Message Passing Algorithms for Recovering Block Sparse Signals}},
  year = {2013},
  eprint = {1303.2389},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1303.2389},
}
Figure