# Feasibility Pump Algorithm for Sparse Representation under Gaussian Noise
## 2 Algorithm
The division with the square of the error removes the difference of the orders in magnitude between the \(\triangle(b,\widetilde{b})\) term, regularization term and the error term during the first iteration steps. With each iteration the importance of the error termsdecays. Without the weight, the importance of the error term decays too fast and has little effect in the optimization process; the weight is used so that the error term plays an important role for more iterations of the algorithm. The factor \(K\) is added such that the error term is as important as the \(\triangle(b,\widetilde{b})\) term for more time, as \(\alpha\) decreases the importance of the error term. It also helps the choice of \(\lambda\). As \(0\leq\triangle(b,\widetilde{b})\leq 2K\), with \(2K\) being nearly impossible to attain, the multiplication with \(K\) puts both the error and the feasibility term on similar weights; without the \(K\) value, the square error would only normalize the error term, while the magnitude of the \(\triangle(b,\widetilde{b})\) term would act as a weight that forces the algorithm to focus more on getting a sparse solution, than on reducing the representation error. We note that directly using the algorithm from Reference [12], without the factor \(\frac{K}{\sigma r_{init}^{2}}\), leads to poor results. Balancing the terms of the objective, like we did in (5), is also done in Reference [9], but with different means. The regularization term \(\|x\|_{1}\) has a double role. It helps enforce the desired sparsity and also helps the algorithm to converge when the dictionary is ill conditioned. The lack of the regularization term increases the running time of the algorithm, sometimes not even reaching convergence. The \(\lambda\) tuning parameter is very important as it influences heavily the performance of the model, as shown in Reference [14]. Note that at the end of Algorithm 1, when the support is settled, the regularization term is removed and the (optimal) least squares solution corresponding to that sparse support is computed; such a feature was not present in Reference [12]. The perturbation strategy used when cycles occur in the Feasibility Pump iterative process is similar to the one used in Reference [12]; it belongs to the category of strong perturbations, as all elements of \(\widetilde{b}\) are perturbed. Inspired by Reference [6], we consider that a cycle appears when one of the following conditions is met (we use index \(t\) for the current iteration and \(t-1\) for the previous one): (i) \(\widetilde{b}\) is the same as in the previous iteration and \(|\alpha_{t}-\alpha_{t-1}|<10^{-3}\) (note that even if \(\widetilde{b}\) is the same, different values of \(\alpha\) lead to different solutions in (5)), (ii) \(\|b_{t}-b_{t-1}\|<10^{-4}\), (iii) \(\|b_{t}-b_{t-1}\|\geq 0.9\|b_{t-1}-b_{t-2}\|\); the last two conditions take into account both the absolute value of \(\|b_{t}-b_{t-1}\|\) and its relative change with respect to the previous iteration. The algorithm described above is named Sparse Quadratic Feasibility Pump (SQFP). Unlike the Branch and Bound algorithms from Reference [13], SQFP may not attain the optimal solution, but it has a running time that is comparable with those of popular algorithms for sparse representation. In contrast, the MIP algorithms from Reference [13] may be extremely slow for some problems.