# Constrained Backtracking Matching Pursuit Algorithm for Image Reconstruction in Compressed Sensing
## 2 Preliminaries
### A Review of the Greedy Pursuit Algorithms
Make the candidate list: \(U^{i}=T^{i-1}\bigcup D^{i},x_{U^{i}}=\Phi^{\dagger}_{U^{i}}y\). 3. Final test: \(F=max(|x_{U^{i}}|,L),x_{F}=\Phi^{\dagger}_{F}y\). 4. Compute residual: \(r=y-\Phi_{F}x_{F}\). if the halting condition is true, then quit the iteration; else if \(\|r\|_{2}\geq\|r_{i-1}\|_{2}\), then \(j=j+1\){update the stage index}, \(L=j\times s\) {update the size of support set}; else T\({}^{i}=F\){update the support set}, \(\hat{r}^{i}=r\) { update the residual}, \(i=i+1\). end if Until the halting condition is true; Output: \(x=\Phi^{\dagger}_{T}y\) {update the stage index}, \(L=j\times s\) {a sparse reconstruction computed by the least squares algorithm}
```  
**Algorithm 1** Sparsity adaptive matching pursuit algorithm  
SAMP uses the \"divide and conquer\" principle stage-by-stage to estimate the sparsity level and the true support set of the target signals. SAMP applies two tests, namely the  
Figure 1: The pipeline of sparsity adaptive matching pursuit (SAMP) [23]. preliminary test and the final test, to estimate the signal's support set. The preliminary test is used to implement the selection of the \(L\) largest elements corresponding to the most considerable correlation between the residual and the measurement matrix, denoted by \(D^{i}=\max\bigl{(}\Phi^{T}\mathrm{r}^{i-1}\mid,L\bigr{)}\). After the preliminary test, a candidate list U is created by the union of the chosen list in the preliminary test and the support set in the previous iteration, represented by \(\mathrm{U}^{i}=T^{i-1}\cup D^{i}\). The final test firstly solves a least squares problem to obtain \(x_{\mathrm{U}^{i}}\), and then chooses a subset of the \(L\) largest elements from \(x_{\mathrm{U}^{i}}\). This subset of coordinates serves as the support set of the current iteration. The residual is finally updated by subtracting the measured vector \(y\) from its projection onto the subspace spanned by the columns in the support set. The pseudo-code of SAMP is summarized below. \(\Phi^{\dagger}=\bigl{(}\Phi^{T}\Phi\bigr{)}^{-1}\Phi^{T}\) represents the pseudo-inverse of \(\Phi\), in which \(\Phi^{T}\) denotes the transposition of \(\Phi\). The main innovation of SAMP is that the increment of the residual is used as the criterion to judge the sparsity level by accumulating with the step size. As previously mentioned, SAMP uses a fixed step size that is sensitive to the reconstruction performance [23]. Specifically, when SAMP is applied to two-dimensional images, the selection of the step size seriously affects the image reconstruction performance due to the lack of flexibility and adaptation in the sparsity level update stage. As shown in Figure 2, the reconstruction performance is affected by the step size. When the step size \(s=64\), the peak signal-to-noise ratio (PSNR) is 24.04 dB, whereas when \(s=512\), the PSNR is 28.44 dB. Then, a variable step size was proposed in EAMP [24], but it focuses on one-dimensional sparse binary signal reconstruction. Recently, IGSAMP [26] was proposed to improve SAMP. Furthermore, it requires one to carefully choose the parameters and control the variable nonlinear step size in the reconstruction process and does not refer to the sensitivity to the step size. In this paper, we propose an improved adaptive greedy algorithm, whose signal reconstruction performance is relatively insensitive to the step size.