# A Two-Stage Method to Test the Robustness of the Generalized Approximate Message Passing Algorithm
## 4 Bernoulli-Gaussian Pursuit GAMP Algorithm
We do \(Q=100\) trials in each experiment, and use the relative mean square error (RMSE) \(\xi=1/Q\times\sum_{l=1}^{Q}\|\hat{\mathbf{x}}^{l}-\mathbf{x}^{l}\|_{2}/\| \mathbf{x}^{l}\|_{2}\) as the performance metric. Given \(N/M=3,M/K=5\), we set \(N=256\), and then \(M=86,K=18\). Choose \(K\) locations at random as the support of \(\mathbf{x}\), and the amplitude of each non-zero entry \(x_{i}\) is independently drawn from \(\mathcal{N}(0,1)\). We set the signal-to-noise ratio (SNR) to 25 dB. The first experiment, termed \(\gamma\) test, investigates non-zero mean Gaussian sensing matrix case. We create two types of sensing matrix: type 1 means \(A(:,j)=\gamma/N+\mathbf{a}_{j}/\sqrt{N}\); type 2 means \(A(:,j)=\gamma/N+\mathbf{a}_{j}/\|\mathbf{a}_{j}\|_{2}\), where each entry of \(\mathbf{a}_{j}\) is i.i.d. drawn from \(\mathcal{N}(0,1)\). Set the range of \(\gamma\) to \([0,1,1.8,1.9,1.95,2,3,4,5,6,7,8,9,10,11,12]\). Figure 0(a) shows that GAMP violently diverges at \(\gamma=2\), AMP fast diverges at \(\gamma=5\). The severely sharp divergence of GAMP and AMP comes from the phase transition property of compressed sensing. Although BGP-GAMP also begins to diverge at \(\gamma=5\), the deterioration speed is slower than AMP. Furthermore, the RMSE of BGP-GAMP is always less than that of AMP. When \(\gamma<4\), the RMSE of BGP-GAMP is a little less than that of OMP, and when \(\gamma<6\), the RMSE of BGP-GAMP is obviously less than that of BP. Figure 0(b) shows that AMP violently diverges at \(\gamma=1.95\), GAMP violently diverges at \(\gamma=3\), but BGP-GAMP just begins to diverge at \(\gamma=8\). The RMSE of BGP-GAMP is always less than that of BP, and less than that of OMP until \(\gamma=8\). Moreover, Figure 0(a),0 shows that BGP-GAMP outperforms OMP slightly in performance over a parameter range \(\gamma<2\). In summary, our proposed algorithm obtains better robustness compared with the standard AMP/GAMP algorithms, at the same time our proposed algorithm achieves performance advantage over a suitable parameter range compared with the standard OMP and BP algorithms. The second experiment, termed \(\alpha\) test, investigates the highly correlated columns sensing matrix \(\mathbf{A}\) case. The elements of \(\mathbf{A}\) are neither normal nor i.i.d distributed. Create two types of sensing matrix: type 1 means \(\mathbf{A}=(1/N)\mathbf{PQ},p_{mr},q_{rn}\sim N(0,1)\), where \(\mathbf{P}\in\mathbb{R}^{M\times R},\mathbf{Q}\in\mathbb{R}^{R\times N}\), and \(R\triangleq\alpha N\); type 2 means \(\mathbf{A}=\mathbf{PQ}\) like type 1, but normalizes each column of \(\mathbf{A}\). We know that \(\mathbf{A}\) is _low rank_ for \(\alpha<M/N\). Set the range of \(\alpha\) to \([0.2\;0.3\ldots 1.0]\). Since GAMP totally diverges at every \(\alpha\) with type 1 and type 2 cases, it is not visible in Figure 1(a),b. AMP also totally diverges at every \(\alpha\) with type 2 case, therefore it is also not visible in Figure 2b. The two figures show that BGP-GAMP remains stable even in a low rank scenario \(\alpha\approx 0.4\), and its performance is obviously better than AMP and BP, and a little better than OMP. It is worth noting that the threshold 0.1 in Figures 1 and 2 is the relative mean square error, not absolute mean square error, which means the average error amplitude is just \(1/100\) of the original signal amplitude. These figures show, for instance, that the standard AMP algorithm and BP algorithm are approaching this threshold. Therefore, it is not a poor performance. We do not consider MAP-GAMP since MAP estimation is not general as MMSE estimation, please see [11] Section 3.6.3 for more discussion. The last experiment uses real world data, namely, a segment of music by [PERSON]. The data has 81,000 sample points, and it is segmented to 54 blocks, each block has \(N=1500\) sample points. The compressed sampling rate is set to \(1/3\), therefore, the measurement number is \(M=500\).