# Image Recovery with Data Missing in the Presence of Salt-and-Pepper Noise
## 4 Problem Formulation and Algorithm Development  
With the sparse representation in the transform domain, the degraded image in Equation (3) is reexpressed more explicitly as  
\[\tilde{\mathbf{y}}=\mathbf{\mathrm{H}}(\mathcal{W}_{WT,FT}^{\mathrm{T}}\mathbf{\alpha}_{ WT,FT})+\tilde{\mathbf{n}}, \tag{13}\]  
where \(\mathcal{W}_{WT,FT}\) respectively indicates the wavelet and framelet transform operator and \(\mathbf{\alpha}_{WT,FT}\) is the transform coefficient vector in the corresponding domain. To utilize the sparse property of the \(\mathbf{\alpha}_{WT,FT}\)  
Figure 1: Comparation of framelet and wavelet decomposition. (**a**) the lena image; (**b**) the sorted framelet coefficients at level 1; (**c**) the sorted wavelet coefficients at level 1.  
\(\mathbf{H}\), and \(\mathbf{n}\), the following optimization problem is developed to jointly conduct image reconstruction and missing pattern estimation in the case of the salt-and-pepper noise. That is,  
\[\begin{split}\text{minimize}&\|\boldsymbol{\alpha}_{WT, FT}\|_{1}+\lambda_{1}\|\mathbf{H}\|_{1}+\lambda_{2}\|\mathbf{\hat{n}}\|_{1}\\ \text{subject to}&\|\hat{\mathbf{y}}-\mathbf{H}( \mathcal{W}_{WT,FT}^{\text{T}}\boldsymbol{\alpha}_{WT,FT})-\mathbf{\hat{n}}\|_ {2}^{2}<\epsilon,\end{split} \tag{14}\]  
with variables \(\boldsymbol{\alpha}_{WT,FT}\), \(\mathbf{H}\) and \(\mathbf{\hat{n}}\). To efficiently solve the optimization problem in Equation (14), a two-step process is utilized. Let us first suppose that \(\mathbf{H}\) is known; the sub-problem is a convex optimization problem with variables \(\boldsymbol{\alpha}_{WT,FT}\) and \(\mathbf{\hat{n}}\). Second, with the estimated values of \(\boldsymbol{\alpha}_{WT,FT}\) and \(\mathbf{\hat{n}}\), the sub-problem is another convex optimization with variable \(\mathbf{H}\). In Equation (14), the parameter of \(\epsilon\) is usually chosen empirically, but some approaches such as factor model can be utilized to obtain the optimal value [30]. To summarize, the two-step procedure is as follows:  
_Initialize missing pattern vector._  
\(\bullet\) **Step 1**_: Solve Equation (14) with the initialized/estimated missing pattern to obtain estimations of \(\boldsymbol{\alpha}_{WT,FT}\) and \(\mathbf{\hat{n}}\) as_  
\[\begin{split}\text{minimize}&\|\boldsymbol{\alpha}_{WT, FT}\|_{1}+\lambda_{2}\|\mathbf{\hat{n}}\|_{1}\\ \text{subject to}&\|\hat{\mathbf{y}}-\mathbf{\hat{ H}}(\mathcal{W}_{WT,FT}^{\text{T}}\boldsymbol{\alpha}_{WT,FT})-\mathbf{\hat{n}}\|_{2}< \epsilon,\end{split} \tag{15}\]  
_where \(\mathbf{\hat{H}}\) is the initialized/estimated value of the missing pattern._  
\(\bullet\) **Step 2**_: With the estimations from Step 1, solving Equation (14) yields missing pattern estimation as_  
\[\begin{split}\text{minimize}&\|\mathbf{H}\|_{1}\\ \text{subject to}&\|\hat{\mathbf{y}}-\mathbf{H}( \mathcal{W}_{WT,FT}^{\text{T}}\mathbf{\hat{n}}_{WT,FT})-\mathbf{\hat{n}}\|_{2} <\epsilon,\end{split} \tag{16}\]  
_where \(\mathbf{\hat{n}}_{WT,FT}\) and \(\mathbf{\hat{n}}\) denote the estimated values of \(\boldsymbol{\alpha}_{WT,FT}\) and \(\mathbf{\hat{n}}\), respectively._  
\(\bullet\) _Iterate Steps 1 and 2 until a stopping rule is met._  
It is seen that at each step, it solves an \(\ell_{1}\)-norm constrained optimization problem, and considering the large size of the image, the following two algorithms of ADMM and APG are tailored to solve the optimization problems.