# Constrained Backtracking Matching Pursuit Algorithm for Image Reconstruction in Compressed Sensing
## 4 Experimental Results  
Several experiments were conducted to illustrate the performance of the CBMP algorithm. The proposed CBMP was compared with SAMP [23] and IGSAMP [26]. The halting condition used by these algorithms was \(\|y_{r}\|\leqslant 10^{-5}\). For a fair comparison, the same initial step size was used by CBMP, SAMP, and IGSAMP. It should be noted that in SAMP and IGSAMP, the reconstruction results shown in their simulation experiments [23; 26] are obtained by a small step size (s = 1). In practical applications, when two-dimensional images are stacked into long one-dimensional vectors, the sparsity level in the transform domain is far greater than one. Correspondingly, the step sizes of the proposed algorithm were relatively large. The step sizes used in the experiment were 64, 128, 256, and 512, respectively. Different sampling rates were used to demonstrate the reconstruction performance of CBMP. The wavelet transform was chosen as the sparse basis to represent images. The quality of recovered images was measured by the peak signal-to-noise ratio (PSNR), which is expressed as:  
\[\text{MSE}=\frac{1}{M\times N}\sum_{i=0}^{M-1}\sum_{j=0}^{N-1}|I(i,j)-\hat{I}(i,j)|^{2} \tag{5}\]  
\[\text{PSNR}(I,\hat{I})=10\log_{10}\left(\frac{\text{MAX}}{\text{MSE}}\right) \tag{6}\]  
Figure 3: The flowchart of the constrained backtracking matching pursuit (CBMP) algorithm. where \(M=N=512\), \(I(i,j)\) denotes the original value of the test image at the position \((i,j)\) and \(\bar{I}(i,j)\) denotes the reconstructed value at the position \((i,j)\). The maximum pixel intensity is given as MAX. All images here are expressed using 8 bit intensity values per pixel, so the peak intensity is 255. The experiment configuration is as follows: the CPU was an Intel(r) CoreTM i5-7200U at 2.50 GHz, and the size of the RAM was 8 GB. The programming language used to perform the experiments was MATLAB. Several experiments were conducted to validate the advantages of CBMP. According to Theorem 1, \(\|x\|_{2}^{2}>\frac{1}{\sqrt{2}}\|y\|_{2}^{2}\). In CBMP, \(x_{F}\) should gradually approach the true one and \(x_{F}\) is much smaller than \(x\) at the beginning. Simultaneously, there are two update stages, and then, the threshold parameter \(a\) is contracted within \(\frac{1}{4\sqrt{2}}\left(\frac{1}{2}\times\frac{1}{2}\times\frac{1}{\sqrt{2}}\right)\). Our experiments demonstrate that the threshold parameters \(a\) and \(b\) do not distinctively affect the reconstruction performance if the parameter satisfies \(a\leq\frac{1}{4\sqrt{2}}\). In CBMP, the support set of the signal obtained by the current iteration is constrained by the parameter \(a\) in the step size update stage, while U\({}_{i}\) is the union of the estimated support set of the previous iteration and the currently selected support set. Therefore, the relationship between these two parameters is set as \(b=2a\). These two parameters play different roles, as \(a\) is used after the final test, while \(b\) corresponds to the union operation after the preliminary test. The relationship between the threshold parameters and reconstruction performance is shown in Figures 4 and 5. Meanwhile, SAMP and IGSAMP are both tested. Two standard images, \"Lena\" and \"Peppers\", were reconstructed to test the reconstruction performance of different parameter pairs \((a,b)\). For a fair comparison, the sampling rate was 0.4, and the same initial step sizes were used. The initial step sizes were chosen from 64 to 512. From Figure 4, we can see that the reconstruction performance of CBMP with different threshold parameters is better than that of SAMP and IGSAMP. For example, when \(a=\frac{1}{16\sqrt{2}}\), all the PSNR values of CBMP with different initial step sizes are greater than 33.5. While the initial step size is 512, SAMP achieves the maximum PSNR value, which is less than 32, and IGSAMP offers the maximum PSNR value, which is less than 32.5. Therefore, CBMP offers better reconstruction performance than SAMP and IGSAMP.