# Salt and Pepper Noise Removal with Multi-Class Dictionary Learning and L0 Norm Regularizations
## 2 Methods
### Proposed Method
#### 2.2.3 Numerical Algorithm  
Directly solving Equation (10) is very hard since its L\({}_{0}\) norm terms are non-smooth and non-differential. In this work, we adopt the alternating direction minimization with continuation algorithm (ADMC) [10; 16; 37] to solve Equation (10). ADMC is chosen since it enables to obtain the solution with much easier sub-problems that have analytical solutions as discussed below. Figure 3: Comparisons on the denoised Barbara images using different norms. (**a**) is the noise-free image, (**b**) is the noisy image, (**c**) and (**d**) are denoised images using FDLCP with L\({}_{1}\) and L\({}_{0}\) norm minimizations, respectively. Note: The noise level is 0.5, meaning that 50% pixels are contaminated by salt and pepper noise. By introducing the continuation parameter \(\beta\) and augmented variables \(\mathbf{\alpha}\) and \(\mathbf{d}\), a relax form of Equation (10) is:  
\[\min_{\mathbf{\alpha},\mathbf{d},\mathbf{x}}\biggl{(}\|\mathbf{\alpha}\|_{0}+\frac{\beta}{2}\| \mathbf{\alpha}-\mathbf{\Phi}^{T}\mathbf{x}\|_{2}^{2}\biggr{)}+\lambda\biggl{(}\|\mathbf{d}\|_{ 0}+\frac{\beta}{2}\mathbf{d}-\mathbf{W}\|(\mathbf{y}-\mathbf{x})\|_{2}^{2}\biggr{)} \tag{14}\]  
where \(\mathbf{\alpha}\) and \(\mathbf{d}\) are two augmented variables. When \(\beta\to\infty\), the solution of Equation (14) approaches that of Equation (10) since any non-zero values of \(\|\mathbf{\alpha}-\mathbf{\Phi}^{T}\mathbf{x}\|\) (or \(\|\mathbf{d}-\mathbf{W}(\mathbf{y}-\mathbf{x})\|\)) will lead \(\frac{\beta}{2}\|\mathbf{\alpha}-\mathbf{\Phi}^{T}\mathbf{x}\|_{2}^{2}\) (or \(\frac{\beta}{2}\|\mathbf{d}-\mathbf{W}(\mathbf{y}-\mathbf{x})\|_{2}^{2}\)) to be infinite. Therefore, in order to minimize the cost function of Equation (14), both \(\mathbf{\alpha}=\mathbf{\Phi}^{T}\mathbf{x}\) and \(\mathbf{d}=\mathbf{W}(\mathbf{y}-\mathbf{x})\) must be simultaneously satisfied, meaning that Equation (14) is equivalent to Equation (10) when \(\beta\to\infty\). In the implementation, we gradually increase \(\beta\). While \(\beta\) is fixed at the kth iterations, the solution of Equation (14) is obtained by alternatively solving the following sub-problems where each one has the analytical solution. (1) Fixed \(\mathbf{d}^{(k)}\) and \(\mathbf{x}^{(k)}\), solve:  
\[\mathbf{\alpha}^{(k+1)}=\operatorname*{argmin}_{\mathbf{\alpha}}\|\mathbf{\alpha}\|_{0}+ \frac{\beta}{2}\|\mathbf{\alpha}-\mathbf{\Phi}^{T}\mathbf{x}^{(k)}\|_{2}^{2}, \tag{15}\]  
whose solution is achieved by hard thresholding according to:  
\[\mathbf{\alpha}^{(k+1)}=H_{\sqrt{\frac{2}{\beta}}}\Bigl{(}\mathbf{\Phi}^{T}\mathbf{x} \Bigr{)}. \tag{16}\]  
(2) Fix \(\mathbf{x}^{(k)}\) and \(\mathbf{\alpha}^{(k+1)}\), solve:  
\[\mathbf{d}^{(k+1)}=\operatorname*{argmin}_{\mathbf{d}}\|\mathbf{d}\|_{0}+\frac{\beta}{2}\| \mathbf{d}-\mathbf{W}(\mathbf{y}-\mathbf{x}^{(k)})\|_{2}^{2}, \tag{17}\]  
whose solution is also achieved by hard thresholding as follows  
\[\mathbf{d}^{(k+1)}=H_{\sqrt{\frac{2}{\beta}}}\Bigl{(}\mathbf{W}\Bigl{(}\mathbf{y}-\mathbf{x} ^{(k)}\Bigr{)}\Bigr{)} \tag{18}\]  
(3) Fix \(\mathbf{\alpha}^{(k+1)}\) and \(\mathbf{d}^{(k+1)}\), solve:  
\[\mathbf{x}^{(k+1)}=\operatorname*{argmin}_{\mathbf{x}}\|\mathbf{\alpha}^{(k+1)}-\mathbf{\Phi}^ {T}\mathbf{x}\|_{2}^{2}+\lambda\|\mathbf{d}^{(k+1)}-\mathbf{W}(\mathbf{y}-\mathbf{x})\|_{2}^{2}, \tag{19}\]  
and have the solution as follows:  
\[\mathbf{x}^{(k+1)}=\Bigl{(}\mathbf{I}+\lambda\mathbf{W}^{T}\mathbf{W}\Bigr{)}^{-1}\Bigl{(}\bm {\Phi}\mathbf{\alpha}^{(k+1)}+\lambda\mathbf{W}^{T}\Bigl{(}\mathbf{W}\mathbf{y}-\mathbf{d}^{(k+1) }\Bigr{)}\Bigr{)}. \tag{20}\]  
The algorithm is summarized in Algorithm 1. It is worth noting that the existing ADMC algorithms solve either a reconstruction model with minimization of L\({}_{1}\) norm (sparsity regularization) and L\({}_{2}\) norm (data fidelity) in compressive image recovery [16; 38; 39], or a denoising model with minimization of L\({}_{1}\) norm (sparsity regularization) and L\({}_{1}\) norm (data fidelity) for impulse noise removal [10; 11].