Abstract: This paper explores the limits of sparse signal reconstruction in compressed sensing by leveraging nonconvex penalties, specifically the Smoothly Clipped Absolute Deviation (SCAD). To overcome the algorithmic instability inherent in nonconvex optimization, the authors introduce a one-step replica-symmetry-breaking (1RSB) Approximate Message Passing (AMP) algorithm. Combined with a nonconvexity-control (NCC) protocol, this approach significantly reduces the divergence region in the phase space, pushing the boundary of perfect reconstruction closer to the theoretical Bayes-optimal limit.
Introduction
Compressed sensing aims to recover high-dimensional sparse signals from a limited number of linear measurements. While convex relaxations like $\ell_1$-minimization (LASSO) are computationally efficient, they require more samples than theoretically necessary for perfect recovery. Nonconvex penalties like SCAD offer a path to lower sample requirements but introduce complex, multi-modal energy landscapes that cause standard algorithms to fail.
The standard Approximate Message Passing (AMP) algorithm, based on the Replica Symmetric (RS) assumption, often diverges when the solution space "shatters" into many isolated clusters—a hallmark of Replica Symmetry Breaking (RSB). This paper addresses this limitation by developing a 1RSB-AMP framework that can navigate these shattered landscapes.
Methodology
The core of the proposed method is the 1RSB-AMP algorithm, which propagates distributions of messages (surveys) rather than single point estimates. This allows the algorithm to handle the fragmented solution space typical of nonconvex problems. The authors derived explicit, closed-form update rules specifically for the SCAD penalty, which is characterized by its thresholding behavior.
As illustrated in the figure above, the SCAD penalty (blue) behaves like LASSO for small values but transitions to an OLS-like behavior for larger values, effectively reducing the bias introduced by $\ell_1$ shrinkage. The derivative $\chi$ is a critical component for the Onsager correction term in the AMP iterations.
A key challenge in 1RSB models is tuning the Parisi parameter ($ℓ$), which weights the solution clusters. The authors found that the standard "zero-complexity" condition was numerically unstable in this context. Instead, they proposed a pragmatic criterion: selecting $ℓ$ to minimize the algorithm's divergence region. This is integrated into a Nonconvexity-Control (NCC) protocol, where the nonconvexity of the SCAD penalty is gradually adjusted during the iterations to guide the algorithm toward the global minimum.
Key Results and Insights
The authors validated their approach using synthetic data consisting of Bernoulli-Gaussian signals and Gaussian measurement matrices. The theoretical predictions from 1RSB State Evolution (SE) equations matched empirical results from 1RSB-AMP simulations with high precision, even in regions where RS-AMP failed.
- Shrinking the Divergence Phase: The 1RSB formulation successfully reduces the region of the phase diagram where the algorithm diverges compared to the RS baseline.
- Improved Reconstruction Limits: For a standard test case (measurement rate $\alpha = 0.5$, SCAD parameter $a=3$), the maximum sparsity level ($\rho$) for perfect reconstruction improved from $\rho \approx 0.297$ (the RS limit) to $\rho \approx 0.302$ (the 1RSB limit).
- Approaching Bayes-Optimality: While the numerical improvement is modest, it pushes the practical algorithmic limit significantly closer to the theoretical Bayes-optimal limit of $\rho \approx 0.309$.
- RS Recovery: The analysis confirms that if the algorithm successfully reaches the perfect reconstruction state, the system naturally returns to a Replica Symmetric state. The 1RSB machinery serves as a robust vehicle to drive the algorithm through the unstable RSB failure phases.
Limitations and Future Work
Despite its success, the performance gain over the previous RS-AMP approach is relatively small and still falls slightly short of the Bayes-optimal threshold. Additionally, the standard "zero-complexity" condition for tuning the Parisi parameter proved difficult to implement due to numerical precision issues, necessitating a heuristic alternative.
Future research may explore higher-step RSB algorithms (such as $K$-step Approximate Survey Propagation) or incremental AMP variants. These methods might better navigate the deeply shattered landscapes of nonconvex regularizers and finally close the remaining gap to the Bayes-optimal limit.
Summary updated