# Feasibility Pump Algorithm for Sparse Representation under Gaussian Noise
## 3 Results  
In order to obtain numerical results, the testing scheme from Reference [12] is used, with the significant distinction that noise is now Gaussian. In a first test, for which we report extensive results, we use randomly generated dictionaries with condition numbers of 100, 1000, 10,000 and 100,000. For each condition number, 160 dictionaries of size \(80\times 200\) are generated. The test signals are obtained with \(y=Dx_{\text{true}}+u\), where the solutions \(x_{\text{true}}\) have \(K\in\{5,7,9,11\}\) nonzero coefficients generated randomly following a Gaussian distribution, in random positions; the noise \(u\) is Gaussian and its variance is chosen such that the signal to noise ratios have values \(10,20,30\), \(\infty\). For the computation of the representation error, the relative error  
\[e=\frac{\|Dx-y\|_{2}}{\|y\|_{2}} \tag{7}\]  
is used (where now \(x\) is the computed solution), in accordance with the formulation of the initial problem (1). We have implemented SQFP as shown in Algorithm 1. The initial weight \(\alpha\) is set to 1 and is multiplied by an update factor \(\gamma=0.9\) at each iteration; these values seem to provide a good compromise between convergence speed and representation error. The number of iterations \(Iter\) is set to 1000. We run SQFP with 50 equally spaced values of the regularization parameter \(\lambda\) from 0 to 1. The value for which the mean representation error is the smallest is considered the best choice for \(\lambda\). Several types of algorithms have been proposed [15] to find the solution of (1) or its relaxed version (2). The OMP (Orthogonal Matchmaking Pursuit) [16] and the FISTA (Fast Iterative Shrinkage-Thresholding Algorithm) [17] algorithms where chosen for comparison as they are some of the most commonly used. Both FISTA and SQFP use the regularization parameter \(\lambda\). FISTA is tested with 500 equally spaced values between 0 to 0.05. The algorithms are implemented in MATLAB and tested on a computer with a 6-core 3.4 GHz processor and 32 GB of RAM. The variation of the error produced by SQFP depending on \(\lambda\) is represented in Figure 1 for \(K=11\) and condition number 1000. It can be seen that for the lower SNR values, the error has a relatively well defined minimum around \(\lambda=0.5\) for \(SNR=10\) and \(\lambda=0.18\) for \(SNR=20\). From the minimum point the error increases as \(\lambda\) increases. For the larger SNR values, the error is very small in the beginning, with small variations as \(\lambda\) increases from zero; after a certain value the error increases a lot. In these cases regularization offers very small benefits. An example of relative errors (7) is given in Figure 2, where SQFP shows the ability to consistently produce solutions whose errors are at about the SNR level. In the same conditions, the recovery error \(\|x-x_{\text{true}}\|/\|x_{\text{true}}\|\) has the values shown in Figure 3; although with more variability, the errors decrease nicely with the SNR for all values of \(K\). Figure 1: Mean representation error depending on \(\lambda\) for \(K=11\), for matrix conditioning of 1000. The mean errors obtained by running the tests are displayed in Figures 4-7. The first (red) bar in each cell corresponds to the relative error of FISTA, the second (green) is for SQFP and the last (blue) is for OMP. It can be seen that as the sparsity level \(K\) increases, the SQFP algorithm has a much smaller representation error than FISTA and, only for some condition numbers, than OMP. For \(K=5\) and \(K=7\), the difference between the algorithms is very small. For larger \(K\), SQFP is clearly better. To evaluate the complexity of the algorithms, we note that the mean number of iterations is 43.33 for SQFP and 726.56 for FISTA. The FISTA iterations are much less complex and time consuming. The average running time for SQFP is 1.09 s, for FISTA is 0.43 s and for OMP is 0.0025 s.  
Figure 3: Recovery errors for SQFP for matrix conditioning of 10,000.