# A Two-Stage Method to Test the Robustness of the Generalized Approximate Message Passing Algorithm
## 4 Bernoulli-Gaussian Pursuit GAMP Algorithm  
The hypothesis of FS-GAMP algorithm is a known support \(\Lambda\), but we do not know it. Now back to BG-GAMP, Equations (15) and (16) use the marginal posterior probability \(\pi_{n}\) to weight the non-zero estimation part \((\gamma_{n},\mu_{n})\) and the zero prior part \(\theta\). At each iteration of BG-GAMP, when \(\pi_{n}\) is greater than zero-one switch threshold \(\zeta=0.5\), the non-zero estimation part takes over the major contribution. In this research we suppose that the non-zero prior probability of every entry in \(\mathbf{x}\) is 0.5. That implies the maximal entropy assumption. Therefore, the zero-one switch threshold is also set to 0.5 in accordance with the maximal entropy assumption. For a matrix which does not meet RIP conditions very well, we observe that the mean and the variance of one \(\pi_{n}>\zeta\) entry shows no sign of convergence, while some entries' \(\pi_{j}<\zeta,j\
eq n\) already increase fast. When they are greater than \(\zeta\), the means and the variances of these entries also show no sign of convergence. This phenomenon spreads to more and more entries, causing all entries to be totally diverged. This observation inspires us to maintain the current computing status until one \(\pi_{n}>\zeta\) entry has converged, and then continue the next entry (or entries). In other words, we introduce a pursuit process of lines (4)-(6) in Algorithm 3 to sequentially find the support of \(\mathbf{x}\), and then estimate the amplitudes on this support by FS-GAMP. BGP-GAMP means BG-GAMP with an intrinsic pursuit process. The steps of BGP-GAMP are listed in Algorithm 3. Note that the initial input parameters of FS-GAMP in line (7) are the output parameters of GAMP in line (3). ```
Input:\(\mathbf{y},\mathbf{A},\Lambda\) Description:\(\mathbf{x}(t+1),\
u^{\mathbf{x}}(t+1)\)
1:\(\hat{\mathbf{x}}_{\Lambda}(t=1)\leftarrow\mathbb{0}^{|\Lambda|\times 1};\
u^{ \Lambda}(t=1)\leftarrow\mathbb{0}^{|\Lambda|\times 1};\hat{\mathbf{s}}(t=0) \leftarrow\mathbb{0}\)
2:repeat
3:\(\
u^{\mathbf{r}}(t)\leftarrow|\mathbf{A}_{\cdot,\Lambda}|^{2}


```
1:\(\mathbf{y},\mathbf{A}\)
2:\(\mathbf{x}(t+1),\
u^{\mathbf{x}}(t+1)\)
3:\(\hat{\mathbf{x}}(t=1)\leftarrow\mathbf{0};\
u^{\mathbf{x}}(t)\leftarrow\mathbf{1} ;\hat{\mathbf{s}}(t=0)\leftarrow\mathbf{0};\Lambda\leftarrow\varnothing\)
4:repeat
5: {(line 3)-(line 12) of GAMP}
6:\(\pi(t+1)\leftarrow[\pi_{n}(t+1)]\), where \(\pi_{n}(t+1)\) obtained from (12)
7:\(J\leftarrow\{j:\pi_{j}(t+1)>0.5\}\)
8:\(\Lambda\leftarrow\Lambda\cup J\)
9: {FS-GAMP}
10:until Terminated. ```

**Algorithm 3**Bernoulli-Gaussian Pursuit GAMP (BGP-GAMP). ## 5 Experiments

We investigate the performance of BGP-GAMP by three experiments. Four benchmark algorithms are adopted to compare with BGP-GAMP. Orthogonal matching pursuit (OMP) [9] and basis pursuit (BP) by interior point method to solve linear programming [10] are the most robust \(\ell_{0}\) and \(\ell_{1}\) optimization algorithms, other algorithms (old or new) are weaker than them in robustness. AMP and GAMP are not only the root cause of the robust problem, but also the basis of our method. The implementation of OMP comes from ([[http://www.cmc.edu/pages/faculty/DNeedell](http://www.cmc.edu/pages/faculty/DNeedell)]([http://www.cmc.edu/pages/faculty/DNeedell](http://www.cmc.edu/pages/faculty/DNeedell))), BP comes from \(11 magic\) ([[http://users.ece.gatech.edu/justin/11](http://users.ece.gatech.edu/justin/11) magic]([http://users.ece.gatech.edu/justin/11](http://users.ece.gatech.edu/justin/11) magic)), AMP comes from [PERSON]'s work ([[http://people.epfl.ch/ulugbek.kamilov](http://people.epfl.ch/ulugbek.kamilov)]([http://people.epfl.ch/ulugbek.kamilov](http://people.epfl.ch/ulugbek.kamilov))) and GAMP comes from _gamplab_ ([[http://eeweb.poly.edu/srangan/index.html](http://eeweb.poly.edu/srangan/index.html)]([http://eeweb.poly.edu/srangan/index.html](http://eeweb.poly.edu/srangan/index.html))).