  In this paper, compressed sensing with noisy measurements is addressed. The
theoretically optimal reconstruction error is studied by evaluating Tanaka's
equation. The main contribution is to show that in several regions, which have
different measurement rates and noise levels, the reconstruction error behaves
differently. This paper also evaluates the performance of the belief
propagation (BP) signal reconstruction method in the regions discovered. When
the measurement rate and the noise level lie in a certain region, BP is
suboptimal with respect to Tanaka's equation, and it may be possible to develop
reconstruction algorithms with lower error in that region.
