Source-linked AI summary
Maximin Analysis of Message Passing Algorithms for Recovering Block Sparse Signals
Armeen Taeb, Arian Maleki, Christoph Studer, Richard Baraniuk
TL;DR
Recovering block-sparse signals from underdetermined random measurements raises the question of whether AMP can outperform group LASSO when blocks are fixed and measurements are scarce. The paper characterizes AMP’s thresholding performance in this regime and shows that no nonlinear shrinkage function improves on group LASSO. Its conclusion complements prior results for large blocks.
Problem
Prior work found that AMP with Stein’s shrinkage can outperform group LASSO for very large blocks, but whether AMP can do so for fixed block sizes under strong undersampling remained open.
Source: §1 · p. 2Method
The paper characterizes the best AMP thresholding performance in the strong-undersampling regime, optimizing over thresholding functions applied separately to each block.
Source: §3 · p. 4Results
Takeaways & Limitations
In strong undersampling, block soft-thresholding is optimal for fixed block sizes, while Stein’s shrinkage requires larger blocks to outperform group LASSO.
Source: §3 · p. 4The analysis assumes equal-sized blocks; extensions to varying block sizes are described as straightforward.
Source: §2.1 · p. 2
Abstract
from arXiv · showhide
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.
1. Introduction.
Block-sparse signals have clusters of nonzero coefficients, and group LASSO provides a popular recovery method whose phase transition remains separated from the information-theoretic limit. The paper asks whether AMP can outperform group LASSO for fixed block sizes under strong undersampling and shows that no nonlinear shrinkage function does so as δ →0.
1. Introduction.
- Block-sparse signals have nonzero coefficients in clusters of size B and arise in genomics, radar, and communication applications.Group LASSO is a popular recovery algorithm, but prior theoretical results characterize recovery conditions rather than accurate performance.Source: §1 · p. 1
- Asymptotic phase-transition analyses found a gap between group LASSO and the information-theoretic limit, motivating the characterization of group LASSO performance [14] [16].The information-theoretic limit for block-sparse signals extends from the regular-sparse result in.Source: §1 · p. 1
- AMP with expectation maximization was experimentally shown to outperform group LASSO, while AMP with Stein’s shrinkage approaches the information-theoretic limit for very large blocks [16].For fixed block sizes, Stein’s estimator does not necessarily improve AMP performance.Source: §1 · pp. 1–2
- For δ →0, no nonlinear shrinkage function lets AMP outperform group LASSO; this does not contradict AMP’s reported gains as B →∞ [16].In the strong-undersampling regime, AMP with Stein’s estimator requires large block sizes to outperform group LASSO.Source: §1 · p. 2
2. Background.
The background specifies the block-sparse signal model and describes group LASSO, AMP, and phase-transition analysis. It also explains why AMP’s thresholding function matters for its recovery performance.
2.1. Notation.
- Signals are divided into equal-sized blocks of size B, with each block drawn from a mixture of zero and nonzero components and ϵ = ρδ.The measurement matrix is i.i.d. zero-mean Gaussian with unit variance, and the model uses an asymptotic setting with δ = n/N and ρ = k/n.Source: §2.1 · p. 2
- Block soft-thresholding zeros a block when its norm is at most τ and otherwise shrinks it toward the origin by τ.Group LASSO minimizes a sum of block norms subject to the measurement constraint.Source: §2.1 · p. 3
2.2. Group LASSO and approximate message passing (AMP).
- AMP iteratively estimates the signal using a correction term and a nonlinear function that imposes block sparsity; with block soft-thresholding, it is asymptotically equivalent to group LASSO [16].AMP’s iterations can be viewed as denoising the signal in Gaussian noise, enabling performance prediction through state evolution.Source: §2.2 · p. 3
2.3. Phase transition.
- The thresholding function determines AMP’s performance, so finding an optimal alternative to block soft-thresholding is of practical interest.Phase-transition curves separate exact-recovery success from failure; at a fixed δ, a higher curve guarantees recovery for more nonzero entries.Source: §3 · p. 3, §2.3 · p. 3
3. Main results.
For fixed block size in strong undersampling, AMP’s best phase transition coincides with group LASSO’s. Block soft-thresholding is therefore optimal, and no AMP thresholding function can outperform group LASSO in this regime.
3. Main results.
- The paper optimizes AMP’s thresholding function over all possible initializations, seeking the best phase transition for the least favorable distribution.The least-favorable criterion is motivated by G typically being unknown in practice.Source: §3 · p. 4
- ρ*(δ) ~ B 2 log(1/δ) and ρL(δ) ~ B 2 log(1/δ) as δ→0.The AMP behavior is determined when G is uniform on a sphere with infinite radius.Source: §3 · p. 4
- When G is unknown, the theorem’s identified behavior does not provide guidelines for choosing ηt.The stated behavior is determined for G uniformly distributed on a sphere with infinite radius.Source: §3 · p. 4
- For fixed B as δ→0, AMP’s best phase transition coincides with group LASSO’s; block soft-thresholding is optimal, and better thresholding requires larger blocks to outperform group LASSO.The results complement, rather than contradict, the large-block Stein-shrinkage findings.Source: §3 · p. 4
4. Proofs of the main results.
The proofs derive group LASSO’s phase transition and bound the optimal phase transition in strong undersampling using state evolution and asymptotic risk analysis.
4.1. Proof of Theorem 3.2.
- State evolution gives group LASSO’s phase transition because its performance is equivalent to AMP with block soft thresholding.The proof uses the minimax MSE and the condition MB = δ to derive the phase-transition expression.Source: §4.1 · p. 5, §4.1.1 · p. 5
4.1.1. Implicit formula for the phase transition of group LASSO.
- The group LASSO phase-transition formula is independent of the signal distribution G.The formula uses an optimal threshold parameter τ*.Source: §4.1.1 · p. 5
4.1.2. Phase transition behavior for δ →0.
- For δ→0, the proof approximates the relevant integrals with Laplace’s method, yielding log(δ^-1) ∼ τ*^2/2.The derivation uses the large-τ* regime.Source: §4.1.2 · pp. 5–6
4.2. Proof of Theorem 3.1.
- For a sparse prior with nonzero blocks uniform on a sphere, the Bayes estimator’s norm is bounded by μ, supporting the risk bound used in the phase-transition proof.The prior is F(xB) = (1 − ϵ)δ0(∥xB∥2) + ϵG*(xB), with G* uniform on a sphere of radius μ.Source: §4.2 · pp. 7–9
- As δ→0, the optimal phase transition satisfies ρ*(δ) ∼ B/(2 log(1/δ)); by optimality, ρ*(δ) ≳ ρL(δ) ∼ B/(2 log(1/δ)).Source: §4.2 · p. 11