# Variational Multiscale Nonparametric Regression: Algorithms and Implementation
## 3 Computational Methods
### The Chambolle-Pock Method  
The primal dual algorithm by [PERSON] and [PERSON] [41] is based on a reformulation of the optimality conditions (9) as fixed point equations. If we multiply the second condition by a parameter \(\tau>0\) and add \(w\) on both sides yields  
\[w+\tau Kv\in w+\tau\partial F^{\star}(w).\]  
Similarly, the first condition yields  
\[v-\delta K^{*}w\in v+\delta\partial G(v).\]  
Hence, the solutions \(v\) and \(w\) of the optimality conditions can be found by repetitively applying the resolvent operators of \(G\) and the dual of \(F\), which are given by  
\[\left(I+\tau\partial G\right)^{-1}(v) :=\operatorname*{argmin}_{x\in\mathbb{R}^{n}}\frac{\|x-v\|^{2}} {2\tau}+R(v) \tag{10a}\] \[\left(I+\delta\partial F^{*}\right)^{-1}(w) :=\operatorname*{argmin}_{z\in\mathbb{R}^{n_{R}}}\frac{\|z-w\|^{ 2}}{2\delta}+q_{n}\sum_{\lambda\in\Lambda_{n}}\big{|}z_{\lambda}-\delta Y_{ \lambda}\big{|}. \tag{10b}\]  
This combined with an extrapolation step yields the Chambolle-Pock algorithm. It can also be interpreted as a splitting of the subdifferential \(\partial J\) into those of \(F\) and \(G\), and then applying proximal point steps (i.e., backwards steps) to \(\partial G\) and the dual of \(\partial F\).  
The first proximal operator in (10) depends on the regularising functional \(R(\cdot)\), which is typically convex, so the computation can be done efficiently. For instance, it can be solved by quadratic programming [56] if \(R(\cdot)\) is a Sobolev norm and with [PERSON]'s algorithm [57] if \(R(\cdot)\) is the TV penalty.  
The second proximal operator in (10) involves the high-dimensional constraint. However, the solution to (10b) is simply the soft-thresholding operator applied to \(\delta^{-1}w-KY\) with threshold \(q_{n}\,\delta\). Altogether, the Chambolle-Pock algorithm applied to (3) is given in Algorithm 1.  
```
0:\(\delta,\tau>0,\theta\in[0,1]\), \(k=0\), \((v_{0},w_{0})\in X\times Y\), stopping criterion
1:while stopping criterion not satisfied do
2:\(w_{k+1}\leftarrow\big{(}I+\delta\,\partial F^{\star}\big{)}^{-1}(w_{k}+\delta \,K\,\widetilde{v}_{k})\)
3:\(v_{k+1}\leftarrow\big{(}I+\tau\,\partial G\big{)}^{-1}(v_{k}-\tau\,K^{\star}\,w _{k+1})\)
4:\(\widetilde{v}_{k+1}\gets v_{N}+\theta\big{(}v_{k+1}-v_{k}\big{)}\)
5:\(k\gets k+1\)
6:endwhile
7:Return \((v_{k},w_{k})\)
```  
**Algorithm 1**Chambolle-Pock algorithm  
To run the Chambolle-Pock algorithm, we need to choose the step sizes \(\delta\) and \(\tau\), and convergence of the algorithm is ensured whenever \(\tau\delta\leq\|K\|_{op}^{-1}\). Due to the different difficulty of the two subproblems, it is reasonable to choose \(\delta\
eq\tau\) and, in particular, to choose \(\delta>\tau\). More precisely, the subproblem with respect to \(F\) is more involved because of the large number of constraints, so this requires a much smaller step size, which by the Moreau's identity is equivalent to choosing a much larger \(\delta\). We observe in practice that the choices \(\delta=\|K\|_{op}^{-1}\sqrt{n}\) and \(\tau=\|K\|_{op}^{-1}/\sqrt{n}\) yield good results (see Section 4).  
We remark that, in the Chambolle-Pock method applied to this problem, the high-dimensionality appears only in the very simple problem of soft-thresholding. This is a very convenient way of dealing with it and, as shown below, makes the Chambolle-Pock-algorithm superior over the ADMM method.