Source-linked AI summary
On the State Evolution of Approximate Message Passing with Discontinuous Denoisers
Kuranage Roche Rayan Ranasinghe, Takumi Takahashi, Giuseppe Thadeu Freitas de Abreu
TL;DR
Classical state-evolution analysis does not cover AMP with discontinuous denoisers, including hard slicers, quantizers, and hard thresholding. The paper proves state evolution for such denoisers when the Onsager coefficient includes the missing boundary term, with a version estimated from the residual and known prior. Simulations show that the corrected slicer-AMP follows state evolution and comes close to Bayes-optimal AMP, unlike the standard coefficient.
Problem
Most state-evolution proofs require Lipschitz denoisers, leaving hard decisions, quantizers, and hard thresholding outside those guarantees.
Source: §I · p. 1Method
The authors transfer the Lipschitz state-evolution theorem to fixed discontinuous denoisers using a crossing bound and an Onsager coefficient that includes the boundary term, either from state evolution or from residual-estimated noise and the known prior.
Source: §I · p. 1Results
With the standard slicer coefficient, the MSE leaves the state-evolution trajectory at the second iteration; with either corrected coefficient, the slicer’s symbol error rate reaches 0.1273 or 0.1272 at K = 8192 against the state-evolution value 0.1271.
Source: §VI · p. 5Takeaways & Limitations
The analysis supports hard decisions, finite-level quantizers, and hard thresholding as AMP denoisers without smoothing when the Onsager coefficient contains the boundary term.
Source: §VII · p. 5
Abstract
from arXiv · showhide
We consider approximate message passing (AMP) with discontinuous denoisers, such as hard slicers, quantizers and hard thresholding, for which the classical state evolution (SE) analysis does not apply. It is first shown that the standard Onsager coefficient; i.e., the average pointwise derivative of the denoiser, misses a boundary term, namely, the sum over the jumps of the jump size times the density of the denoiser input at the jump. Then, for real independent and identically distributed (i.i.d.) Gaussian matrices, a positive noise variance, a fixed number of iterations and a prior with finite second moment, we transfer the Lipschitz SE theorem directly to denoisers, fixed in advance, that are continuously differentiable with bounded derivative except at finitely many jumps, by bounding the distance between the iterates of AMP and of AMP on Lipschitz ramps of the denoisers through the fraction of inputs that cross a jump. It is thereby proven that AMP follows SE, also for test functions such as symbol errors, if its Onsager coefficient contains the boundary term, evaluated either along SE or, as we propose, at the noise level estimated from the residual, with the density computed from the known prior. Simulation results with 4- and 8-level pulse amplitude modulation (PAM) demonstrate that AMP with a hard slicer, whose standard coefficient is identically zero, fails with this coefficient, while with the proposed one, it follows SE and comes close to Bayes-optimal AMP.
I. INTRODUCTION
AMP’s state-evolution analysis has generally required Lipschitz denoisers, leaving hard decisions, quantizers, and hard thresholding outside its classical guarantees. The paper proves state evolution for discontinuous denoisers when the Onsager coefficient includes a boundary term, and proposes estimating that term from the residual.
I. INTRODUCTION
- Most existing state-evolution proofs require Lipschitz denoisers, while prior remedies either smooth the denoiser or use an SE-derived divergence without proof.The gap matters for hard decisions, quantizers, and hard thresholding, for which AMP failures have been reported.Source: §I · p. 1
- For fixed-iteration AMP with real i.i.d. Gaussian matrices, positive noise variance, finite-second-moment priors, and finitely many jumps, state evolution holds with either the distributional or SE-corrected Onsager coefficient.The result also covers test functions such as symbol errors.Source: §I · p. 1
- The standard average pointwise derivative misses a boundary term: each jump contributes its jump size times the denoiser-input density at that jump.The proposed coefficient evaluates the boundary term at the residual-estimated noise level using the known prior, without requiring the SE trajectory or signal.Source: §I · pp. 1–2
- For η(u) = |u| + 1{u > 0}, the pointwise-derivative form predicts E[˜zη(˜z)] = 0, but the actual value is φ(0).Source: §I · p. 1
II. AMP AND STATE EVOLUTION
The paper considers noisy linear measurements with an i.i.d. Gaussian sensing matrix and defines state evolution as a scalar recursion for the effective noise variance. For Lipschitz denoisers, the cited theorem establishes that this recursion describes AMP in the large-system limit.
II. AMP AND STATE EVOLUTION
- The measurement model is y = Hx + z, with i.i.d. Gaussian matrix entries scaled by 1/N and i.i.d. unknowns drawn from prior p.The load α = K/N is fixed as K, N grow, and the noise variance is positive.Source: §II · p. 2
- AMP starts with zero estimates and residuals, then iterates using denoisers and Onsager coefficients to update its residual and cavity estimate.The residual-based noise estimate enters only the coefficient in equation (5).Source: §II · p. 2
- For x drawn from p, the scalar-channel pair (x, x + σ̄_t z̃) has law μ_t, with σ̄_t constrained to be at least σ_z.Source: §II · p. 2
- For Lipschitz denoisers that are continuously differentiable outside a finite set, the cited theorem establishes state evolution and convergence of the empirical average derivative to its scalar-channel expectation.The proof applies the Lipschitz state-evolution theorem and uses continuity of the derivative outside a finite set.Source: §II · p. 2
III. THE DISTRIBUTIONAL ONSAGER COEFFICIENT
The distributional Onsager coefficient extends the derivative-based coefficient by including contributions from denoiser jumps. The paper also proposes an online, SE-corrected version that evaluates the boundary term using the residual-estimated noise level and known prior.
III. THE DISTRIBUTIONAL ONSAGER COEFFICIENT
- For discontinuous denoisers, Stein’s identity adds each jump size times the input density at that jump to the average pointwise derivative.The resulting distributional derivative includes both the ordinary derivative and point masses at the jump locations.Source: §III · p. 2
- For a hard slicer, the pointwise derivative is zero, so the standard coefficient vanishes while the distributional coefficient includes positive jump contributions.For equally likely ±1 symbols, the boundary contribution reduces to 2φ(1/σ)/σ.Source: §III · p. 2
- The proposed SE-corrected coefficient evaluates the boundary term at the residual-estimated noise level using the known prior, rather than requiring the SE trajectory.The boundary term is set to zero when the estimated noise level is zero; for finitely supported priors, its stated cost is O(J_t #supp p), alongside O(N) noise estimation.Source: §III · pp. 2–3
IV. STATE EVOLUTION FOR DISCONTINUOUS DENOISERS
Under the stated conditions, AMP with discontinuous denoisers follows state evolution when its Onsager coefficient includes the boundary term. The proof transfers the Lipschitz result through a crossing bound, and the theorem covers discontinuous test functions such as symbol errors.
IV. STATE EVOLUTION FOR DISCONTINUOUS DENOISERS
- With either the distributional or SE-corrected Onsager coefficient, AMP follows state evolution for finitely many iterations under Assumption 1, including convergence for test functions whose discontinuity sets have zero SE measure.The theorem assumes a positive noise floor, a finite-second-moment prior, and denoisers fixed in advance with finitely many separated jumps.Source: §IV · p. 3
- The proof compares the discontinuous AMP iterates with Lipschitz-ramp iterates, bounding their difference by the fraction of cavity inputs near jump points.Bounded SE densities make the near-jump fraction O(s); the theorem concerns the discontinuous iteration itself, and the order of limits in equation (6) matters.Source: §IV · pp. 3–4
- The result includes mean-squared error and, for a slicer whose alphabet contains the prior support, symbol error rate converging to their SE predictions.The theorem also gives the limit of the empirical average pointwise derivative as the distributional coefficient minus its boundary term.Source: §IV · p. 3
- The standard coefficient converges to the distributional coefficient minus the boundary term, so it is inconsistent when that term is nonzero and fails for the slicer.The paper explicitly makes no other recursion claim for the standard coefficient.Source: §IV · p. 3
- The theorem and tensor-program results overlap but neither contains the other: this theorem requires only a finite second moment for the prior, while tensor-program results allow polynomially bounded nonlinearities and test functions.The authors note they have not verified the parameter-control and rank-stability conditions needed to place their residual-dependent coefficient under the cited tensor-program results.Source: §IV · p. 3
- A positive noise floor can be replaced by a positive minimum SE noise level, but thresholds chosen from the residual-estimated noise make denoisers data-dependent and are outside the stated scope.The theorem also relies on fixed-in-advance denoisers and a fixed iteration count.Source: §IV · pp. 3–4
V. PROOF OF THEOREM 1
The proof transfers Lipschitz state evolution to discontinuous denoisers by comparing AMP with iterations using Lipschitz ramps. A crossing bound controls the comparison near jumps, and induction establishes state evolution for the original iterations.
V. PROOF OF THEOREM 1
- Comparing AMP with its Lipschitz-ramp version reduces the proof to controlling entries that cross jumps and showing their Onsager coefficients converge.The crossing bound uses the O(s) fraction of cavity entries within distance s of a jump, plus a Chebyshev term; the SE cavity has bounded density.Source: §V · p. 4
- The proof’s bounds are uniform in system size and ramp width, with constants depending on the fixed iteration horizon and model parameters.The stated bound uses a uniformly bounded cavity density for noise levels at least σ_z.Source: §V · p. 4
- The crossing bound limits denoiser-output differences using the distance to the nearest jump and the number of jumps between two inputs.The ramp agrees with the denoiser outside jump windows and is Lipschitz within the approximation scheme.Source: §V · p. 4
- For each fixed ramp, the Lipschitz SE theorem gives Wasserstein-2 convergence, while the ramp’s jump-window mass is bounded by the cavity density.The proof takes the probability-one event on which these statements hold for all ramp widths and positive window sizes.Source: §V · p. 4
- Induction shows the original AMP iterates approach the ramp iterates as the ramp width vanishes, establishing SE for pseudo-Lipschitz tests.The argument also extends convergence to tests of quadratic growth when the limiting measure assigns zero mass to their discontinuity set.Source: §V · p. 5
VI. NUMERICAL RESULTS
The numerical results show that slicer-AMP with the residual-based coefficient tracks state evolution and approaches Bayes-optimal AMP, whereas the standard coefficient performs poorly. A high-SNR finite-size error floor appears with the SE-scheduled coefficient.
VI. NUMERICAL RESULTS
- At K = 8192, the 8-PAM SER is 0.1273 with ¯bt and 0.1272 with ˆbt, against an SE value of 0.1271.For 8-PAM at 20 dB, the MSE gap falls from 1.0 · 10−2 at K = 64 to 4.3 · 10−5 with ¯bt, and from 5.3·10−3 to 3.4·10−5 with ˆbt.Source: §VI · p. 5
- With ˆbt, slicer-AMP follows SE and approaches Bayes-optimal AMP, while standard-coefficient SER stays near 0.59 (4-PAM) and 0.80 (8-PAM) at every SNR.The comparisons use K = 1024, N = 2048, and T = 20.Source: §VI · p. 5
- For 4-PAM at 18 dB, the SER is 3.3·10−4 for slicer-AMP, 3.0 · 10−4 for SE, and 3.1 · 10−4 for Bayes-optimal AMP.The 8-PAM SER is 5.1 · 10−4 at 24 dB (SE: 5.1 · 10−4; Bayes-optimal AMP: 4.8 · 10−4).Source: §VI · p. 5
- At high SNR, ¯bt has an error floor near 10−2 for 8-PAM because rare realizations leave the SE trajectory and do not recover.At 24 dB, 7 of 400 realizations fail at K = 1024, versus none of 200 at K = 4096.Source: §VI · p. 5
VII. CONCLUSION
The paper proves state evolution for AMP with discontinuous denoisers when the Onsager coefficient includes a boundary term. Its online coefficient uses the residual and known prior; the guarantees hold under stated fixed-horizon and Gaussian-matrix assumptions.
VII. CONCLUSION
- A boundary-term Onsager coefficient makes state evolution valid for discontinuous denoisers, while the standard coefficient is inconsistent whenever the boundary term is nonzero.The boundary term supports hard decisions, finite-level quantizers, and hard thresholding without smoothing.Source: §VII · p. 5
- The SE-corrected coefficient is computed online from the residual and known prior, without using the signal or SE trajectory.The proof transfers Lipschitz SE through a crossing bound comparing AMP with iterations on Lipschitz ramps.Source: §VII · p. 5
- The analysis assumes a finite-second-moment prior and leaves growing iteration counts, data-dependent thresholds, non-separable denoisers, and orthogonal or vector AMP for future work.The paper contrasts its assumptions with tensor-program results requiring Gaussian signals or polynomially bounded functions of Gaussian vectors.Source: §VII · p. 5