A unifying tutorial on Approximate Message Passing

AMP algorithms have two features that make them particularly attractive. First, they can easily be tailored to take advantage of prior information on the structure of the signal, such as sparsity or other constraints. Second, under suitable assumptions on a design or data matrix, AMP theory provides precise asymptotic guarantees for statistical procedures in the high-dimensional regime where the ratio of the number of observations n to dimensions p converges to a constant (Bayati and Montanari, 2012; Donoho et al., 2013; Sur et al., 2017). More generally, AMP has been also used to obtain lower bounds on the estimation error of first-order methods (Celentano et al., 2020), and in linear regression and low rank matrix estimation, it plays a fundamental role in understanding the performance gap between information-theoretically optimal and computationally feasible estimators (Reeves and Pfister, 2019; Barbier et al., 2019; Lelarge and Miolane, 2019). In these settings, it is conjectured that AMP achieves the optimal asymptotic estimation error among all polynomial-time algorithms (cf.