[**Regions 2 and 3:**]{} There are 2 local maxima in the free energy, $D_1$ and $D_2$, where $D_1<D_2$. In Region 2, the smaller MSE, $D_1$, leads to the larger local maximum free energy  (hence, $\mathcal{F}(D_1)$ is the global maximum), and is the MMSE. In Region 3, the larger MSE, $D_2$, is the MMSE.

[**Boundaries between regions:**]{} We denote the boundary separating regions 1 and 2 by the [*BP threshold*]{} $R_{BP}(\Delta)$, the boundary separating regions 2 and 3 by the [*low noise threshold*]{} $R_l(\Delta)$, and the boundary separating regions 3 and 4 by the [*critical threshold*]{} $R_c(\Delta)$.

[**Numerical results:**]{} Consider $J$-dimensional Bernoulli-Gaussian signals  with sparsity rate $\rho=0.1$. Evaluating the free energy  with the noise variance $\Delta$ from -20 dB to -50 dB and measurement rate $R$ from 0.11 to 0.24, we obtain the MMSE as a function of $\Delta$ and $R$ for $J=1,3$, and $5$, as shown in Fig. \[fig:PerformanceRegions\].[^10] The darkness of the shades represents the natural logarithm of the MMSE, $\ln$(MMSE). In all panels, the critical threshold $R_c(\Delta)$, low noise threshold $R_l(\Delta)$, and BP threshold $R_{BP}(\Delta)$, as well as Regions 1-4, are marked.

In Regions 3 and 4, the best-possible algorithm yields a large MMSE for all noise variances. 