## 4 Dictionary Pair Learning Algorithm
### Sparse coding phase
threshold can be removed with the substitution that \(\mathbf{y}_{i}-\mathcal{S}_{\lambda}(\mathbf{\Psi}^{T}\mathbf{R}_{i}\mathcal{I}^{k}) \approx\mathbf{y}_{i}+\mathbf{c}^{k}\odot\mathbf{u}-\mathbf{\Psi}^{T}\mathbf{R} _{i}\mathcal{I}^{k}\) Thus, in the \(k\)-th step, the problem needs to be solved is expressed as

\[\{\hat{\mathcal{I}}^{k}\}=\min_{\mathcal{I}^{k-1}}\|\mathcal{L}-SH\mathcal{I}^ {k-1}\|_{\mathrm{F}}^{2}+\gamma\sum_{i}\|\mathbf{R}_{i}\mathcal{I}^{k-1}- \mathbf{\Phi}\mathbf{y}_{i}\|_{\mathrm{F}}^{2}+\gamma_{1}\sum_{i}\|\mathbf{y} _{i}+\mathbf{c}^{k}\odot\mathbf{u}^{k}-\mathbf{\Psi}^{T}\mathbf{R}_{i}\mathcal{ I}^{k-1}\|_{\mathrm{F}}^{2} \tag{42}\]

where \(\odot\) is point multiplication. This convex problem can be easily solved by gradient descent algorithm. We summarized the restoration algorithm in Algorithm 3. ```
0: Training dictionaries \(\mathbf{\Phi}\), \(\mathbf{\Psi}\), iteration number \(r\), a degraded image \(\mathcal{L}\), set \(\mathcal{I}_{0}=\mathcal{L}\). 0: The high quality image \(\hat{\mathcal{I}}\)
1: Compute \(\mathbf{Y}\) and \(\lambda\) via the method in Algorithm 1. 0: For k=1:r
2: compute \(\mathbf{d}^{k}=\mathbf{\Psi}^{T}\mathbf{R}_{i}\mathcal{I}^{k-1}\). Set \(\mathbf{c}^{k}=sign(\mathbf{d}^{k})\). set \(\mathbf{O}^{k}\) as an index set that satisfies \(|\mathbf{d}^{k}_{l}|\leq\lambda_{l},l\in\mathbf{O}^{k}\). Set \(\mathbf{u}^{k}_{l}= \begin{cases}\lambda_{l}&l\in\mathbf{O}^{k},\\ 0&\text{otherwise.}\end{cases} \). 3: Solving the Problem (42) via gradient descent algorithm. Endfor
```

**Algorithm 3** Restoration algorithm

## 6 Complexity Analysis

In this section, we discuss the computational complexity of our sparse coding and dictionary pair learning algorithms with regard to those of conventional sparse model counterparts. We first analyze complexities of the main components of the sparse coding (SC) and dictionary updating (DU) algorithms. In terms of SC, given a set of training samples, \(\mathbf{X}\in\mathcal{R}^{N\times L}\), the complexity of BtOMP of calculating \(\hat{\mathbf{Y}}=\min_{\mathbf{Y}}\|\mathbf{X}-\mathbf{\Phi}\mathbf{Y}\|_{F }^{2}+\gamma_{1}\|\mathbf{Y}-\mathcal{S}_{\lambda}(\mathbf{\Psi}^{T}\mathbf{X} )\|_{F}^{2}+\gamma_{2}\|\mathbf{Y}\|_{0}\) is \(O(K^{2}ML)\) where \(K\) is the target sparsity and the complexity of threshold of calculating \(\hat{\boldsymbol{\lambda}}=\min_{\lambda}\|\mathbf{Y}-\mathcal{S}_{\lambda}( \mathbf{\Psi}^{T}\mathbf{X})\|_{F}^{2}\) is \(O(NML)\), which cost most of time in SC step at each iteration. The sparse coefficients \(\mathbf{Y}\in N\times L\) and the the threshold values \(\lambda\) are computed with fixed dictionaries \(\mathbf{\Phi}\in\mathcal{R}^{N\times M}\) and \(\mathbf{\Psi}\in\mathcal{R}^{N\times M}\). Correspondingly, the traditional sparse coefficients \(\mathbf{B}\in N\times L\) is sparse approximated by dictionary \(\mathbf{D}\in\mathcal{R}^{N\times M}\) and the computational complexity is \(O(K^{2}ML)\). In terms of DU, with the given training samples \(\mathbf{X}\in\mathcal{R}^{N\times L}\), we learn a pair of dictionary \(\mathbf{\Phi}\in\mathcal{R}^{N\times M}\) and \(\mathbf{\Psi}\in\mathcal{R}^{N\times M}\). We update \(\mathbf{\Psi}\) via Problem (34) with a computational complexity of \(O(N^{2}L)\). In order to update \(\mathbf{\Phi}\). we need to calculate the gradient via Equation (39) with a computational complexity of \(O(NML)\) and the step size via Equation (40) with a computational complexity of \(O(rNML)\) where \(r\) is the iteration number of the gradient descent. For the traditional dictionary learning, the corresponding training set is \(\mathbf{X}\in\mathcal{R}^{N\times L}\) and the dictionary \(\mathbf{D}\in\mathcal{R}^{N\times M}\) is updated by SVD decomposition of rank-1 with a computational complexity of \(O(KML)\).