# Variational Multiscale Nonparametric Regression: Algorithms and Implementation
## 4 Numerical Study
### Comparison of Three Algorithms  
Here, we compare the convergence speed of the Chambolle-Pock, ADMM and semismooth Newton algorithms in solving (3) or equivalently (6). We stress that the relative performance of the three algorithms remains similar over different settings. Thus, as a particular example, we choose the \"cameraman\" image (\(256\times 256\) pixels) as the function \(f\) in model (1) and the indicator functions of dyadic (partition) system of cubes (cf. Definition 2.2 in [16]), which consists of cubes  
\[\left[i2^{-\ell},\,(i+1)2^{-\ell}\right]\times\left[j2^{-\ell},\,(j+1)2^{-\ell }\right]\quad\subseteq\quad[0,1]^{2}\qquad\text{for all possible }i,j,\ell\in\mathbb{N} \tag{18}\]  
as the dictionary \(\{\phi_{\lambda}|\lambda\in\Lambda_{n}\}\). The noise level \(\sigma\) is assumed to be known and is chosen such that the signal-to-noise ratio (SNR) \(\max_{i=1,\ldots,n}|f(x_{i})|/\sigma=30\), see Figure 2. Besides the aforementioned image quality measures, we employ objective values \(R(g_{k})\), (relative) constraint gaps \(\left(\max_{\lambda\in\Lambda_{n}}|\langle\phi_{\lambda},g_{k}-\gamma\rangle |-q_{n}\right)/q_{n}\), and the distance \(\|g_{k}-g_{\infty}\|\) to the limit solution \(g_{\infty}\) to examine the evolution of iterations \(g_{k}\). The limit solution \(g_{\infty}\) is obtained for each algorithm after a large number of iterations, that is \(3\times 10^{4}\) outer iterations for the Chambolle-Pock, \(3\times 10^{3}\) outer iterations for the ADMM, and the largest possible number of iterations until which the path-continuation scheme remains stable for the semismooth Newton method (in the considered setup, 29 outer iterations in case of \(H^{1}\) regularisation). As mentioned in Section 3.3, the semismooth Newton method is unstable for the case of TV regularisation, which is thus not reported here. All limit solutions \(g_{\infty}\) are shown in Figures 3 and 4 and are visually quite the same in each figure (while MIND with TV regularisation leads to a slightly better result than that with \(H^{1}\) regularisation). This indicates that all three algorithms are able to find the global solution of (3) to a desirable accuracy. Figure 3: Limit solutions of all three algorithms for MIND with \(H^{1}\) (PSNR = 30 for all) regularisation after long iterations. (**a**) Chambolle–Pock; (**b**) ADMM; (**c**) Semismooth Newton. Figure 2: Image “cameraman” and its noisy version with SNR = 30. (**a**) Truth; (**b**) Noisy. To reduce the burden of practitioners on parameter tuning, we set the parameters in the Chambolle-Pock (Algorithm 1) by default as \(\theta=1\), \(\delta=\|K\|_{op}^{-1}\sqrt{n}\) and \(\tau=\|K\|_{op}^{-1}/\sqrt{n}\) in all settings. We note that the performance of the Chambolle-Pock, which is reported below, can be further improved by fine tuning \(\theta\) and \(\delta\) and possibly also by preconditioning [69], for every choice of regularisation functional and dictionary. In contrast, the parameters of the ADMM and the semismooth Newton algorithms are fine tuned towards the best performance for each case. More precisely, for ADMM, we choose \(\lambda=50\) in the case of \(H^{1}\) and \(\lambda=0.5\) in the case of TV, and, for the semismooth Newton, we choose \(\delta=1/3\) and \(\Delta\delta=1/3\) in the case of \(H^{1}\). The performance of three algorithms over time is shown in Figures 5 and 6 for \(H^{1}\) and TV regularisation, respectively. In both cases, the Chambolle-Pock clearly outperformed the ADMM with respect to all considered criteria. The semismooth Newton algorithm, as is ensured by the theory, exhibited a faster convergence rate than the other two, but this happened only at a very late stage. Moreover, the path-continuation scheme is sensitive to the choice of parameters and makes it difficult to decide the right stopping stage in general. In summary, from a practical perspective, the overall performance of the Chambolle-Pock algorithm was found to be superior compared to the other algorithms.