# Feasibility Pump Algorithm for Sparse Representation under Gaussian Noise
## 2 Algorithm  
Algorithm 1 solves the reformulation (4) of problem (1). It is similar in structure to that in Reference [12], although the underlying optimization problem and some important details are different. We will point out the differences when they are presented. The Feasibility Pump algorithm starts with the computation of the solution for the relaxed version of the initial problem (4), where \(b\) takes values in the \([0,1]^{n}\) interval, instead of being a binary variable. The problem becomes convex; more precisely, it belongs to quadratic programming; the MATLAB function quadprog is used to solve it, based on an interior-point algorithm; other solvers or packages could be used as well. The real solution \(b\) is rounded to the vector \(\widetilde{b}\in\left\{0,1\right\}^{n}\). The largest \(K\) elements of \(b\) are rounded upwards to \(1\), while the others are rounded downwards to \(0\). Indirectly, a sparse solution is obtained with exactly \(K\) elements. ```
Data: Dictionary \(D\in\mathbb{R}^{m\times n}\), signal to represent \(y\in\mathbb{R}^{m}\), number of non-zero coefficients used for the representation \(K\in\mathbb{Z}\), maximum number of iterations Iter, weight parameters \(\alpha\), \(\lambda\), \(\gamma\) Result: a feasible solution \(x\in\mathbb{R}^{n}\) Solve relaxed (4) with \(b\in[0,1]^{n}\). The vectors \(x\) and \(b\) are obtained. Use rounding procedure to obtain vector \(\widetilde{b}\). whilenumber of iterations \(\leq Iter\)do  Solve problem (5). The vectors \(x\) and \(b\) are obtained. if\(b\) isintegerthen  return \(x\);  end if  Use rounding procedure to obtain vector \(\widetilde{b}\). ifcycle is detectedthen  Use perturbation on \(\widetilde{b}\). end if  Update the value of \(\alpha\) using (6). end if  Use Least Squares Method to optimize the error for the found support. ```  
**Algorithm 1**Modified Feasibility Pump. In each iteration of the Feasibility Pump, the vector \(b\) and the tentative solution \(x\) are updated by solving  
\[ \begin{split}\operatorname*{minimize}_{x\in\mathbb{R}^{n},\
u\in \mathbb{R}^{n},b\in[0,1]^{n}}&(1-\alpha)\triangle(b,\widetilde{b })+\alpha\left[\frac{K}{err_{init}^{2}}(x^{T}D^{T}Dx-2y^{T}Dx)+\lambda 1_{n}^{T}w \right]\\ \text{subject to}& 1_{n}^{T}b\leq K\\ &-w\leq x\leq w\\ & w\leq Mb,\end{split}  \tag{5}\]  
where \(\triangle(b,\widetilde{b})=\|b-\widetilde{b}\|_{1}\) and \(err_{init}\) is the representation error at the initial Feasibility Pump step (4). This quadratic programming problem is also solved with quadprog in MATLAB. The iteration step has an objective that combines the representation error \(\|y-Dx\|_{2}\) with a term that enforces the new solution \(b\) to be near from the current integer vector \(\widetilde{b}\), with the aim of making the solution \(b\) nearer from a binary vector. This kind of modification, named Objective FP, is proposed in Reference [3] and is essential in our case for finding good values of the objective; feasibility is easy to obtain, since rounding always gives a \(K\)-sparse solution, and so the original FP [1] would always converge in one iteration, possibly to a poor solution. After each iteration, the parameter \(\alpha\) is reduced and the integer condition will weigh more than the error objective. The reduction of \(\alpha\) is done by multiplication with a value \(\gamma\in(0,1)\):  
\[\alpha\leftarrow\gamma\alpha. \tag{6}\]  
A large \(\gamma\) will give the smallest error, but the execution time is longer, while a smaller \(\gamma\) offers faster results, but with a larger error. During our tests, it was observed that the addition of the factor \(\frac{K}{err_{init}^{2}}\) in (5) is necessary to increase the influence of the error in the optimization process because the error is much smaller than the \(\triangle(b,\widetilde{b})\) and \(\|x\|_{1}\) terms and it needs an additional weight parameter.