# Variational Multiscale Nonparametric Regression: Algorithms and Implementation
## 1 Introduction  
Regression analysis has a centuries long history in science and is one of the most powerful and widely used tools in modern statistics. As it aims to discover a functional dependency \(f\) between certain variables of interest, it provides important insight into the relationship of such variables. Typically, the data are noisy and specific regression models provide a mathematical framework for the recovery of this unknown relationship \(f\) given such noisy observations. Due to the flexibility of such models, they can be accommodated to many different scenarios, e.g., for linearly dependentdata as in linear regression and for data following a general nonlinear structure as in nonlinear regression. The literature on this and the range of applications is vast, we exemplarily refer to the work of [PERSON] and [PERSON] [1] for an overview. Often, these models depend on a few parameters only specifying \(f\) already, which then can be estimated from the data in a relatively simple way. In contrast, nonparametric regression avoids such a restrictive modelling and becomes indispensable when prior knowledge is not sufficient for parametric modelling (see, e.g., [2; 3]). One of the most fundamental and most studied nonparametric models is the Gaussian nonparametric regression (i.e., denoising) model with independent errors, sometimes denoted as white noise regression model (after a Fourier transformation). In this model, we aim to estimate the unknown regression function \(f:\,[0,1]^{d}\to\mathbb{R}\) given noisy observations \(Y_{i}\), which are related to \(f\) as  
\[Y_{i}=f(x_{i})+\sigma\,\epsilon_{i},\ \ x_{i}\in\Gamma_{n},\ \ i=1,\ldots,n, \tag{1}\]  
where \(\epsilon_{i}\) are independent normal random variables with zero mean and unit variance and \(\Gamma_{n}\) is a discrete grid in \([0,1]^{d}\) that consists of \(n\) points. Note that \(\sigma\) determines the noise level, which we assume for simplicity to be constant (see, however, Section 5). We stress that much of what is addressed in this paper can be generalised to other error models and other domains than the \(d\)-dimensional unit cube \([0,1]^{d}\) (see also Section 5). However, to keep the presentation simple, we restrict ourselves to the Gaussian error and equidistant grids in the \(d\)-dimensional unit cube. A mathematical theory of such nonparametric regression problems has a long history in statistics (see [4] for an early reference), as they are among the simplest models where the unknown object is still in a complex function space and not just encoded in a low-dimensional parameter, yet they are general enough to cover many applications (see, e.g., [3]). Consequently, the statistical estimation theory of nonparametric regression is a well investigated area for which plenty of methods have been proposed, such as kernel smoothing [5; 6]; global regularisation techniques such as penalised maximum likelihood [7]; ridge regression, which amounts to Tikhonov regularisation [8; 9]; or total variation (TV) regularisation [10]. These methods have not been designed a-priori in a spatially adaptive way which could be overcome by a second generation of (sparse) localising regularisation methods originating in the development of wavelets [11]. To fine tune the estimator for first generation methods, usually a simple regularisation parameter has to be chosen (statistically); for wavelet-based estimators, this amounts to properly select (and truncate) the wavelet coefficients methods, e.g., by soft thresholding (see, e.g., [12]). We refer to [PERSON] [13] for an introduction to the modern statistical theory of nonparametric regression, mainly from a minimax perspective. One of the latest developments to the problem of recovering the function \(f\) in (1) already dates back to [PERSON] [14] and is implicitly exemplified by the Dantzig selector [15], which can be seen as a hybrid between a sparse approximation with respect to a dictionary and variational (\(L^{1}\)) regularisation. Such hybrid methods were coined by [PERSON] et al.