S-AMP: Approximate Message Passing for General Matrix Ensembles

We propose a novel iterative estimation algorithm for linear observation models called S-AMP. The fixed points ofS-AMP are the stationary points of the exact Gibbs free energy under a set of (first- and second-) moment consistency constraintsin the large system limit. S-AMP extends the approximate message-passing (AMP) algorithm to general matrix ensembleswith a well-defined large system size limit. The generalization is based on the S-transform (in free probability) of the spectrumof the measurement matrix. Furthermore, we show that the optimality of S-AMP follows directly from its design rather thanfrom solving a separate optimization problem as done for AMP