On the State Evolution of Approximate Message Passing with Discontinuous Denoisers
Abstract
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.
Related
- Deriving Approximate Message Passing from the Convex Gaussian Min-Max Theorem
- Quantitative Universality of Approximate Message Passing for Rank-One Quadratic Sensing
- Universality of approximate message passing under a fourth-moment tail condition
- Almost Sharp Equivalence between Approximate Message Passing and Low-Degree Polynomials
- DAIF: A Data-Driven Intermediate Fusion Framework for Multimodal Supervised Learning via Approximate Message Passing
BibTeX
@misc{ranasinghe2026state,
title = {{On the State Evolution of Approximate Message Passing with Discontinuous Denoisers}},
author = {Kuranage Roche Rayan Ranasinghe and Takumi Takahashi and Giuseppe Thadeu Freitas de Abreu},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.08256},
eprint = {2610.08256},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.08256},
}
RIS
TY - UNPB
TI - On the State Evolution of Approximate Message Passing with Discontinuous Denoisers
AU - Kuranage Roche Rayan Ranasinghe
AU - Takumi Takahashi
AU - Giuseppe Thadeu Freitas de Abreu
PY - 2026
DA - 2026/10/06
PB - arXiv
DO - 10.48550/arxiv.2610.08256
UR - https://arxiv.org/abs/2610.08256
AB - 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.
ER -