  We consider the estimation of a signal from the knowledge of its noisy linear
random Gaussian projections, a problem relevant in compressed sensing, sparse
superposition codes or code division multiple access just to cite few. There
has been a number of works considering the mutual information for this problem
using the heuristic replica method from statistical physics. Here we put these
considerations on a firm rigorous basis. First, we show, using a Guerra-type
interpolation, that the replica formula yields an upper bound to the exact
mutual information. Secondly, for many relevant practical cases, we present a
converse lower bound via a method that uses spatial coupling, state evolution
analysis and the I-MMSE theorem. This yields, in particular, a single letter
formula for the mutual information and the minimal-mean-square error for random
Gaussian linear estimation of all discrete bounded signals.
