Source-linked AI summary
Adaptive Damping and Mean Removal for the Generalized Approximate Message Passing Algorithm
Jeremy Vila, Philip Schniter, Sundeep Rangan, Florent Krzakala, Lenka Zdeborova
TL;DR
GAMP can be optimal for suitable random matrices but may diverge for generic A, motivating methods that improve convergence robustness. The paper develops adaptive damping and mean removal, and experiments show substantially improved robustness across difficult matrix types, with performance similar to SwAMP and faster runtime in the tested comparisons.
Problem
For generic A, GAMP may diverge, while global convergence under generic priors, likelihoods, and matrices is not yet understood.
Method
The paper details adaptive damping and mean-removal modifications of GAMP to mitigate divergence for difficult matrices.
Results
The modifications significantly improve robustness to non-zero-mean, rank-deficient, column-correlated, and ill-conditioned A, with robustness similar to SwAMP and faster runtime in the tested implementation.
Takeaways & Limitations
Adaptive damping and mean removal make GAMP substantially more robust while preserving the ability to exploit fast implementations such as FFTs.
Takeaways & Limitations
The MMSE-GAMP cost evaluation requires numerical regularized Newton iterations whose parameters must be tuned to the likelihood function.
Abstract
from arXiv · showhide
The generalized approximate message passing (GAMP) algorithm is an efficient method of MAP or approximate-MMSE estimation of $x$ observed from a noisy version of the transform coefficients $z = Ax$. In fact, for large zero-mean i.i.d sub-Gaussian $A$, GAMP is characterized by a state evolution whose fixed points, when unique, are optimal. For generic $A$, however, GAMP may diverge. In this paper, we propose adaptive damping and mean-removal strategies that aim to prevent divergence. Numerical results demonstrate significantly enhanced robustness to non-zero-mean, rank-deficient, column-correlated, and ill-conditioned $A$.
1. INTRODUCTION
GAMP efficiently addresses large-scale MAP and approximate-MMSE estimation, with optimal fixed points under suitable random matrices but possible divergence for generic A. This paper introduces adaptive damping and mean removal to improve robustness while retaining faster convergence than SwAMP.
- GAMP converts large-scale MAP or approximate-MMSE inference into a sequence of tractable scalar inference problems.It is motivated by high-dimensional approximations to loopy belief propagation.
- For large i.i.d. zero-mean sub-Gaussian A, GAMP has state-evolution fixed points that are MMSE- or MAP-optimal when unique.
- For generic A, GAMP may diverge, and global convergence remains unresolved beyond characterized special cases.Gaussian-GAMP converges under a sufficiently small peak-to-average ratio of squared singular values, while damping can guarantee convergence at slower speed for arbitrary A.
- Prior robustification methods trade speed or implementation flexibility for stability: SwAMP is more robust but slower and unsuitable for fast implementations such as FFTs.Existing GAMPmatlab software also included adaptive damping and mean removal without prior literature descriptions.
- The paper details adaptive damping and mean-removal mechanisms and experimentally evaluates them on difficult matrices, finding improved robustness relative to SwAMP and enhanced convergence speed.The tested settings include non-zero-mean, rank-deficient, column-correlated, and ill-conditioned A.
2. ADAPTIVELY DAMPED GAMP
AD-GAMP adapts its damping factor using an iteration cost, increasing damping after passes and decreasing it after failures. The section also defines MMSE cost evaluation and a mean-removal reformulation that makes the transformed matrix approximately zero-mean.
- Adaptive damping: AD-GAMP increases β after passing iterations and decreases it after failures, retrying failed iterations to balance divergence prevention against unnecessary slowdown.An iteration passes when its cost is at least as good as the worst recent cost, or β(t) is already at βmin; β remains bounded by βmin and βmax.
- Cost evaluation: The damping rule computes J(t+1) from JMAP in MAP-GAMP and from a Bethe-based JMSE cost in MMSE-GAMP.The MMSE cost uses moment-matched quantities rather than directly substituting the current belief parameters into the Bethe cost.
- MMSE-GAMP cost evaluation: For non-AWGN likelihoods, the method solves the MMSE moment-matching equation numerically with regularized Newton iterations instead of closed-form inversion.The procedure uses a stepsize α, regularization φ, iteration limit Imax, initialization epm(1), and tolerance ǫinv; AWGN permits a closed-form solution.
- Mean removal: Mean removal rewrites z = Ax with an augmented linear system whose transformed matrix has approximately zero-mean rows and columns.The construction adds elements with improper uniform priors and augments the likelihoods and priors when running GAMP or AD-GAMP.
3. NUMERICAL RESULTS
Experiments evaluate GAMP variants on several difficult matrix types across AWGN, robust, and 1-bit compressive sensing. Mean removal and adaptive damping substantially improve robustness, while MAD-GAMP generally matches or exceeds SwAMP and runs faster overall.
- AWGN compressive sensing: AD-GAMP was slightly more robust than SwAMP and significantly more robust than GAMP for low-rank, correlated, and ill-conditioned matrices in AWGN compressive sensing.For non-zero-mean matrices, M-GAMP and MAD-GAMP achieved near-genie performance across tested means, whereas GAMP worked only with zero-mean A and SwAMP only with small-mean A.
- Robust compressive sensing: MAD-GAMP improved robust compressive-sensing performance over GAMP, while SwAMP was slightly more robust for low-rank, correlated, and ill-conditioned matrices.With non-zero-mean A, performance increased from GAMP to M-GAMP to SwAMP to MAD-GAMP.
- 1-bit compressive sensing: MAD-GAMP and M-GAMP were more robust than SwAMP for non-zero-mean A in noiseless 1-bit compressive sensing, while all proposed methods were far more robust than original GAMP on difficult matrices.For low-rank, correlated, and ill-conditioned matrices, MAD-GAMP and SwAMP showed similarly robust performance, whereas GAMP was very fragile.
- Convergence speed: MAD-GAMP ran several times faster than SwAMP overall, despite using more iterations.Only (M)AD-GAMP can exploit fast O(N log N) implementations such as FFTs.
4. CONCLUSIONS
The paper proposes adaptive damping and mean removal to prevent GAMP divergence on difficult matrices. Experiments show substantially improved robustness, comparable robustness to SwAMP, and faster runtime than the current SwAMP implementation.
- 4. CONCLUSIONS: Adaptive damping and mean removal substantially increase GAMP’s robustness to non-zero-mean, low-rank, column-correlated, and ill-conditioned matrices.The modifications are intended to help prevent divergence for difficult A matrices.
- 4. CONCLUSIONS: The proposed modifications provide robustness similar to SwAMP while running faster than the current SwAMP implementation.The paper suggests combining SwAMP’s sequential updates with mean removal or adaptive damping as future work.