Statistical Mechanics of MAP Estimation: General Replica Ansatz
  The large-system performance of MAP estimation is studied considering a general distortion function when the observation vector is received through a linear system with additive white Gaussian noise. The analysis considers the system matrix to be chosen from the large class of rotationally invariant random matrices. We take a statistical mechanical approach by introducing a spin glass corresponding to the estimator, and employing the replica method for the large-system analysis. In contrast to earlier replica based studies, our analysis evaluates the general replica ansatz of the corresponding spin glass and determines the asymptotic distortion of the estimator for any structure of the replica correlation matrix. Consequently, the replica symmetric as well as the Replica Symmetry (RS) breaking ansatz with $b$ steps of breaking is deduced from the given general replica ansatz. The generality of our distortion function lets us derive a more general form of the MAP decoupling principle. Based on the general replica ansatz, we show that for any structure of the replica correlation matrix, the vector-valued system decouples into a bank of equivalent decoupled linear systems followed by MAP estimators. The structure of the decoupled linear system is further studied under both the RS and the Replica Symmetry Breaking (RSB) assumptions. For $b$ steps of RSB, the decoupled system is found to be an additive system with a noise term given as the sum of an independent Gaussian random variable with $b$ correlated impairment terms. As an application of our study, we investigate large compressive sensing systems by considering the $\ell_p$ minimization recovery schemes. Our numerical investigations show that the replica symmetric ansatz for $\ell_0$ norm recovery fails to give an accurate approximation of the mean square error as the compression rate grows, and therefore, the RSB ans\"atze are needed. 
Ali Bereyhi and Ralf R. M\"uller and Hermann Schulz-Baldes
cs.IT math.IT