# Constrained Backtracking Matching Pursuit Algorithm for Image Reconstruction in Compressed Sensing
## 3 The Constrained Backtracking Matching Pursuit Algorithm for Image Reconstruction  
To overcome the sensitivity to the step size and improve the reconstruction performance of greedy pursuit algorithms, we propose the CBMP algorithm, which introduces restrictions to the backtracking stage, which provides more flexibility as the algorithm gradually approaches the true sparsity level of the unknown signal. The main steps of CBMP are described as follows:  
Considering the signal to be reconstructed is a two-dimensional image, the sparsity level is relatively large; the process of sparsity level estimation is divided into large and small step size estimation stages. In the large step size stage, the increment of the step size  
Figure 2: Performance of SAMP vs. different step sizes. is \(s^{j}=2\times s^{j-1}\). \(j\) denotes the stage iteration index. The increment of the sparsity level in the stage of the small step size is fixed and equals the step size of the previous stage. Due to the advantages of combing information and improving accuracy [34; 35], a composite strategy is proposed to effectively control the increment of the estimated sparsity level in the two stages. It includes two constraints controlled by parameters \(a\) and \(b\), which are required in the backtracking threshold operation of CBMP, as described in Algorithm 2. The theoretical support for the composite strategy is clarified as follows:  
**Theorem 1**. : _Let \(x\in R^{N}\) be a sparse signal and \(y\) be a measurement vector. If the measurement matrix \(\Phi\) satisfies the RIP, then \(\|x\|_{2}^{2}>\frac{1}{\sqrt{2}}\|y\|_{2}^{2}\). The proof is presented in Appendix A._  
```
Input: \(M\times N\) measurement matrix \(\Phi\), measurement vector \(y\), step size \(s^{0}\) Initialization: \(x=0\{\text{trivial Initialization }\};y_{r}^{0}=y\{\text{initial residue }\};T^{0}=\varnothing\{\text{the estimated support set }\};L^{0}=s^{0}\{\text{size of the support set (sparsity level)}\};j=1\{\text{stage index}\};\) i=1\(\{iterationindex\}\) ; \(\text{U}^{0}=\varnothing\{\text{ union set }\}\) Repeat the following steps until the stopping condition holds:
1. Preliminary test: \(v=\Phi^{T}y_{r}^{i-1}\), find the matched set \(D^{i}=\{L^{j-1}\text{ indices corresponding to the largest absolute values of }v\}\), that is \(D^{i}=\max(|\Phi^{T}y_{r}^{i-1}|,L^{j-1})\). 2. Union operation: to broaden the selection space and make candidate list \(\text{U}^{i}:\text{U}^{i}=T^{i-1}\cup D^{i},x_{\text{U}^{i}}=\Phi^{\dagger}_{ \text{U}^{i}}y\). 3. Final test: to obtain the vector \(x_{F}^{i}\) : find the matched indices \(F^{i}\) based on the largest absolute values of \(x_{\text{U}^{i}}\), that is \(F^{i}=\max(|x_{\text{U}^{i}}|,L^{j-1}),\quad x_{F}^{i}=\Phi^{\dagger}_{F^{i}}y\). 4. Compute residual: \(r_{F}^{i}=y-\Phi_{F}x_{F}^{i}\). 5. Backtracking threshold operation:  if \(\left\|x_{F}^{i}\right\|_{2}^{2}\leq a\|y\|_{2}^{2}\) and \(\text{size}(\text{U}_{i})<b\times M\), then shift into the large step size estimation stage: \(s^{j}=2\times s^{j-1},\quad L^{j}=L^{j-1}+s^{j},\quad y_{r}^{i}=y_{r}^{i-1},j= j+1,i=i+1\), then shift into \(1\). \(\text{if }\left\|r_{F}^{i}\right\|_{2}>\left\|y_{r}^{i-1}\right\|_{2}\), then shift into the small step size estimation stage: \(s^{j}=s^{j-1},L^{j}=L^{j-1}+s^{j},\quad y_{r}^{i}=y_{r}^{i-1},j=j+1,\quad i=i+1\), then shift into \(1\). Otherwise, shift into the stage that updates the support set based on the current estimated sparsity level: \(y_{r}^{i}=r_{F}^{i},L^{j}=L^{j-1},\quad T^{i}=F^{i},\quad i=i+1\), then shift into \(1\). Output:\(x=\Phi^{\dagger}_{T}y\) \(\{\text{ a sparse reconstruction computed by the least squares algorithm }\}\)
```  
**Algorithm 2** The proposed CBMP algorithm  
According to Theorem 1, the energy of the original signal \(x\) is greater than the square root of one half of that of the measurement vector \(y\), that is \(\|x\|_{2}^{2}>\frac{1}{\sqrt{2}}\|y\|_{2}^{2}\). Different step sizes are used in CBMP.