# Backtracking-Based Iterative Regularization Method for Image Compressive Sensing Recovery
## 3 Image CS Recovery via Backtracking-Based Adaptive IST
### BAIST Algorithm for Solving the New Objective Function  
Firstly, we offer the procedure for solving Equation (3) with the IST algorithm outlined in Algorithm 2, named ISTANR (IST with adaptive nonlocal regularization). In step (a), the fidelity term is optimized by gradient descent to get a solution \(x_{g}\), which can be regarded as a noise image. Step (b) is a proximity denoising correction step implemented through the use of nonlocal thresholding. ```
Input:\(y\), \(\mathbf{A}\), \(s\), \(c\), \(x^{0}=0\) for\(k=1\)to\(K\)do (a) \(x_{g}=x^{k}-c\
abla f(x^{k})\) (b) \(x^{k}=\underset{x}{\text{argmin}}\{\mu\sum\limits_{i=1}^{G}\left\|\mathbf{ \Gamma_{3D}}x_{i}\right\|_{0}+\left\|x-x_{g}\right\|_{2}^{2}/(2c)\}\) endfor
```  
**Algorithm 2** IST with Adaptive Nonlocal Regularization  
Secondly, we solve Equation (4) with ISTANR by letting \(g(x)=\frac{1}{2}\|y-\mathbf{A}x\|_{2}^{2}+\sum\limits_{j=1}^{B}\frac{b_{j}}{2 }\|x-x^{(k-j)}\|_{2}^{2}\), and substituting \(f(x)\) for \(g(x)\). The proposed method named BAIST (backtracking-based adaptive IST) is summarized in Algorithm 3, where \(\
abla g(x^{k})=-\mathbf{A}^{*}(y-\mathbf{A}x^{k})+\sum\limits_{j=1}^{B}b_{j} (x^{k}-x^{(k-j)})\). Unlike ISTANR which obtains the noisy observation of \(x\) (i.e., \(x_{g}\)) using the fidelity term, BAIST super-adds the difference between the current solution and the previous ones, and thus obtains a noisier \(x_{g}\) for avoiding prematurity. It can be confirmed in Figure 1 that BAIST yields the intermediate result of \(x_{g}\) with more details. ```
Input:\(y\), \(\mathbf{A}\), \(b_{1}\), \(b_{2}\),..., \(b_{B}\), \(s\), \(c\), \(x^{0}=0\) for\(k=1\)to\(K\)do (a) \(x_{g}=x^{k}-c\
abla g(x^{k})\) (b) \(x^{k}=\underset{x}{\text{argmin}}\{\mu\sum\limits_{i=1}^{G}\left\|\mathbf{ \Gamma_{3D}}x_{i}\right\|_{0}+\left\|x-x_{g}\right\|_{2}^{2}/(2c)\}\) endfor
```  
**Algorithm 3** Backtracking-Based Adaptive IST  
The key to success in implementing both BAIST and ISTANR is to compute the proximity denoising correction. We use a lemma in [15], namely the minimization problem:  
\[\hat{x}=\underset{x}{\text{argmin}}\frac{1}{2}\|x-a\|_{2}^{2}+\lambda\|x\|_{0} \tag{5}\]which has a closed form solution, expressed as:  
\[\hat{x}=\text{hard}(a,\sqrt{2\lambda})=\left\{ \begin{array}{ll}a,&\text{if }\text{abs}(a)-\sqrt{2\lambda}>0\\ 0,&\text{otherwise}\end{array} \right. \tag{6}\]  
Since the orthogonal transform \(\mathbf{\Gamma_{3D}}\) has the property of energy conservation, step (b) can be written as:  
\[x=\text{arg}\underset{x}{\min}\{3\mu\sum\limits_{i\in G}\left\|\mathbf{ \Gamma_{3D}}x_{i}\right\|_{0}+\frac{\sum\limits_{i\in G}\left\|\mathbf{ \Gamma_{3D}}x_{i}-\mathbf{\Gamma_{3D}}(x_{g})_{i}\right\|_{2}^{2}}{2 cN}\} \tag{7}\]  
Its solution is:  
\[\left(x\right)_{i}=\text{hard}(\mathbf{\Gamma_{3D}}(x_{g})_{i^{\prime}}\sqrt{ 6\mu cN})=\left\{ \begin{array}{ll}\mathbf{\Gamma_{3D}}(x_{g})_{i^{\prime}}& \text{if }\text{abs}(\mathbf{\Gamma_{3D}}(x_{g})_{i})-\sqrt{6\mu cN}>0\\ 0,&\text{otherwise}\end{array} \right. \tag{8}\]  
where \(x_{i}\) and \(\left(x_{g}\right)_{i}\) are the \(i\)-th similar patches 3D group of \(x\) and \(x_{g}\), respectively. Since a patch may be assigned to several 3D groups, the patches in the last item of Equation (7) are repetitively computed. Let \(N\) be a scale factor for balancing the increasing energy caused by the repetitive computation; however, we can directly set the threshold of the hard thresholding operator in Equation (8) \(\delta=\sqrt{6\mu cN}\), rather than computing \(N\) and selecting an appropriate regularization parameter \(\mu\). Apparently, the threshold \(\delta\) should be reduced with the increasing iteration number to gain a more and more clear image, which is similar to the continuation strategy [15] in IST-type methods. A natural idea is that \(\delta\) is proportional to the observation residual in CS reconstruction:  
\[\delta=s\sqrt{\left\|y-\mathbf{A}x_{g}\right\|_{2}^{2}/m} \tag{9}\]  
where \(s\) is a scale factor and can be set empirically.