MMV, where the MMSE has different characteristics based on channel noise variance and measurement rate. Finally, we find a phase transition for belief propagation algorithms (BP) [@DMM2009; @CSBP2010; @Bayati2011; @Montanari2012; @Krzakala2012probabilistic; @krzakala2012statistical; @Barbier2015] applied to MMV problems, which separates regions where BP achieves the MMSE asymptotically and where it is suboptimal. BP simulation results confirm the phase transition results.

The remainder of the paper is organized as follows. We introduce our signal and measurement models in Section \[sec:model\], followed by replica analyses for two MMV settings as well as two SMV complex CS problems in Section \[sec:main\]. Section \[sec:proof\] proves the results of Section \[sec:main\]. Numerical results are discussed in Section \[sec:numeric\] and we conclude in Section \[sec:conclusion\].

[**Notations:**]{} In this paper, bold capital letters represent matrices, bold lower case letters represent vectors, and normal font lower case letters represent scalars. The entry (scalar) in the $\mu$-th row, $l$-th column of a matrix $\F$ is denoted by $F_{\mu,l}$, where the comma is often omitted. The $\mu$-th entry (scalar) in a vector $\z$ is denoted by $z_{\mu}$.

Signal and Measurement Models {#sec:model}
=============================

[**Signal model**]{}: We consider an ensemble of $J$ signal vectors, $\underline{\s}^j\in\mathbb{R}^N,\ j\in\{1,...,J\}$, where $j$ is the index of 