# Feasibility Pump Algorithm for Sparse Representation under Gaussian Noise
## 1 Problem Formulation  
The sparse representation of a signal \(y\in\mathbb{R}^{m}\) is the solution \(x\in\mathbb{R}^{n}\) with the smallest number of nonzero elements to the under-determined system \(y=Dx\), where \(D\in\mathbb{R}^{m\times n}\), \(m<n\), is a given matrix named dictionary. Since in most cases noise is involved, the data misfit measure is minimized. Also, rather than attempting to find the sparsest solution, it is easier to bound the number of nonzero elements by a given threshold \(K\) and so the sparse representation can be found by solving the optimization problem  
\[ \begin{split}\underset{x\in\mathbb{R}^{n}}{\text{minimize}}& \quad\|y-Dx\|_{2}\\ \text{subject to}&\quad\|x\|_{0}\leq K.\end{split}  \tag{1}\]  
Since the 2-norm is involved, the assumption is that the noise is Gaussian. This is still an NP-hard problem. A common way to treat (1) is to replace the \(l_{0}\) norm with the \(l_{1}\) norm, thus relaxing the problem to a convex one. Transferring also the constraint into the objective, the result is a lasso style problem:  
\[\underset{x\in\mathbb{R}^{n}}{\text{minimize}}\quad\|y-Dx\|_{2}^{2}+\lambda\| x\|_{1}. \tag{2}\]  
A less used approach takes into account the fact that the number of non-zero coefficients in (1) is bounded using the \(l_{0}\) norm, hence Mixed Integer Programming (MIP) algorithms can be considered to solve the problem as it is posed, using either an integer variable for the number of coefficients or the binary decision whether a coefficient is used for the representation or not. The Feasibility Pump (FP), proposed in References [1,2], is an MIP algorithm that alternates between solving the problem with relaxed integer constraints and the one satisfying the integer requirements. This is done until a point is reached that satisfies all the constraints, even though it might be not optimal, or for a prescribed number of iterations. The Feasibility Pump begins at an initialsolution and then proceeds through several iterations to minimize the difference between the solutions of the alternating problems. Several modifications and improvements [3; 4; 5; 6; 7; 8; 9; 10] have been proposed for this algorithm. See the bibliography in Reference [11] for a more extensive image. The case in which the \(l_{1}\) norm is used for the representation error was analyzed and a modification of the Feasibility Pump algorithm for this problem was presented in Reference [12]. We propose to combine the MIP approach with the lasso problem (2). The binary variable \(b\in\left\{0,1\right\}^{n}\) is introduced to perform the role of an indicator that shows which atom of the dictionary \(D\) is used for the representation of \(y\). We then combine (1) with (2) to obtain the problem  
\[ \begin{array}{ll}\underset{x\in\mathbb{R}^{n},b\in\left\{0,1\right\}^{n}} {\text{minimize}}&\|y-Dx\|_{2}^{2}+\lambda\|x\|_{1}\\ \text{subject to}&1_{n}^{T}b\leq K\\ &-Mb\leq x\leq Mb,\end{array}  \tag{3}\]  
where \(\mathbf{1}_{n}\) is a vector of length \(n\) whose elements are all equal to \(1\). The \(l_{1}\) regularization enforces the sparsity condition on the representation \(x\), as the \(l_{1}\) norm favors sparsity, and helps the convergence of the Feasibility Pump algorithm, which will be used as an (approximate) MIP solver. As in Reference [13], a pioneer of MIP techniques for sparse representations, the big-\(M\) trick is employed in (3), where \(M\) is a preset parameter chosen as \(M=1.1\|D^{T}y\|_{\infty}/\|D\|_{2}^{2}\). This is used to bound the size of the representation coefficients. Note that if \(b=0\), then \(x=0\); if \(b=1\), then \(x\) is practically free, since the constraint \(|x|\leq M\) is of no consequence due to the large value of \(M\). Finally, to implement problem (3), an auxiliary variable \(w\in\mathbb{R}^{n}\) is introduced for the regularization term, resulting in  
\[