Bayes-Optimal Estimation in Generalized Linear Models via Spatial Coupling

We consider the problem of signal estimation in a generalized linear model (GLM). GLMs cover many canonical problems in statistical estimation including linear regression and phase retrieval. Recent work has precisely characterized the asymptotic minimum mean-squared error (MMSE) for GLMs with i.i.d. Gaussian sensing matrices. However, in many models there is a significant gap between the MMSE and the performance of the best known feasible estimators. In this work we address this gap by considering GLMs defined via spatially coupled sensing matrices. We propose an efficient approximate message passing (AMP) algorithm for estimation and prove that with a simple choice of spatially coupled design, the MSE of a carefully tuned AMP estimator approaches the asymptotic MMSE. Numerical results show that for finite signal dimensions, spatially coupled designs can yield substantially lower MSE than i.i.d. Gaussian designs when used with AMP algorithms.