# Constrained Backtracking Matching Pursuit Algorithm for Image Reconstruction in Compressed Sensing
## 2 Preliminaries
### A Review of the Greedy Pursuit Algorithms  
Among the reconstruction algorithms used in CS, the greedy pursuit algorithms are the most widely used due to their easy implementation and low computational complexity. The goal of greedy pursuit algorithms is to find the support set of the unknown signal. After finding the support set, the signal can be reconstructed by solving a least squares problem [31; 32; 33]. There exit the indices of the optimal support set \(J\in\{1,2,\ldots,n\}\), and \(z^{*}\) satisfies \(y=z^{*}\varphi_{j}\). \(\varphi_{j}\) is the \(J\)-th column (index) of \(\Phi\). Then, the error function \(e(j)\) is:  
\[e(j)= \min_{z}\bigl{\|}z\varphi_{j}-y\bigr{\|}_{2}^{2}=\min_{z}\Bigl{[} \Bigl{(}\varphi_{j}^{T}\varphi_{j}\Bigr{)}z^{2}-2\Bigl{(}\varphi_{j}^{T}y \Bigr{)}z+y^{T}y\Bigr{]}\] \[= \min_{z}\Bigl{(}\varphi_{j}^{T}\varphi_{j}\Bigr{)}\biggl{(}z- \frac{\varphi_{j}^{T}y}{\varphi_{j}^{T}\varphi_{j}}\biggr{)}^{2}+y^{T}y-\frac{ \Bigl{(}\varphi_{j}^{T}y\Bigr{)}^{2}}{\varphi_{j}^{T}\varphi_{j}}\]  
Letting \(e(j)=0\), the optimal solution:  
\[z^{*}=\left\{ \begin{array}{l}\frac{\varphi_{j}^{T}y}{\|\varphi_{j}\|^{2}},j =J\\ 0,\text{ otherwise.}\end{array} \right\} \tag{4}\]  
The matching pursuit (MP) algorithm is one of the most classical and primitive greedy pursuit algorithms. As described in Equation (4), only the column \(J\) minimizing the error function is selected in each iteration of the MP algorithm [32]. Later on, the OMP algorithm [15] was developed based on the MP algorithm. As stated in OMP, some indices are searched, corresponding to the most significant correlations between the measurement matrix and the residual. In each iteration, only one or more coordinates are selected and added to the support set. These selected coordinates correspond to the columns (indices) of observation matrices with the largest correlation with the residuals. The optimization iterates until the termination condition is satisfied. Finally, the pseudo-inverse of the observation matrix corresponding to the obtained support set is used for signal reconstruction. CS-based greedy pursuit algorithms adopted in CS include OMP [15; 16; 17], StOMP [18], ROMP [19; 20], SP [21], CoSaMP [22], SAMP [23], EAMP [24], and IGSAMP [26]. Utilizing some criteria, they can approximate the sparse signals iteratively. Each of the algorithms iteratively computes the estimated support set of the signals. In each iteration, one or several coordinates are added to the support set. In particular, in OMP, only one column of \(\Phi\) is added to the estimated support set. In StOMP, a hard threshold is used to choose several columns that are to be added to the support set. Both algorithms have to select these columns previously. Otherwise, these algorithms cannot be rectified. These greedy pursuit algorithms required more measurements for exact reconstruction and lacked stable reconstruction capability until the backtrackingidea was introduced in SP [21] and CoSaMP [22]. Refining the last estimated support set, the backtracking scheme allows eliminating the wrong coordinates, which are selected in the previous iterations. The candidate set is introduced into the greedy pursuit algorithm, which is the key point of the backtracking. However, both SP [21] and CoSaMP [22] require prior knowledge about the sparsity level \(k\), which is impractical to know previously. SAMP [23], on the other hand, was put forward to gradually approach the sparsity level by accumulation with a step size. The SAMP algorithm is shown in Figure 1 and Algorithm 1. ```
Input:\(M\times N\) measurement matrix \(\Phi\), measurement vector \(y\), step size \(s\) Initialization:\(\hat{x}=0\) {Trivial Initialization}, \(r^{0}=y\) {Initial residue}, \(U^{0}=\emptyset\) {the estimated support set}, \(L=s\) {size of the support set}, \(j=1\) { stage index}, \(i=1\) { iteration index}. Repeat:
1. Preliminary test: find the matched L indices from \(\Phi\) based on the correlation between \(\Phi\) and \(\hat{r}^{i-1}\), that is \(D^{i}=max(|\Phi^{T}\hat{r}^{i-1}|,L)\). 2.