  Recovering a sparse signal from an undersampled set of random linear
measurements is the main problem of interest in compressed sensing. In this
paper, we consider the case where both the signal and the measurements are
complex. We study the popular reconstruction method of $\ell_1$-regularized
least squares or LASSO. While several studies have shown that the LASSO
algorithm offers desirable solutions under certain conditions, the precise
asymptotic performance of this algorithm in the complex setting is not yet
known. In this paper, we extend the approximate message passing (AMP) algorithm
to the complex signals and measurements and obtain the complex approximate
message passing algorithm (CAMP). We then generalize the state evolution
framework recently introduced for the analysis of AMP, to the complex setting.
Using the state evolution, we derive accurate formulas for the phase transition
and noise sensitivity of both LASSO and CAMP.
