# A Two-Stage Method to Test the Robustness of the Generalized Approximate Message Passing Algorithm
## 2 GAMP Algorithm Review  
The GAMP algorithm can be classified to minimum mean error estimation form (MMSE-GAMP) and maximum posterior estimation form (MAP-GAMP) [3]. We restrict our attention to MMSE-GAMP, since the problems in the real world are noisy, such that the posterior function has a very complex shape with details which depend on the observation \(\mathbf{y}\). However, MMSE is robust to such fluctuations. Firstly, GAMP algorithm approximates the true marginal posterior \(p(z_{m}|\mathbf{y})\) by the output channel marginal posterior  
\[p_{z_{m}|\mathbf{p}_{m}}(z|\hat{p}_{m},v_{m}^{p})\triangleq\frac{p_{\gamma_{m} |z_{m}}(y_{m}|z)\mathcal{N}(z;\hat{p}_{m},v_{m}^{p})}{\int p_{y_{m}|z_{m}}(y_{m }|z)\mathcal{N}(z;\hat{p}_{m},v_{m}^{p})\mathrm{d}z}, \tag{2}\]  
where \(z_{m}\) is the estimation of \((\mathrm{A}\mathrm{x})_{m}\) condition on the observation \(y_{m}\), and \(p_{y_{m}|z_{m}}(y_{m}|z)\) is the likelihood of the output channel \(y_{m}=z_{m}+\mathsf{w}_{m}\). It is worth noting that \(\mathsf{w}_{m}\) means a noise, a random variable, and it corresponds to the estimated random variable \(z_{m}\), instead of the original noise \(\mathsf{n}_{m}\) in Equation (1). Therefore, \(w_{m}\) is the residual after estimation of \((\mathbf{A}\mathbf{x})_{m}\). The iterative algorithm computes the conditional mean and variance of \(z_{m}\). We want to obtain the posterior mean and variance estimates  
\[\mathbb{E}\{z_{m}|\mathbf{p}_{m}=\hat{p}_{m},v_{m}^{p}\} =\int z_{m}\;p_{z_{m}|\mathbf{p}_{m}}(z_{m}|\hat{p}_{m},v_{m}^{p}) \mathrm{d}z_{m} \tag{3}\] \[\mathrm{var}\{z_{m}|\mathbf{p}_{m}=\hat{p}_{m},v_{m}^{p}\} =\int(z_{m}-\mathbb{E}\{z_{m}|\mathbf{p}_{m}=\hat{p}_{m},v_{m}^{p} \})^{2}\;p_{z_{m}|\mathbf{p}_{m}}(z_{m}|\hat{p}_{m},v_{m}^{p})\mathrm{d}z_{m}. \tag{4}\]  
Secondly, GAMP algorithm approximates the true marginal posterior \(p(x_{n}|\mathbf{y})\) by the input channel marginal posterior  
\[p_{x_{n}|\mathbf{r}_{n}}(x|\hat{p}_{n},v_{n}^{r})\triangleq\frac{p_{x_{n}}(x) \mathcal{N}(x;\hat{p}_{n},v_{n}^{r})}{\int p_{x_{n}}(x)\mathcal{N}(x;\hat{p}_{ n},v_{n}^{r})\mathrm{d}x} \tag{5}\]  
where \(p_{x_{n}}(x)\) is the prior of random variable \(x_{n}\) in the input channel \(\mathsf{r}_{n}=x_{n}+\mathsf{v}_{n}\). We want to obtain the posterior mean and variance estimates  
\[\mathbb{E}\{x_{n}|r_{n}=\hat{r}_{n},v_{n}^{r}\} =\int x_{n}\;p_{x_{n}|\mathsf{r}_{n}}(x_{n}|\hat{p}_{n},v_{n}^{r}) \mathrm{d}x_{n} \tag{6}\] \[\mathrm{var}\{x_{n}|r_{n}=\hat{r}_{n},v_{n}^{r}\} =\int(x_{n}-\mathbb{E}\{x_{n}|r_{n}=\hat{r}_{n},v_{n}^{r}\})^{2} \;p_{x_{n}|\mathsf{r}_{n}}(x_{n}|\hat{r}_{n},v_{n}^{r})\mathrm{d}x_{n}. \tag{7}\]  
GAMP algorithm is an intrinsic parallel computing process, since it decouples \(\mathsf{y}_{m}=\sum_{n=1}^{N}a_{mn}\mathsf{x}_{n}+\mathsf{w}_{m}\) to the input channel \(\mathsf{r}_{n}=\mathsf{x}_{n}+\mathsf{v}_{n}\) estimation and the output channel \(\mathsf{y}_{m}=\mathsf{z}_{m}+\mathsf{w}_{m}\) estimation. According to the factor graph theory, the messages are probability measures. They can be classified to two types: from the variable node to the factor node, and from the factor node to the variable node. For AMP and GAMP algorithms, all the messages are passed simultaneously between the factor nodes and variable nodes along the edges on the factor graph. These probability measures can be approximated as Gaussian density, based on the derivation of AMP and GAMP algorithms. Therefore, the mean and variance of every entry of \(\mathbf{x}\) are i.i.d. Gaussian random variable. This intrinsic parallel computing implies a flaw: if \(\mathbf{A}\) does not satisfy restricted isometry property (RIP) very well. For example \(\mathbf{A}\) has highly correlated columns, GAMP will diverge. In real world problems, such as radar application, the sensing matrix \(\mathbf{A}\) may be deterministic, not statistics. Therefore the RIP analysis can not be applied to this situation, researchers use simulation to find the behavior of this kind of reconstruction. We will show it in Section 5.