Sampling from the Random Linear Model via Stochastic Localization Up to the AMP Threshold

The Approximate Message Passing (AMP) algorithm has garnered significant attention in recent years for solving linear inverse problems, particularly in the field of Bayesian inference for high-dimensional models. In this paper, we consider sampling from the posterior in the linear inverse problem, with an i.i.d. random design matrix. We develop a sampling algorithm by integrating the AMP algorithm and stochastic localization. We give a proof for the convergence in smoothed KL divergence between the distribution of the samples generated by our algorithm and the target distribution, whenever the noise variance Δ is below ΔAMP, which is the computation threshold for mean estimation introduced in (Barbier et al., 2020).