# Image Recovery with Data Missing in the Presence of Salt-and-Pepper Noise
## 4 Problem Formulation and Algorithm Development
### Alternating Direction Method of Multipliers (ADMM)  
To efficiently solve the optimization problems of Equations (15) and (16), in this paper, the ADMM approach [31] is utilized in which the dual ascent and method of multipliers are utilized recursively. In light of ADMM approach, consider the **Step 1** in Equation (15) first, and since the optimizations of \(\mathbf{n}\) and \(\boldsymbol{\alpha}\) are separable, the estimation of \(\mathbf{n}\) is rewritten as  
\[\text{minimize}\ \|\mathbf{y}-\mathbf{\hat{H}}\mathbf{n}\|_{2}^{2}+\lambda\| \mathbf{n}\|_{1} \tag{17}\]  
with variable \(\mathbf{n}\), where the subscripts are omitted to simplify the notation expression and \(\lambda\) is the regularization parameter. For this problem, the ADMM steps for estimating the \(\mathbf{n}\) at \(l\)th iteration are given by  
\[ \begin{split}\mathbf{n}^{l+1}&=\text{minimize}_{ \mathbf{n}}\big{(}\|\mathbf{y}-\mathbf{\hat{H}}\mathbf{n}\|_{2}^{2}+(\rho/2)\| \mathbf{n}-\mathbf{z}^{l}+\mathbf{s}^{l}\|_{2}^{2}\big{)},\\ \mathbf{z}^{l+1}&=\text{minimize}_{\mathbf{z}} \big{(}\lambda\|\mathbf{z}\|_{1}+(\rho/2)\|\mathbf{n}^{l+1}-\mathbf{z}+ \mathbf{s}^{l}\|_{2}^{2}\big{)},\\ \mathbf{s}^{l+1}&=\mathbf{s}^{l}+\mathbf{r}^{l+1}- \mathbf{z}^{l+1}.\end{split}  \tag{18}\]In the \(\mathbf{n}\)-step of Equation (18), setting the derivative of the cost function with respect to \(\mathbf{n}\) to zero yields  
\[-2\hat{\mathbf{H}}^{\mathrm{H}}\mathbf{y}+2\hat{\mathbf{H}}^{\mathrm{H}}\hat{ \mathbf{H}}\mathbf{n}+\rho(\mathbf{n}-\mathbf{z}^{l}+\mathbf{s}^{l})=0. \tag{19}\]  
Rearranging the terms in Equation (19) produces  
\[(\rho\mathbf{I}+2\hat{\mathbf{H}}^{\mathrm{H}}\hat{\mathbf{H}})\mathbf{n}= \rho(\mathbf{z}^{l}-\mathbf{s}^{l})+2\hat{\mathbf{H}}^{\mathrm{H}}\mathbf{y}. \tag{20}\]  
By the use of Equation (20), the estimate of \(\mathbf{n}\) in a closed-form expression is  
\[\mathbf{n}=(\rho\mathbf{I}+2\hat{\mathbf{H}}^{\mathrm{H}}\hat{\mathbf{H}})^{- 1}(\rho(\mathbf{z}^{l}-\mathbf{s}^{l})+2\hat{\mathbf{H}}^{\mathrm{H}}\mathbf{ y}). \tag{21}\]  
In the \(\mathbf{z}\)-step of Equation (18), according to subdifferential calculus, the estimate of \(\mathbf{z}\) is obtained by componentwise soft thresholding as  
\[\mathbf{z}^{l+1}=\mathbf{T}_{\lambda/\rho}\big{(}\mathbf{n}^{l+1}+\mathbf{s}^ {l}\big{)}, \tag{22}\]  
where the soft thresholding operator \(\mathbf{T}\) is given by  
\[\mathbf{T}_{\lambda/\rho}(a)=\left\{ \begin{array}{cc}a-\lambda/\rho,&a> \lambda/\rho,\\ 0,&|a|<\lambda/\rho,\\ a+\lambda/\rho,&a<-\lambda/\rho.\end{array} \right. \tag{23}\]  
It is documented that soft thresholding is the proximity operator of the \(\ell_{1}\) norm--see [31]. To estimate \(\boldsymbol{\alpha}\), without ambiguity, the subscript of \(\mathcal{W}\) is dropped, and the optimization problem now is  
\[\mathrm{minimize}\ \|\mathbf{y}-\hat{\mathbf{H}}\mathcal{W}\boldsymbol{ \alpha}-\hat{\mathbf{n}}\|_{2}^{2}+\lambda\|\boldsymbol{\alpha}\|_{1}. \tag{24}\]  
Similarly, the ADMM steps of \(\boldsymbol{\alpha}\) at \(l\)th iteration are  
\[ \begin{split}\boldsymbol{\alpha}^{l+1}&=\mathrm{ minimize}_{\boldsymbol{\alpha}}\big{(}\|\mathbf{y}-\hat{\mathbf{H}}\mathcal{W} \boldsymbol{\alpha}-\hat{\mathbf{n}}\|_{2}^{2}+(\rho/2)\|\boldsymbol{\alpha}- \mathbf{g}^{l}+\mathbf{u}^{l}\|_{2}^{2}\big{)}\\ \mathbf{g}^{l+1}&=\mathrm{minimize}_{\mathbf{g}} \big{(}\lambda\|\mathbf{g}\|_{1}+(\rho/2)\|\boldsymbol{\alpha}^{l+1}-\mathbf{ g}+\mathbf{u}^{l}\|_{2}^{2}\big{)}\\ \mathbf{u}^{l+1}&=\mathbf{u}^{l}+\boldsymbol{\alpha}^{l+1}- \mathbf{g}^{l+1}.\end{split}