# Variational Multiscale Nonparametric Regression: Algorithms and Implementation
## 1 Introduction
### Variational Multiscale Methods  
Variational multiscale methods offer a solution to the problem of such Gibbs-artefacts, as they combine multiscale methods with classical (non-sparse) regularisation techniques, with the idea of making use of the best of both worlds: the stringent data-fitting properties of (overcomplete) multiscale dictionaries, and the desired (problem dependent) smoothness imposed by a regularisation method, e.g., by TV regularisation.  
**Definition 1**.: _Let \(\mathcal{F}\) be a class of functions, \(R:\mathcal{F}\to\mathbb{R}\cup\{\infty\}\) a convex functional and \(\{\phi_{\lambda}|\lambda\in\Lambda_{n}\}\) a finite collection of functions. Given observations \(Y_{i}\) as in (1), the Multiscale Nemirovski-Dantzig Estimator (MIND) is defined by the constrained optimisation problem_  
\[\hat{f}\in\operatorname*{argmin}_{g\in\mathcal{F}}R(g)\ \ \ \text{such that}\ \max_{\lambda\in\Lambda_{n}}|\langle\phi_{\lambda},g-Y\rangle|\leq q_{n} \tag{3}\]  
_for a threshold \(q_{n}>0\), where we use the inner product \(\langle h,g\rangle:=n^{-1}\sum_{i=1}^{n}h(x_{i})g(x_{i})\)._Several particular cases of the MIND have been proposed: the first time by [PERSON] [14] (who gave credit to [PERSON]) in 1985 for a system of indicator functions and a Sobolev seminorm, \(R(g)=|g|_{H^{s}}\), [PERSON] [12] derived soft-thresholding from this principle where the dictionary \(\{\phi_{\lambda}\,|\,\lambda\in\Lambda_{n}\}\) is a wavelet basis (for the latter, see also [30]). For the case of a curvelet frame, we refer to [28] and for a system of indicator functions and the Poisson likelihood to [31; 32], where \(R(g)=|g|_{BV}\) is the TV seminorm. Notice that, in practice, the choices of \(R\) and the dictionary reflect previous knowledge or expectations on the unknown function \(f\): the amount of regularisation that \(R\) imposes should be dependent on how smooth we expect \(f\) to be; and the dictionary should measure patterns that we expect \(f\) to obey, e.g., elongated features in the case of curvelets and piecewise constant areas in the case of indicator functions. Furthermore, we have the following rule of thumb: the more redundant is the dictionary, the better is the statistical properties of the estimator but the more expensive is the computation of a solution to (3).  
It is documented that the different proposed instances of the MIND show increased regularity and reduced artefacts as compared with standard multiscale methods (i.e., thresholding type estimators), but still avoid oversmoothing if the threshold \(q_{n}\) is appropriately chosen (see [29; 31; 32]). For instance, we illustrate in Figure 1 that the MIND with \(R\) the TV seminorm outperforms the soft-thresholding estimator under various choices of multiscale dictionaries, including wavelets, curvelets and shearlets. In addition to their good empirical performance, estimators of the form (3) have recently been analysed theoretically and proved to be (nearly minimax) optimal for nonparametric regression [16; 29] and certain inverse problems [15; 33]. We give a brief review of these theoretical results in Section 2.  
Figure 1: _Cont._