text:
\section{Introduction}\label{intro}

In this paper, we are concerned with the solution of the equation
\begin{equation}\label{intro:lineqn}
  Ku = g,
\end{equation}
where $K:U\rightarrow V$ is a linear and bounded operator mapping between two
Hilbert-spaces $U$ and $V$. Equations of type \eqref{intro:lineqn} are  called
\emph{well-posed} if for given $g\in V$ there exists a unique solution
$u^\dagger\in U$ that depends continuously on the right-hand side $g$.  If one
of these conditions is not satisfied, the problem is called \emph{ill-posed}. In  the
case of ill-posedness, arbitrary small deviations in the right hand side $g$
may lead to useless solutions $u$ (if solutions exist). These
deviations are commonly modelled as random: They are due to
indispensable numerical errors as well as to the random nature of the
measurement  process itself. \emph{(Statistical) regularisation methods} aim
at computing stable approximations of true solutions $u$
from a (statistically)  perturbed signal $g$.

In this paper we assume that  we are given the observation
\begin{equation}\label{intro:noisemodel}
  Y = Ku^\dagger + \sigma \varepsilon.
\end{equation}
Here, $\sigma>0$ denotes the noise-level and $\varepsilon:V\rightarrow \Ls{2}(X,
\mathfrak{A}, \mathbb{P})$ a Gaussian white noise process, i.e. $\varepsilon$ is linear and
continuous and for all $v,w \in V$ one has
\begin{equation*}
  \varepsilon(v) \sim \mathcal{N}(0,\norm{v}^2)\quad\text{ and }\quad
  \Cov{\varepsilon(v)}{\varepsilon(w)} = \inner{v}{w},
\end{equation*}
where $\mathcal{N}(\mu, \sigma^2)$ denotes the normal distribuion with
expectation $\mu$ and variance $\sigma^2$. The white noise model
\eqref{intro:noisemodel} is very common in the theory of statistical inverse
problems \citep[see e.g.][]{frick:JohSil91, frick:NusPer99, frick:ChoIbrKha99,
frick:CavTsy02, frick:BisHohMunRuy07, frick:CohHofRei04, frick:Cav08} and it can
be regarded as reasonable approximation to models relevant for many areas of
applications.  A statistical regularisation method amounts to compute an
estimator $\hat u = \hat u (\sigma)$ given the data $Y$
 in \eqref{intro:noisemodel} such that $\hat u(\sigma)\rightarrow u^\dagger$ (in an
 appropriate sense) as $\sigma \rightarrow 0^+$ .

The simplest case covered by Model \eqref{intro:noisemodel} is classical
nonparametric regression and its amplitude of applications. Here, $U$ and $V$
are suitable function spaces where it is assumed that $U$ can be continuously
embedded into $V$. $U$ models the smoothness of the true signal $u^\dagger$ and
$K$ is the embedding operator $K:U\hookrightarrow V$ (cf.
\cite{frick:BisHohMunRuy07}). More sophisticated examples for $K$ arise in
imaging, when blurring induced by the recording optical systems is modelled as a
convolution with a kernel $k(x-y)$ (in engineering and physical terminology
denoted as a point spread function). Beyond convolution, different operators $K$
occur in various other applications, e.g. in seismic engineering
(\cite{frick:ChiAlbGla04}), in material sciences (\cite{frick:PopTaf04}),
magnetic resonance imaging (\cite{frick:BloUecFra07}), image  processing
(\cite{frick:BerBoc98}), tomography (\cite{frick:SchGraGroHalLen09,frick:EHN96})
and astrophysics (\cite{frick:BisHol08}).

Due to the broad area of applications, the literature on statistical
regularisation methods is vast. We only give a few, selective references:
Penalised least-squares estimation  (that includes Tikohonov-Philipps and
maximum entropy regularisation) \citep{frick:BisHohMun04, frick:Sul86,
frick:Wah77}, wavelet based methods \citep{frick:Don93, frick:Don95,
frick:Joh99, frick:KerKyrPenPet10, frick:JohKerPicRai04}, estimation in
Hilbert-scales \citep{frick:BisHohMunRuy07, frick:GolPer03, frick:MaiRuy96,
frick:MatPer01, frick:MatPer03, frick:MatPer03a} and regularisation by
projection \citep{frick:CavGolPicTsy02, frick:CavTsy02, frick:CohHofRei04,
frick:MatPer01, frick:HofRei08} to name but a few.

In this work, we follow a different route and study a variational estimation
scheme that defines estimators $\hat u$ as solutions of
\begin{equation}\label{intro:opt}
  \inf_{u\in U} J(u)\quad \text{ subject to }\quad  T_N(\sigma^{-1}(Y - Ku))
  \leq q_N(\alpha).
\end{equation}
Here, $J$ is a \emph{convex regularisation functional} that is supposed to
measures the regularity of candidate estimators $u\in U$ and $T_N$ is a
\emph{data fidelity term} on $V$ that measures the deviation of the data $Y$
and the estimated image $Ku$. In this work we consider fidelity measures $T_N$
of the form
\begin{equation}\label{intro:mrstatrough}
T_N(v) = \max_{1\leq n\leq N} \mu_n(v),\quad \text{ for }v \in V.
\end{equation}
The functions $\mu_n:V\rightarrow \mathbb{R}$ are designed to be sensitive to
non-random structures in $v$. We will refer to
\eqref{intro:mrstatrough} as \emph{multiresolution statistic (MR-statistic)}
and to corresponding solutions of the optimisation problem \eqref{intro:opt} as
\emph{statistical multiresolution estimators (SMRE)}.

The parameter $q_N(\alpha)$ in \eqref{intro:opt} is chosen to be the
$(1-\alpha)$-quantile of the statistic $T_N(\varepsilon)$ and governs the trade-off
between data-fit and regularity. Hence the
\emph{admissible region}
\begin{equation}\label{intro:admis}
  \mathcal{A}_N(\alpha) = \set{u \in U ~:~ T_N(\sigma^{-1}(Y
  - Ku))\leq q_N(\alpha)}
\end{equation}
constitutes a $(1-\alpha)$-confidence region for a solution $\hat u$ of
\eqref{intro:opt}, i.e. a region which covers the true solution $u^\dagger$ with
probability $1-\alpha$ at least. This gives the estimation procedure
\eqref{intro:opt} a precise statistical interpretation: Since for each solution
$u^\dagger$ of \eqref{intro:lineqn} one has $u^\dagger \in
\mathcal{A}_N(\alpha)$ with probability at least $1-\alpha$ it follows from \eqref{intro:opt} that
\begin{equation*}
  \mathbb{P}\left( J(\hat u) \leq J(u^\dagger) \right) \geq 1-\alpha.
\end{equation*}
Summarizing, regularisation methods of type \eqref{intro:opt} pick among all
estimators $\hat u$ for which the distance between $K\hat u$ and the data $Y$
does not exceed the threshold value $q_N(\alpha)$ one with largest regularity.
The probability that this particular estimator is more regular than any solution of
\eqref{intro:lineqn} is bounded from below by $1-\alpha$ . This is in contrast
to many other regularisation techniques where regularisation parameters merely
govern the trade-off between fit-to-data and smoothness and do not allow such an
interpretation. (In the case of wavelet-thresholding, this property was studied
in \cite{frick:Don95a})

Whereas most of the literature is concerned with the proper choice of the
regularisation functional $J$, in this work we will discuss the issue of the
data fidelity term $T_N$. We claim that from a statistical perspective the
choice of $T_N$ is of equal importance as the choice of $J$.

In Definition \ref{gen:mrstat} below we will delimit a class of feasible
functions for  $\mu_1,\ldots,\mu_N$ in \eqref{intro:mrstatrough}. However, in
order to make ideas clear (and also to justify the notion ``multiresolution''), we
will start with a simple, yet illustrative example: Let $G\subset [0,1]^d$ be
the equi-spaced grid of points in the unit cube and assume that $V$ consists of
all real valued functions $v:G\rightarrow\mathbb{R}$. Moreover, let $\set{S_1,S_2,\ldots,S_N}$
be a sequence of non-empty subsets of $G$. We define for $n\in\mathbb{N}$ and $v\in V$
the \emph{local average function} $\mu_n(v) = \abs{\sum_{\nu\in V} v_\nu}\slash
\sqrt{\# S_n}$. Thus, the MR-statistic $T_N$ reads as
\begin{equation}\label{intro:mrstatspecial}
T_N(\sigma^{-1}(Y-Ku)) =  \max_{1\leq n\leq N}\frac{1}{\sqrt{\# S_n}
}\abs{\sum_{\nu\in S_n} \sigma^{-1}(Y-Ku)_\nu }.
\end{equation}
In other words,  the statistic $T_N$ returns the largest local average of the
residuals $\sigma^{-1}(Y-Ku)$ over the sets $S_1,\ldots,S_N$.  Under the
hypothesis that $u^\dagger$ is the true solution of \eqref{intro:lineqn}, we
have that $T_N(\sigma^{-1}(Y-Ku^\dagger)) = T_N(\varepsilon)$ does not exceed the
threshold $q_N(\alpha)$ with probability $1-\alpha$ at least. Recall that
$\varepsilon$ is a white noise process and hence ``oscillates around zero'' as an effect of which
the quantile values $q_N(\alpha)$ are relatively small due to cancellations in
the sums in \eqref{intro:mrstatspecial}. If, however, $u$ is wrongly specified the
residual $Y - Ku$  contains a non-random signal which may happen to be covered
by a set $S_{n_0}$. As an effect the local average over $S_{n_0}$ - and thus
also the statistic $T_N(\sigma^{-1}(Y-Ku))$ - becomes relatively large and $u$
lies outside the admissible domain of the optimisation problem
\eqref{intro:opt}.

The choice of the system $\set{S_1,\ldots,S_N }$ is subtle, since it should not
miss any non-random information in the residual, if present. Put differently, it
encodes a priori information on where one expects to encounter non-random
behavior in the residuals of \emph{any possible} estimator $\hat u$.  Thus,
$T_N$ would be most sensible against a large variety of signals $\hat u$, if we employ
a large number $N$ of overlapping sets $S_n$ that cover $G$. This approach,
however, turns \eqref{intro:opt} into an optimisation problem with a huge number
of constraints which is hard to tackle numerically (this is treated separately
in \cite{frick:FriMarMun11}). Besides these numerical difficulties, there is
also a statistical limitation which will be a major issue  to be discussed in
this paper: If the dictionary $\set{S_1,\ldots,S_N }$ is too large (in the sense
of a metric entropy), the asymptotic distribution of $T_N$ will degenerate
and would hence be useless for our purposes. In practical situations, a priori
knowledge on the true solution of \eqref{intro:lineqn} can be used in order to
design dictionaries whose  entropy guarantees a non-degenerate limit of $T_N$
and in addition allows to derive rates of convergence of the SMRE to the true
signal. A similar comment applies to the choice of the regularisation functional
$J$  which models a priori information on the regularity of the true solution.

As a consequence the MR-statistic $T_N$ plugged in into \eqref{intro:opt} plays
the role of a \emph{shape constraint} and the resulting estimation method is
capable of adapting the amount of regularization in a \emph{locally adaptive}
manner. Put differently, our approach offers a general methodology to
\emph{localise} any global convex regularisation functional in order to obtain
spatial adaption. This is in contrast to global data fidelity terms such as the
widely used squared $2$-norm fidelity (or any other $p$-norm, $p\geq 1$ for that
matter) that do not allow for adaptation to local structures. This is
illustrated in the following example:

\begin{example}\label{intro:ex}
Assume that $U = V = \mathbb{R}^n$  with
$n=1024$ and let $K:U\rightarrow V$ be the identity
operator, i.e. \eqref{intro:noisemodel} can be rewritten into the simple
nonparametric regression model
\begin{equation*}
Y_i = u_i^\dagger + \sigma \varepsilon_i,\quad i=1,\ldots,n
\end{equation*}
with $\varepsilon_1,\ldots,\varepsilon_n$ i.i.d. standard normal random variables.
The signal $u^\dagger \in U$ and the data $Y$ according to
\eqref{intro:noisemodel} with $\sigma = 0.05$ are depicted in Figure
\ref{intro:figdata}.

\begin{figure}[h!]
\begin{center}
\includegraphics[width = 0.27\textwidth]{signal.png}
\hspace{0.02\textwidth}
\includegraphics[width = 0.27\textwidth]{data.png}
\caption{True signal $u^\dagger$ (left) and data $Y$
(right).}\label{intro:figdata}
\end{center}
\end{figure}

The signal $u^\dagger$ exhibits kinks, jumps, peaks and smooth
portions simultaneously which makes estimation a delicate matter. For
example, the regularisation functional
\begin{equation}\label{intro:h1penalty}
J(u) = \frac{1}{n}\sum_{i=1}^{n-1}\abs{u_{k+1} - u_k}^2.
\end{equation}
appears to be well suited to recover at least the smooth parts of the signal,
however, with a tendency to ``smear out'' edges, peaks and kinks. In the
following we will show how this deficiency can be repaired by \emph{localising}
$J$ by means of MR-statistics. To this end we will compute SMREs, solutions of
\eqref{intro:opt} that is, with $J$ as in \eqref{intro:h1penalty}.

Before we do so, we start with reconstructing $u^\dagger$ by the usual
``global'' approach for the purpose of comparison: We compute a $J$-penalized
least squares estimator $\hat u_2$, i.e. the solution of
\begin{equation}\label{intro:penleastsquare}
\min_{u\in \mathbb{R}^n}\frac{1}{n} \sum_{l=1}^n \abs{Y_l - u_l}^2 +
\frac{\lambda}{n} \sum_{l=1}^{n-1}\abs{u_{l+1} - u_l}^2.
\end{equation}
Here, the proper selection of smoothness amounts to a proper choice of the
parameter $\lambda > 0$. It is instructive to rewrite
\eqref{intro:penleastsquare} in a slightly different form, such that the
relationship to \eqref{intro:opt} becomes obvious: To each $\lambda > 0$ there
corresponds a threshold value $q = q(\lambda)$, such that $\hat u_2$ is a
solution of
\begin{equation}\label{intro:penleastsquarealt}
\min_{u\in\mathbb{R}^n}\frac{1}{n}\sum_{i=1}^{n-1}\abs{u_{k+1} - u_k}^2\quad\text{ s.t.
}\quad \frac{1}{n}\sum_{l=1}^n \abs{Y_l - u_l}^2 \leq q.
\end{equation}
The first
three panels in the upper row of Figure \ref{intro:figsmre} depict solutions
$\hat u_2$ for $q=25,43$ and $50$. The choice $q=43$ yields the visually best
result, however it becomes immediately clear that there are under- and
oversmoothed parts in the reconstruction. The latter becomes undeniably visible
in the qq-plot of the residual $Y - \hat u_2$ (lower row) which indicates that
there is a significant amount of outliers. Note, that less oversmoothing,
i.e. fewer outliers in the residuals, can only be achieved at the cost of more
artefacts in the reconstruction (by decreasing $q$) and vice versa fewer
artefacts only by accepting severe oversmoothing (by increasing $q$). This is due to the fact that
each residual value $Y_l - u_l$ ($1\leq l\leq n$) contributes equally to
the quadratic fidelity in \eqref{intro:penleastsquare} (or likewise in
\eqref{intro:penleastsquarealt}) \emph{independent of its spatial position}.

\begin{figure}[h!]
\begin{center}
\includegraphics[width = 0.242\textwidth]{res_global1.png}
\includegraphics[width = 0.242\textwidth]{res_global.png}
\includegraphics[width = 0.242\textwidth]{res_global2.png}
\includegraphics[width = 0.242\textwidth]{res_smre.png}

\includegraphics[width = 0.242\textwidth]{qq_global1.png}
\includegraphics[width = 0.242\textwidth]{qq_global.png}
\includegraphics[width = 0.242\textwidth]{qq_global2.png}
\includegraphics[width = 0.242\textwidth]{qq_smre.png}
\caption{Upper row: Global estimators $\hat u_\Ls{2}$ for $q=25, 43$ and $50$
and SMRE $\hat u_\text{SMRE}$. Lower row: Corresponding qq-plots of the
standardised residuals against standard normal}.\label{intro:figsmre}
\end{center}
\end{figure}

To overcome this obvious ``lack of locality'' , we compute solutions of
\eqref{intro:opt} where we employ the MR-statistic in
\eqref{intro:mrstatspecial} as fidelity measure. To be more precise, we choose
the sets $\set{S_1,\ldots,S_N}$ to consist of all discrete intervals of the type
$\set{i,\ldots,j}\slash n$ with $1\leq i<j \leq n$ and $j - i \leq 20$ (i.e. $N
= 20.290$). Put differently, the SMRE $\hat u_\text{SMRE}$ is a solution of the
convex optimisation problem
\begin{equation*}
\min_{u\in\mathbb{R}^n}\frac{1}{n}\sum_{i=1}^{n-1}\abs{u_{k+1} - u_k}^2\quad\text{ s.t.
}\quad \max_{\substack{1\leq i < j\leq n \\ j-i \leq 20}} \frac{1}{\sqrt{j-i+1}}
\abs{\sum_{l=i}^j Y_l - u_l}\leq q.
\end{equation*}
For the computation of $\hat u_\text{SMRE}$  in the rightmost panel of Figure
\ref{intro:figsmre} we set $q = q_N(\alpha)=2.9$ which corresponds to a small
value of $1-\alpha\approx 0.01$ in order to avoid oversmoothing. The value of
$\alpha$ was determined by simluations of the statistic $T_N(\varepsilon)$ (see also
\cite{frick:Kab11} for an asymptotic representation of the distribution of
$T_N(\varepsilon)$). Indeed, the result is visually appealing: The kinks, jumps and
peaks are strikingly well recovered,  both in location and height and the smooth
parts of the signal exhibit no artefacts. Also the corresponding qq-plot
confirms  that there are hardly any outliers in the residuals $Y - \hat
u_\text{SMRE}$,  which indicates that oversmoothing is limited to a reasonable
amount. Again, this is all the more remarkable as the regularisation functional
$J$ is known to usually blur edges, peaks and kinks.

Summarising, it becomes evident that the SMRE approach outperforms the standard
method that employs the global quadratic fidelity. In particular, this example
shows that pluggin in the MR-statistic $T_N$ into \eqref{intro:opt} results in
an estimation scheme that regularises in a \emph{locally adaptive}
manner. Aside to the specific choice \eqref{intro:h1penalty} any other convex
regularisation functional $J$ can be ``localised'' in this way, of course, as
for example the squared 2-norm or the total variation semi-norm. It has turned
out, however, that for the present example \eqref{intro:h1penalty} is preferable
since it accounts well for the smooth parts in the signal (no ``staircasing''
effect).

We finally remark, that the computation of $\hat u_\text{SMRE}$ relies on the
algorithmic framework for SMRE as developed in \cite{frick:FriMarMun11} and
will not be discussed here.
\end{example}

The regularisation scheme \eqref{intro:opt} with the MR-statistic $T_N$ as in
\eqref{intro:mrstatspecial}  was studied in
\cite{frick:DavKovMei09} for the specific case  of non-para\-metric regression
in one space dimension and the total-variation  semi-norm as regularisation
functional $J$.  In this paper we will show that the general formulation in
\eqref{intro:opt} reveals the SMRE as a powerful regularisation method far
beyond this situation: It can be extended to space dimensions larger than one as
well as to inverse problems with general $K$ as in \eqref{intro:noisemodel}
including deconvolution problems. Furthermore, we present very general
consistency and convergence rates results for SMRE  in the context of statistical inverse problems and discuss
their impact on particular applications. To our best knowledge, results of this
type have never been obtained before. It is necessary to assume additional
regularity of the true solution of \eqref{intro:lineqn} in order to come up with
convergence rates results. In the context of inverse problems, this is usually
done by formulating so-called \emph{source conditions}. These determine
smoothness classes of solutions for \eqref{intro:lineqn} that guarantee risk bounds and
fast convergence of the estimator to the true signal. In this work we study the
standard source conditions used in the framework of Bregman-divergences that
yield for each penalty functional $J$ in \eqref{intro:opt} \emph{one} specific
smoothness class. As shown in Section \ref{simple} this can be considered as a
generalization of the Sobolev-class of functions with exponent $1\slash 2$. The
formulation of conditions that give optimal convergence rates in a \emph{scale}
of smoothness classes for a general but \emph{fixed} $J$ to our knowledge is
still open and will not be treated in this work.

This paper is organised as follows. After reviewing some basic definitions from
convex analysis and the theory of inverse problems in Section \ref{defs} we
develop in Section Section \ref{gen:multiressec} a general scheme for estimation
for the statistical inverse problem \eqref{intro:noisemodel} based on the convex
optimisation problem
\eqref{intro:opt}. In Section \ref{gen:conssec}
we then prove consistency and convergence rate results in terms of the
Bregman-divergence w.r.t. the regularisation functional $J$. In Section
\ref{simple} we study the performance of the so constructed estimators for
various examples, as the Gaussian sequence model (Section \ref{simple:indep})
and linear inverse regression problems (Section \ref{lutz}). In Section \ref{tv}
we investigate the particular situation when the regularisation functional $J$
is chosen to be the total-variation semi-norm, which has a particular appeal for
imaging problems. Finally, some examples that illustrate the notions of
source-condition and Bregman-divergence are given in Appendix \ref{app:breg} and
the proofs of the main results as well as some auxiliary lemmata are collected
in Appendix \ref{app}.

\section{Basic Definitions}\label{defs}

In this section we summarise some relevant definitions and assumptions needed
throughout the paper.

\begin{assumption}\label{defs:basicass}
\begin{enumerate}[(i)]
  \item $U$ and $V$ denote separable Hilbert spaces. The norms on
  $U$ and $V$ are not further
  specified, and will be always denoted by $\norm{\cdot}$, since the
  meaning is clear from the context.
  \item Let $J:U \rightarrow \overline{\R}$ be a convex functional from $U$ into the extended
  real numbers $\overline{\R}=\mathbb{R} \cup \set{\infty}$.
  The domain of $J$ is defined by
  \begin{equation*}
    D(J) = \set{ u \in U : J(u) \neq \infty}.
  \end{equation*}
  $J$ is called \emph{proper} if $D(J) \neq \emptyset$ and $J(u) >
  -\infty$ for all $u\in U$. Throughout this paper $J$ denotes a convex,
  proper and lower semi-continuous (l.s.c.) functional with dense domain $D(J)$.
  \item $K : U \to V$ is a linear and bounded operator. By
  $\textnormal{ran}(K) = K(U)$ we denote the range of $K$ and by $K^*:V \rightarrow U$ the adjoint
  operator of $K$.
\end{enumerate}
\end{assumption}
In the course of this paper we will frequently make use of tools from convex
analysis. For a standard reference see \cite{frick:ET76}.
\begin{itemize}
  \item The sub-differential (or generalised derivative)  $\partial J(u)$ of $J$
  at $u$ is the set of all elements $p \in U$ satisfying
  \begin{equation*}
    J(v) - J(u) - \inner{p}{v-u} \geq 0\quad\text{ for all }v\in U.
  \end{equation*}
  The \emph{domain} $D(\partial J)$ of the sub-differential consists of all
  $u\in U$ for which $\partial J (u) \neq \emptyset$.

  \item We will prove consistency of estimators with respect to the
  \emph{Bregman-divergence}. For $u \in D(J)$ the Bregman-divergence of $J$
  between $u$ and $v$ is defined by
  \begin{equation*}
    D_J(v,u) = J(v) - J(u) - J'(v)(v-u)
  \end{equation*}
  where $J'(v)(v-u)$ denotes the directional derivative of $J$ at $v$ in
  direction $v-u$. The directional derivative is defined as
  \begin{equation*}
    J'(v)(w) = \lim_{h\rightarrow 0^+}\frac{J(v+hw) - J(v)}{h}.
  \end{equation*}
  and is well defined for convex functions (possibly with values in $[-\infty,
  \infty]$).
  \item For $u \in D(\partial J)$ the  Bregman-divergence of $J$ between
  $u$ and $v$ w.r.t. $\xi \in \partial J(u)$ is defined as
  \begin{equation*}
    D_J^\xi(v,u) = J(v) - J(u) - \inner{\xi}{v-u}.
  \end{equation*}
  The following basic estimates hold
  \begin{equation*}
    0\leq D_J(v,u) \leq D_J^\xi(v,u),\quad \text{ for all }\xi\in\partial J(u).
  \end{equation*}
\end{itemize}

\begin{remark}\label{defs:bregrem}
Clearly, the Bregman-divergence does not define a (quasi-)metric on $U$: It is
non-negative but in general it is neither symmetric nor satisfies the triangle
inequality. The big advantage, however, of formalising asymptotic results
w.r.t. to the Bregman-divergence (such as consistency or convergence rates) for
estimators defined by a variational scheme of type \eqref{intro:opt}, is the
fact, that the regularising properties of the used penalty functional $J$ are
incorporated automatically. If, for example, the functional $J$ is slightly
more  than strictly convex, it was shown in \cite{frick:R04} that convergence
w.r.t. the Bregman-divergence already implies convergence in norm. If, however,
$J$ fails to be strictly convex (e.g. if it is of linear growth) it is in
general hard to establish norm-convergence results but convergence results
w.r.t. the Bregman-divergence, though weaker, may still be at hand.  In
Examples \ref{defs:norm}-\ref{defs:entropy} as well
as in Section \ref{tv} we compute the Bregman-divergence for some particular choices of $J$.

The concept of Bregman-divergence in optimisation was introduced in
\cite{frick:Bre67} and has recently attracted much attention e.g. in the
inverse problems community \citep[see][]{frick:BO04,frick:FriSch10,frick:Csi91}
or in statistics and machine learning \citep{frick:ColSchSin02,
frick:LafPiePie97, frick:ZhaYu05}.
\end{remark}

Next, we introduce different classes of solutions for Equation
\eqref{intro:lineqn} discussed in this paper.

\begin{definition}\label{defs:solution}
\begin{enumerate}[(i)]
  \item Let $u \in D(J)$ be a solution of \eqref{intro:lineqn}. Then $g$ is
  called \emph{attainable}.
  \item An element $u \in D(J)$ is called \emph{$J$-minimising solution} of
  \eqref{intro:lineqn}, if $u$ solves \eqref{intro:lineqn} and
  \begin{equation*}
    J(u) = \inf \set{ J(\tilde u) ~:~ K\tilde u = g}.
  \end{equation*}
  \item Let $g\in V$ be attainable. An element $p\in V$ is called a
  \emph{source element} if there exists a $J$-minimising solution $u$ of
  \eqref{intro:lineqn}  such that
  \begin{equation}\label{defs:solution:source}
    K^*p \in \partial J(u).
  \end{equation}
  Then, we say that $u$ \emph{satisfies the source condition}
  \eqref{defs:solution:source}.
\end{enumerate}
\end{definition}

It is well-known in the theory of inverse problems with deterministic noise
\citep[see][]{frick:EHN96} that the source condition
\eqref{defs:solution:source} is sufficient for establishing convergence rates for regularisation methods. It can
be understood as a regularity condition for $J$-minimising solutions of Equation
\eqref{intro:lineqn}. Put differently, for each regularisation functional $J$
and each operator $K$, the source condition \eqref{defs:solution:source}
characterises \emph{one particular} smoothness-class of solutions for \eqref{intro:lineqn} for which fast
reconstruction is guaranteed. We clarify the notions
\emph{Bregman-divergence} and \emph{source condition} by some examples in
Appendix \ref{app:breg}.

Under fairly general conditions existence of $J$ minimising solution can be
guaranteed. We formalise these conditions in the following result, however, we
omit the proof since it is standard in convex analysis \citep[see][Chap. II
Prop. 2.1]{frick:ET76}.

\begin{proposition}\label{defs:exjmin}
Let $g\in V$ be attainable and assume that for all $c\in \mathbb{R}$ the sets
\begin{equation}\label{defs:comset}
  \set{ u \in U ~:~ \norm{Ku} + J(u) \leq c}
\end{equation}
are bounded in $U$. Then, there exist a $J$-minimising solution of
\eqref{intro:lineqn}.
\end{proposition}

\section{A General Scheme for Estimation}\label{gen}

In this section we construct a family of estimators $\hat u$ for $J$-minimising
solutions (cf. Definition \ref{defs:solution}) of Equation \eqref{intro:lineqn}
from noisy data $Y$ given by the white noise model   \eqref{intro:noisemodel}.
We define the estimators in a variational framework  and prove consistency as
well as convergence rates in terms of the Bregman-divergence w.r.t. $J$.

\subsection{MR-Statistic and
SMR-Estimation}\label{gen:multiressec}

We introduce a class of similarity measures in order to
determine whether the residuals $Y - K\hat u$ for a given estimator $\hat u \in
U$ resemble a white noise process or not. To this end we will consider the
extreme-value distribution of projections of the residuals onto a predefined collection of
lines in $V$.  To this end, assume that
\begin{equation*}
  \Phi = \set{\phi_1,\phi_2,\ldots}\subset \overline{\textnormal{ran}(K)}\backslash\set{0}
\end{equation*}
is a fixed dictionary such that $\norm{\phi_n}\leq 1$ for all
$n\in\mathbb{N}$. For the sake of simplicity, we will frequently make use of the
abbreviation $\phi^*_n = \phi_n \slash \norm{\phi_n}$.

\begin{definition}\label{gen:mrstat}
Let $\set{t_N:\mathbb{R}^+\times (0,1] \rightarrow \mathbb{R}}_{N\in¸\mathbb{N}}$ be a sequence of functions
that satisfy the following conditions
\begin{enumerate}[(i)]
  \item For all $r\in (0,1]$, the function $s\mapsto t_N(s,r)$ is convex,
  increasing and Lipschitz-continuous with Lipschitz-constants $L_{Nr}$ such
  that $ L_{Nr} \leq
  L<\infty$ for all $N\in\mathbb{N}$ and
  \begin{equation}\label{gen:lowbnd}
    0 > \lambda_N(r):= \inf_{s\in \mathbb{R}^+} t_N(s,r) > -\infty.
  \end{equation}
  \item There exist constants $c_1, c_2 > 0$ and $\sigma_0 \in (0,1)$ such
  that for all $0<\sigma < \sigma_0$
  \begin{equation}\label{gen:ineq}
    t_N(s,r)\geq c_1 s + c_2 t_N(\sigma s, r)\quad\text{ for } (s,r)\in
    \mathbb{R}^+\times (0,1]\text{ and }N\in\mathbb{N}.
  \end{equation}
\end{enumerate}
Then, for $N\in\mathbb{N}$, the mapping $T_N: V \rightarrow \mathbb{R}$ defined by
\begin{equation*}
  T_N(v) = \max_{1\leq n\leq N} t_N\left(\abs{\inner{v}{\phi_n^*}},
  \norm{\phi_n}\right)
\end{equation*}
is called a \emph{multiresolution statistic (MR-statistic)}.
\end{definition}

\begin{remark}\label{gen:remmean}
Let $\set{t_N}_{N\in\mathbb{N}}$ be a sequence of functions satisfying i) and ii) in
Definition \ref{gen:mrstat}. For a fixed $N\in\mathbb{N}$ the mappings $\mu_n:V\rightarrow \mathbb{R}$
defined by
\begin{equation*}
\mu_n(v) = t_N(\abs{\inner{v}{\phi_n^*}}, \norm{\phi_n})
\end{equation*}
can be interpreted as the \emph{average} of the signal $v$ restricted to the
subspace spanned by $\phi_n^*$. With $\mu_n$ as above, the MR-statistic $T_N(v)$
in Definition \ref{gen:mrstat} takes the form \eqref{intro:mrstatrough} and
hence can be considered to measure the maximal local average of $v$ w.r.t. the
dictionary $\set{\phi_1,\ldots,\phi_N}$.
 \end{remark}

Definition \ref{gen:mrstat} allows for a vast class of MR-statistics  and the
conditions in (i) and (ii) appear rather technical. The
following example sheds some light on a special class of MR-statistics that
later on will be studied in more detail. We note, however, that our general
setting also applies to more involved statistics, as e.g. introduced in
\cite{frick:DueSpo01,frick:DueWal08}.

\begin{example}\label{gen:mrstatex}
  Assume that $\set{f_N:(0,1]\rightarrow \mathbb{R}}_{N\in\mathbb{N}}$ is a sequence of positive
  functions and define
  \begin{equation*}
    t_N(s,r) := s - f_N(r).
  \end{equation*}
  Then, the assumptions in Definition \ref{gen:mrstat} are satisfied; to be
  more precise, we can set $L = 1$, $\lambda_N(r) = -f_N(r)$ and $c_1 =
  1-\sigma_0$ and $c_2 = 1$, where $\sigma_0\in(0,1)$ is arbitrary but fixed.
  Moreover, for a fixed $N\in\mathbb{N}$, the average functions $\mu_n:V\rightarrow\mathbb{R}$ in Remark
  \ref{gen:remmean} read as
  \begin{equation*}
  \mu_n(v) = \abs{\inner{v}{\phi_n^*}} - f_N(\norm{\phi_n}).
  \end{equation*}
\end{example}

For a white noise process $\varepsilon:V\rightarrow \Ls{2}(\Omega, \mathfrak{A}, \mathbb{P})$  and
$N\in \mathbb{N}$, consider the random variable
\begin{equation*}
  T_N(\varepsilon) =  \max_{1\leq n\leq N} t_N\left(\abs{\varepsilon(\phi_n^*)},
  \norm{\phi_n}\right).
\end{equation*}
Then, for a level $\alpha\in (0,1)$ we denote the
$(1-\alpha)$-quantile of $T_N(\varepsilon)$ by $q_N(\alpha)$, that is,
\begin{equation}\label{gen:quantile}
  q_N(\alpha) := \inf\set{q\in\mathbb{R}~:~ \mathbb{P}\left( T_N(\varepsilon)\leq q \right) \geq
  1 - \alpha}
\end{equation}

Our key paradigm is that an estimator $\hat u$ for a solution of
\eqref{intro:lineqn} fits the data $Y$ sufficiently well, if the statistic
$T_N(Y-K\hat u)$  does not exceed the threshold $q_N(\alpha)$ ($\alpha\in
(0,1)$ and $N\in\mathbb{N}$ fixed). Among all those estimators we shall pick the
\emph{most parsimonious} by minimising the functional $J$.

\begin{definition}\label{gen:smrest}
Let $N\in\mathbb{N}$ and $\alpha\in (0,1)$. Moreover, assume that $T_N$ is an
MR-statistic  and that $Y$ is given by \eqref{intro:noisemodel}.  Then every
element $\hat u_N(\alpha) \in U$ solving the convex optimisation problem
\eqref{intro:opt} is called a \emph{statistical multiresolution estimator
(SMRE)}.
\end{definition}

An SMRE $\hat u_N(\alpha)$ depends on the regularisation parameters $N\in\mathbb{N}$ and
$\alpha\in (0,1)$ that determine the admissible region $\mathcal{A}_N(\alpha)$
in \eqref{intro:admis}. In order to guarantee existence of a solution of the
convex problem in Definition \ref{gen:smrest}, that is existence of an SMRE,  it
is necessary to impose further standard assumptions:

\begin{assumption}\label{gen:assK}
There exists $N_0\in\mathbb{N}$ such that for all $c\in \mathbb{R}$ the sets
\begin{equation*}
  \Lambda(c) = \set{u\in U~:~ \max_{1\leq n\leq N_0}
  \abs{\inner{Ku}{\phi_n^*}} + J(u) \leq c }
\end{equation*}
are bounded in $U$.
\end{assumption}

Assumption \ref{gen:assK}  guarantees weak
compactness of the level sets of the objective functional $J$ restricted to the
admissible region $\mathcal{A}_N(\alpha)$. We note, that if $J$ is strongly
coercive (e.g. when $J$ is as in Example \ref{defs:norm} or
\ref{defs:entropy}) then Assumption \ref{gen:assK} is satisfied without any
restrictions on the operator $K$. If $J$ lacks strong coercivity (as it is e.g. the case with the
total-variation semi-norm studied in Section \ref{tv}) additional properties of
$K$ are required in order to meet Assumption \ref{gen:assK}.

Application of standard arguments from convex optimisation yields

\begin{proposition}\label{gen:smrexist}
Assume that Assumption \ref{gen:assK} holds and let $N \geq
N_0$ and $\alpha\in (0,1]$. Then, an SMRE $\hat u_N(\alpha)$ exists.
\end{proposition}

Finally, we note that Assumption \ref{gen:assK} already implies the
requirements in Proposition \ref{defs:exjmin} and consequently existence of
$J$-minimising solutions.

\subsection{Consistency and Convergence Rates}\label{gen:conssec}

We investigate the asymptotic behaviour of $\hat u_N(\alpha)$ as the noise level
$\sigma$ in \eqref{intro:noisemodel} tends to zero.  According to the
reasoning following Definition \ref{gen:smrest}, the parameters $N\in\mathbb{N}$ and
$\alpha\in(0,1)$ can be interpreted as regularisation parameters and have to be
chosen accordingly: The model parameter $N$ has to be increased in order to
guarantee a sufficiently accurate approximation of the image space $V$, whereas
the test-level $\alpha$ tends to $0$ such that the true solution (asymptotically)
satisfies the constraints of \eqref{intro:opt} almost surely. We formulate
consistency and convergence rate results by means of the Bregman-divergence of
the SMRE $\hat u_N(\alpha)$ and a true solution $u^\dagger$ in terms of almost
sure convergence.

Throughout this section we shall assume  that $\set{\sigma_k}_{k\in\mathbb{N}}$ is a
sequence of positive noise-levels in \eqref{intro:noisemodel} such that
$\sigma_k \rightarrow 0^+$ as $k\rightarrow\infty$. Moreover, we assume that
$\set{\alpha_k}_{k\in\mathbb{N}} \subset(0,1)$ is a sequence of significance levels and
that $N_k\geq N_0$ is such that
\begin{equation}\label{gen:sumlim}
  \sum_{k=1}^\infty\alpha_k < \infty\quad\text{ and }\quad
  \lim_{k\rightarrow\infty} N_k = \infty.
\end{equation}

\begin{theorem}\label{gen:consist}
Assume that Assumptions \ref{defs:basicass} and \ref{gen:assK} hold. Let further
$u^\dagger$ be a $J$-minimising solution of \eqref{intro:lineqn} where $g\in \overline{\textnormal{span} \Phi }$ and assume that
\begin{equation*}
\sup_{N\in\mathbb{N}} T_N(\varepsilon) < \infty
\end{equation*}
and
\begin{equation}\label{gen:paramchoice}
  \zeta_k :=  \sigma_k \max\left(\inf_{1\leq n\leq N_k}
  \lambda_{N_k}(\norm{\phi_n}), \sqrt{-\log \alpha_k}\right)\rightarrow 0.
\end{equation}
Then, for $\hat u_k := \hat u_{N_k}(\alpha_k)$ as in \eqref{intro:opt} one
has
\begin{equation}\label{gen:conseqn}
  \sup_{k\in\mathbb{N}}\norm{\hat u_k} < \infty,\quad J(\hat u_k) \rightarrow
  J(u^\dagger)\quad\text{ and }\quad D_J(u^\dagger, \hat u_k)  \rightarrow 0\quad\text{ a.s. }
\end{equation}
as well as
\begin{equation}\label{gen:imgconseqn}
  \limsup_{k\rightarrow\infty} \max_{1\leq n\leq N_k} \frac{
  \abs{\inner{\phi_n^*}{K\hat u_k - K u^\dagger}}}{\zeta_k} < \infty
  \quad
  \text{ a.s.}
\end{equation}
\end{theorem}

Theorem \ref{gen:consist} states that if for a given vanishing sequence of
noise levels $\sigma_k$, suitable (in the sense of
\eqref{gen:paramchoice}) sequences of regularisation parameters $N_k$ and
$\alpha_k$ can be constructed, then the sequences of corresponding SMRE
converges to a true $J$-minimising solution $u^\dagger$ w.r.t. the
Bregman-divergence. We note that the assumption on the boundedness
of MR-statistic $T_N(\varepsilon)$ is crucial and in general
non-trivial to show.

It is well known that without further regularity
restrictions on $u^\dagger$, the speed of convergence in \eqref{gen:conseqn} can
be arbitrarily slow. \emph{Source conditions} as in Definition
\ref{defs:solution} (iii) are known to constitute sufficient regularity
conditions with quadratic fidelity  (cf.
\cite{frick:MaiRuy96,frick:BisHohMunRuy07,frick:LouLud08}). In our situation, where the
fidelity controls the maximum over all residuals, we additionally have to assume
that the source elements exhibit certain approximation properties:

\begin{assumption}\label{gen:assSE}
There exists a $J$-minimising solution $u^\dagger$ of \eqref{intro:lineqn} that
satisfies the source condition \eqref{defs:solution:source}  with source
element $p^\dagger$. Moreover, for $n,N\in\mathbb{N}$ there exist  $b_{n,N}\in \mathbb{R}$
such that
\begin{equation}\label{gen:seapprox}
  \textnormal{err}_N(p^\dagger):= \norm{p^\dagger - \sum_{n=1}^N b_{n,N} \phi_n^*}\ra0
  \quad\text{ and } \quad\sup_{N\in\mathbb{N}} \sum_{n=1}^N
  \abs{b_{n,N}} < \infty.
\end{equation}
\end{assumption}

\begin{remark}\label{gen:assSErem}
\begin{enumerate}[i)]
  \item Assumption \ref{gen:assSE} amounts to say that there exists a
  $J$-minimising solution $u^\dagger$ that satisfies the source condition
  \eqref{defs:solution:source} with a source element $p^\dagger$ that can be
  approximated sufficiently well by the dictionary $\Phi$ in use.
  From \eqref{defs:solution:source} it becomes clear that we can always assume
  that $p^\dagger \in \overline{\textnormal{ran}(K)}$, such that the first condition in
  \eqref{gen:seapprox} is not very restrictive, in fact.

  \item Good estimates of approximation errors for non-orthogonal dictionaries
  $\Phi$ are hard to come up with in general. Examples of non-orthogonal
  dictionaries where such estimates are available are wavelet-
 \citep{frick:Dau92} and curvelet- \citep{frick:CanDon04} frames.

  \item It is important to note that, given prior information on the true
  solution $u^\dagger$, the conditions in Assumption \ref{gen:assSE} may indicate
  whether a given dictionary is well suited for the
  reconstruction of $u^\dagger$ or not. As we will see in Section \ref{simple},
  a priori information on the smoothness of $u^\dagger$ can typically be
  employed.
\end{enumerate}
\end{remark}

\begin{theorem}\label{gen:thmrates}
Let the requirements of Theorem \ref{gen:consist} be satisfied and assume
further that Assumption \ref{gen:assSE} holds with $g\in \overline{\textnormal{span} \Phi
}$. If $\eta_k := \max(\zeta_k, \textnormal{err}_{N_k}(p^\dagger)) \rightarrow \infty$, then
\begin{equation}\label{gen:rateeqn}
  \limsup_{k\rightarrow\infty} \frac{D_J^{K^*p^\dagger}(\hat u_k,
  u^\dagger)}{ \eta_k} < \infty \quad \text{ and }\quad \limsup_{k\rightarrow\infty}
  \max_{1\leq n\leq N_k} \frac{ \abs{\inner{\phi_n^*}{K\hat u_k - K
  u^\dagger}}}{ \eta_k} < \infty \quad \text{ a.s.}
  \end{equation}
\end{theorem}

\begin{remark}\label{gen:ratesrem}
The convergence rate result in Theorem \ref{gen:thmrates} is rather general, in
the sense that the rate function $\eta_k$ in \eqref{gen:rateeqn} has to be
determined for each choice of $K$, $J$ and $\Phi$ separately. We outline a
general procedure how this can be done in practice: assume that $u^\dagger$ is a
$J$-minimising solution of \eqref{intro:lineqn} that satisfies Assumption
\ref{gen:assSE} with a source element $p^\dagger$.
\begin{enumerate}[(i)]

  \item The sequence $\set{-\inf_{1\leq n\leq N} \lambda_N(\norm{\phi_n})
  }_{N\in\mathbb{N}}$ is positive according to \eqref{gen:lowbnd}. Hence
  \begin{equation*}
    N_k:= \inf\set{ N\in\mathbb{N}~:~ \textnormal{err}_N(p^\dagger) \leq- \sigma_k \inf_{1\leq n\leq
    N} \lambda_N(\norm{\phi_n}) }
  \end{equation*}
  is well-defined and since $\set{\sigma_k}_{k\in\mathbb{N}}$ is
  non-increasing one has $N_k \leq N_{k+1}$ and $N_k \rightarrow \infty$ as
  $k\rightarrow\infty$.
  \item After setting $\eta_k =-\sigma_k \inf_{1\leq n\leq N_k}
  \lambda_{N_k}(\norm{\phi_n})$ it remains to check that the sequence of
  test-levels $\alpha_k = \exp\left(-\left(\kappa
  \eta_k\slash \sigma_k \right)^2\right)$ is summable (for some constant
  $\kappa > 0$).
\end{enumerate}
For the so constructed sequences $N_k$, $\eta_k$ and $\alpha_k$, the
assertions of Theorem  \ref{gen:thmrates} hold.
\end{remark}

\section{Applications and Examples}\label{simple}

In Section \ref{gen} we developed a general method for estimation of
$J$-minimising solutions of linear and ill-posed operator equations from  noisy
data. Our estimation scheme thereby employed the MR-statistic
$T_N$ (cf. Definition \ref{gen:mrstat}).  In this section we will study
particular instances of MR-statistics  covered by the general theory in Section
\ref{gen}:
\begin{itemize}
  \item We study the case where $T_N$ constitutes the extreme-value statistic of
the coefficients w.r.t. an orthonormal dictionary $\Phi$ (Section
\ref{simple:indep}). We show how Assumption \ref{gen:assSE} in this case reduces
to the requirement that the true solution $u^\dagger$ lies in a
Sobolev-ellipsoid w.r.t. the system $\Phi$. Moreover, it will turn out that for
the case when $\Phi$ denotes the eigensystem of a compact operator, SMR
estimation can be considered as soft-thresholding.
  \item In Section \ref{lutz} we skip the assumption of orthonormality and  examine
general SMR-estimation w.r.t. (non-orthonormal)  dictionaries that
satisfy certain entropy conditions. In particular, we will consider the case
when $U = V = \Ls{2}([0,1]^d)$ and when $\Phi$ consists of indicator
functions w.r.t. a redundant system of subcubes in $[0,1]^d$ (cf. Example
\ref{intro:ex}).
\item Finally, we study the case when the penalty functional $J$
is chosen to be the total-variation semi-norm on $U = \L{2}$ in Section
\ref{tv}. We shed some light on the meaning behind the source-condition
\eqref{defs:solution:source} and the Bregman-divergence for total-variation
regularisation, complementing the examples in Appendix
\ref{app:breg}. Additionally, we highlight the implications of our general
convergence rate results for image deconvolution.
\end{itemize}

Throughout this section we assume that Assumptions \ref{defs:basicass} and
\ref{gen:assK} hold. Moreover, we shall agree upon
$\set{\sigma_k}_{k\in\mathbb{N}}$ being a sequence of noise levels such that $\sigma_k
\rightarrow 0^+$ and that for $k\in\mathbb{N}$ there are $\alpha_k \in (0,1)$ and
$N_k\in\set{N_0, N_0+1,\ldots}$ such that \eqref{gen:sumlim} holds.

\subsection{Introductory Example: Gaussian Sequence Model}\label{simple:indep}
In this section we shall consider the case where the dictionary $\Phi  =
\set{\phi_1,\phi_2,\ldots}$ constitutes an orthonormal basis of
$\overline{\textnormal{ran}(K)}$. Evaluation of Equation \eqref{intro:noisemodel} at the
elements $\phi_n$ hence yields
\begin{equation*}
  y_n =  \theta_n + \sigma \varepsilon_n,
\end{equation*}
where $Y(\phi_n) = y_n$, $\theta_n = \inner{Ku}{\phi_n}$ and $\varepsilon_n =
\varepsilon(\phi_n)$. We define the MR-statistic $T_N$ by setting
$t_N(s,r) = s - \sqrt{2\log N}$ in Definition \ref{gen:mrstat}. In
other words, we consider the maximum of the coefficients w.r.t to the dictionary
$\Phi$, that is
\begin{equation}\label{simple:simplestat}
  T_N(v) = \max_{1\leq n\leq N}\abs{\inner{v}{\phi_n}} - \sqrt{2\log N}.
\end{equation}
Since $\set{\phi_1,\phi_2,\ldots}$ are linearly independent and
normalised, it follows that the random variables $\varepsilon_1,\varepsilon_2,\ldots$ are
independent and standard normally distributed. This implies that $
T_N(\varepsilon)$ is bounded almost surely.

In what follows, we will apply Theorems \ref{gen:consist} and
\ref{gen:thmrates} to the present case. To this end, we observe that for
$\sigma > 0$ and $ N\in\mathbb{N}$ it follows that
\begin{equation*}
  -\sigma \inf_{1\leq n\leq N} \lambda_{N} (\norm{\phi_n}) =
  \sigma \sqrt{2\log N}.
\end{equation*}
With the above preparations, we are able to reformulate the consistency result
in Theorem \ref{gen:consist}.

\begin{corollary}\label{simple:conscorindep}
Let $u^\dagger \in U$ be a $J$-minimising solution
of \eqref{intro:lineqn} where $g\in \overline{\textnormal{span} \Phi}$. Moreover, assume
that $\sigma_k^2 \max(\log N_k,-\log \alpha_k) \rightarrow 0$.
Then, the SMRE $\hat u_k = \hat u_{N_k}(\alpha_k)$ almost surely satisfies
\eqref{gen:conseqn} and \eqref{gen:imgconseqn}.
\end{corollary}

In order to apply the convergence rate result in Theorem \ref{gen:thmrates},
Assumption \ref{gen:assSE} has to be verified. We set $b_{n,N}\equiv
\inner{p^\dagger}{\phi_n}$ in Assumption \ref{gen:assSE}. Note that   the
expression $\textnormal{err}_N(p)$ denotes the  approximation error of the $N$-th partial
Fourier-series w.r.t. $\Phi$. Thus, Assumption \ref{gen:assSE} is linked to
absolute summability of the Fourier-coefficients w.r.t. the basis $\Phi$, i.e.
\begin{equation}\label{simple:sourcerep}
  \sum_{n=1}^\infty \abs{\inner{p^\dagger}{\phi_n}} < \infty
\end{equation}
The \emph{Bernstein-Stechkin criterion} is a classical method for
testing for absolute summability. We present a version suitable for our purpose
in the following

\begin{proposition}\label{simple:berstecrit}
Let $p^\dagger \in V$. Then, \eqref{simple:sourcerep} is satisfied if $\sum_{N =
1}^\infty \textnormal{err}_N(p^\dagger)\slash \sqrt{N}  < \infty$.
\end{proposition}

\begin{proof}
  The classical version of the Bernstein-Stechkin Theorem \citep[see e.g. ][Thm.
  7.4]{frick:Lau73} states that for each $f\in \Ls{2}([0,1])$ and each ON-basis
  $\underline{v} = \set{v_1,v_2,\ldots}$ of $\Ls{2}([0,1])$, the
  Fourier-coefficients of $f$ are absolutely summable, if $\sum_{N =
1}^\infty \textnormal{err}_N(p^\dagger)\slash \sqrt{N}  < \infty$. Since
  each separable Hilbert space is isometrically isomorphic to $\Ls{2}([0,1])$,
  the assertion finally follows.
\end{proof}

Following the procedure outlined in Remark \ref{gen:ratesrem} (Section
\ref{gen}) we define
\begin{equation}\label{simple:sequences}
  N_k := \inf\set{N\in\mathbb{N}~:~\textnormal{err}_N(p^\dagger) \leq \sigma_k\sqrt{2\log
  N}}\quad\text{ and }\quad \eta_k := \sigma_k \sqrt{2\log N_k}.
\end{equation}

\begin{corollary}\label{simple:ratescordep}
Let $g\in V$ be attainable and $u^\dagger \in U$ be a $J$-minimising solution of
\eqref{intro:lineqn} that satisfies the source condition with a source element
$p^\dagger$ such that the condition in Proposition \ref{simple:berstecrit}
holds. Moreover, let $N_k$ and $\eta_k$ be defined  as in
\eqref{simple:sequences}. If
\begin{equation*}
  \alpha_k := e^{-\left(\frac{\kappa \eta_k}{\sigma_k}\right)^2} =
  N_k^{-2\kappa^2} \in \ell^1(0,1)
\end{equation*}
for a constant $\kappa > 0$, then the SMRE $\hat u_k = \hat
u_{N_k}(\alpha_k)$ almost surely satisfies \eqref{gen:rateeqn}.
\end{corollary}

The problem of characterising those elements $p^\dagger\in V$ that satisfy the
assumption of Proposition \ref{simple:berstecrit} is a classical issue in
Fourier-analysis and approximation theory. Sufficient condition are usually
formalised by characterising the decay properties of the Fourier-coefficients.
In a function space setting, this leads to particular smoothness classes of
functions and in the general situation can be given in terms of \emph{Sobolev
ellipsoids}: for constants $\beta, Q > 0$ we define $\Theta(\beta, Q)$ as the
infinite-dimensional ellipsoid
\begin{equation}\label{simple:sobell}
  \Theta(\beta,Q) = \set{ \theta \in \ell^2~:~ \sum_{n\in\mathbb{N}} n^{2\beta}
  \theta_n^2 \leq Q^2}.
\end{equation}
The \emph{Sobolev class} $W(\beta, Q)\subset V$ is then defined to consists of
all $v\in V$ such that $\set{\inner{v}{\phi_n}}_{n\in\mathbb{N}}\subset \Theta(\beta,Q)$
\citep[see][Sec.1.10.1]{frick:Tsy09}. For $v\in W(\beta,Q)$ we have that
Proposition  \ref{simple:berstecrit} is applicable if $\beta > 1\slash 2$.

\begin{example}\label{simple:svd}
  Assume that $J(u) = \frac{1}{2}\norm{u}^2$ and let $K$ be a compact operator
  with singular value decomposition (SVD) $\set{(\psi_n,\phi_n,s_n)}_{n\in\mathbb{N}}$:
  $\set{\psi_n}_{n\in\mathbb{N}}$ is an orthonormal basis (ONB) of $\ker(K)^\bot$,
  $\set{\phi_n}_{n\in\mathbb{N}}$ is an ONB of $\overline{\textnormal{ran}(K)}$ and the singular values
  $\set{s_n}_{n\in\mathbb{N}}$ are positive and $s_n\rightarrow 0$ as $n\rightarrow\infty$. Moreover
  \begin{equation}\label{simple:svdeqn}
    K\psi_n = s_n \phi_n\quad\text{ and }\quad K^* \phi_n = s_n \psi_n,
  \end{equation}
  for all $n\in\mathbb{N}$. For $N\in\mathbb{N}$ and $\alpha\in (0,1]$ it turns out (e.g. by
  applying the method of Lagrangian multipliers) that the SMRE $\hat
  u_N(\alpha)$ with $T_N$ as in \eqref{simple:simplestat} is a \emph{shrinkage
  estimator} given by
  \begin{equation*}
    \hat u_N(\alpha) = \sum_{n=1}^N s_n^{-1} y_n \left(1 -
    \frac{q_N(\alpha) + \sqrt{2\log N}}{\abs{y_n}}\right)_+ \psi_n.
  \end{equation*}
  We note that $\hat u_N(\alpha)$ is a particular instance of a soft
  thresholding estimator.

  Now, let $u^\dagger\in U$ be a minimum-norm solution of \eqref{intro:lineqn}
  that satisfies the source condition $K^*p^\dagger = u^\dagger$
  (cf. Example \ref{defs:norm})
  with source element $p^\dagger\in W(\beta,Q)$ for $Q > 0$ and $\beta > 1\slash 2$. Then,
  $\textnormal{err}_N(p^\dagger) \leq Q N^{-\beta}$ and it follows from \eqref{simple:sequences} that
  \begin{equation*}
    N_k \sim \left(\frac{Q}{\sigma_k}\right)^2\quad\text{
    and }\quad \eta_k \sim \sigma_k\sqrt{-\log \sigma_k}.
  \end{equation*}
  If $\sigma_k$ has polynomial decay, we can choose a constant $\kappa > 0$
  such that $\alpha_k = \exp(-(\kappa \eta_k \slash \sigma_k)^2) =
  \sigma_k^{\kappa^2}$ is summable and it follows from Corollary
  \ref{simple:ratescordep} and Example \ref{defs:norm} that
  \begin{equation*}
    \limsup_{k\rightarrow\infty} \frac{1}{\sigma_k\sqrt{-\log
    \sigma_k}}\norm{u^\dagger - \hat u_{N_k}(\alpha_k)}^2 < \infty\quad\text{
    a.s.}
  \end{equation*}
  This corresponds to the choice $\gamma_k = \sigma_k\sqrt{-\log
  \sigma_k}$ in \cite{frick:BisHohMun04}.
\end{example}

As mentioned above, sufficient conditions for the Bernstein-Stechkin
criterion (cf. Proposition \ref{simple:berstecrit}) in a function space
setting are usually formalised in characterising smoothness properties. The following example shows
how this applies to H\"older-continuity.

\begin{example}\label{simple:trigo}
  Let $V = \Ls{2}_{\text{per}}([0,1])$ be the Hilbert space of all
  square-integrable and periodic functions on the unit interval. Moreover,  we
  assume that $\overline{\textnormal{ran}(K)} =
  \Ls{2}([0,1])$ and consider the \emph{trigonometric basis}
  \begin{equation*}
    \phi_{2n} = \sqrt{2}\cos(n\pi x)\quad\text{ and }\quad \phi_{2n+1}
    = \sqrt{2}\sin(n\pi x).
  \end{equation*}
  Assume that  $p^\dagger \in \mathcal{H}_\beta([0,1])\cap V$ (cf. Definition
  \ref{app:hoelder}) with $\beta > 1\slash 2$. Then we have that
  $\textnormal{err}_N(p^\dagger) \leq Q N^{-\beta}\log N$ for a suitable constant $Q>0$ and
  therefore it follows from  Proposition \ref{simple:berstecrit} that
  \eqref{simple:sourcerep} holds.

  Hence, if $u^\dagger$ is a $J$-minimising solution of \eqref{intro:lineqn}
  that satisfies the source condition \eqref{defs:solution:source} with source
  element $p^\dagger \in \mathcal{H}_\beta([0,1])$  and
  if the sequences $N_k, \eta_k$ and $\alpha_k$ are chosen as in Example
  \ref{simple:svd}, then $\hat u_k = \hat u_{N_k}(\alpha_k)$  almost surely
  satisfy \eqref{gen:rateeqn}.
\end{example}

\begin{remark}
\begin{enumerate}[i)]
  \item The assertions of Example
  \ref{simple:trigo} still hold if the trigonometric basis is replaced by any
  other  orthonormal basis $\set{\phi_n}_{n\in\mathbb{N}}$ of $\overline{\textnormal{ran}(K)}$ such
  that the Bernstein-Stechkin criterion in Proposition \ref{simple:berstecrit}
  is satisfied. This holds for example for a vast class of orthonormal wavelet bases of $\Ls{2}([0,1])$ as studied in
  \cite{frick:CohDauVia93}.
  \item For the trigonometric basis in Example \ref{simple:trigo}, the
  Bernstein-Stechkin criterion \ref{simple:berstecrit} can be replaced by the
  requirement that $p^\dagger\in \mathcal{H}_\beta([0,1])$ for any $\beta>0$
  is additionally of bounded variation \citep[see][Vol.1\
  Thm.3.6]{frick:Zyg77}.
\end{enumerate}
\end{remark}

\subsection{Non-orthogonal Models}\label{lutz}

In contrast to Section \ref{simple:indep}, where we considered orthonormal
dictionaries, we will now focus on more general (non-orthonormal)
systems. In other words,  we consider sequences
\begin{equation*}
  \Phi = \set{\phi_1,\phi_2, \dots } \subset \overline{\textnormal{ran}(K)}\backslash\set{0}
\end{equation*}
and assume that $\norm{\phi_n}\leq 1$ for all $n\in\mathbb{N}$. Moreover, we will
make use of the MR-statistic $T_N$ (cf. Definition \ref{gen:mrstat})
defined by
\begin{equation}\label{lutz:statistic}
  t_N(s,r) = s - \sqrt{-2\gamma \log r},\quad (s,r)\in \mathbb{R}^+\times (0,1]
\end{equation}
where $\gamma > 0$ is some constant. As outlined in Example \ref{gen:mrstatex},
one verifies that $t_N(s,r)$ satisfies the assumptions of Definition
\ref{gen:mrstat}. In particular, we find that $\lambda_N(r) = - \sqrt{-2\gamma
\log r} > -\infty$ for all $r\in (0,1]$. The parameter $\gamma$ that appears in
\eqref{lutz:statistic} has to be chosen  appropriately in dependence on $\Phi$
in order to guarantee that the MR-statistic  $T_N(\varepsilon)$ is bounded almost
surely. A sufficient condition on $\gamma$ has  for example been given in
\cite[Thm 7.1]{frick:DueWal08}

\begin{proposition}\label{lutz:teststatfinite}
If there exists constants $A,B>0$ such that
\begin{equation}\label{mrnorm:caprequ}
  D(u \delta, \set{\phi \in \Phi~:~ \norm{\phi}\leq \delta}) \leq A u^{-B}
  \delta^{-\gamma},\quad \text{ for all } u,\delta \in (0,1]
\end{equation}
then almost surely $\sup_{N\in\mathbb{N}} T_N(\varepsilon) < \infty$. Here $D$  denotes the
capacity number (cf. Definition  \ref{lutz:capcovdef}).
\end{proposition}

\begin{corollary}\label{lutz:consistcor}
Let $u^\dagger \in U$ be a $J$-minimising solution of
\eqref{intro:lineqn} where $g\in \overline{\textnormal{span}{\Phi}}$ and $\gamma>0$ be
chosen such that the assumption of Proposition \ref{lutz:teststatfinite} is
satisfied. Moreover, assume that
\begin{equation*}
\sigma_k^2 \min( \min_{1\leq n\leq N_k}
\log\left(\norm{\phi_n}\right), \log \alpha_k) \rightarrow 0.
\end{equation*}
 Then, the SMRE $\hat u_k
= \hat u_k(\alpha_k)$ almost surely satisfies \eqref{gen:conseqn}.
\end{corollary}

In order to apply the convergence rate results in Theorem \ref{gen:thmrates}, it
is necessary that a $J$-minimising solution $u^\dagger$ of \eqref{intro:lineqn}
satisfies the source condition \eqref{defs:solution:source} with a source element
$p^\dagger$ that can be approximated by the dictionary $\Phi$
sufficiently well (cf. Assumption \ref{gen:assSE}). We illustrate the
assertion of Theorem \ref{gen:thmrates} when  $U = V = \Ls{2}([0,1]^d)$ ($d\geq
1$) and when $\Phi$ consists of a countable selection of indicator functions
on cubes in $[0,1]^d$ (cf. Example \ref{intro:ex}).

First, we shall examine when Proposition
\ref{lutz:teststatfinite} holds. To this end, we will focus first on the
(uncountable) collection $\Phi_s$ of indicator functions on cubes in $[0,1]^d$.
Then, according to Proposition \ref{mrnorm:allsetass}, the assumptions of
Proposition \ref{lutz:teststatfinite} are satisfied for $\Phi = \Phi_\text{s}$
and  $\gamma = d$. Particularly, it follows that the assertion of
Proposition \ref{lutz:teststatfinite} also holds for arbitrary (countable)
sub-systems $\Phi\subset\Phi_s$, that is the statistic
\begin{equation*}
  T_N(\varepsilon) = \max_{1\leq n\leq N} \abs{\varepsilon(\chi_{Q_n})} - \sqrt{-d
  \log\abs{Q_n} }\quad\text{ where }\quad\chi_{Q_n}\in \Phi
\end{equation*}
stays bounded a.s. as $N\rightarrow\infty$ (note here, that $\norm{\chi_{Q_n}} =
\sqrt{\abs{Q}}$).

Next, we study Assumption \ref{gen:assSE} in the present setting. Let
$\mathcal{P} = \set{Q_1, Q_2, \ldots}$ be a countable
system of cubes and set $\Phi = \set{\chi_{Q_n}~:~ n\in\mathbb{N}}$. We shall assume
that $\mathcal{P}$ satisfies the conditions of Lemma \ref{reg:approx} (where
$\Omega = [0,1]^d$ and $A_i = Q_i$ for $i\in\mathbb{N}$). Let $\set{n_l}_{l\in\mathbb{N}}$ and
$\set{\delta_l}_{l\in\mathbb{N}}$ be defined accordingly. Moreover, we define
\begin{equation*}
  \varepsilon_l = \inf_{n_l<j\leq n_{l+1}} \sqrt{\abs{Q}} = \inf_{n_l<j\leq
  n_{l+1}} \norm{\chi_{Q_j}},
\end{equation*}
where we assume that $\set{\varepsilon_l}_{l\in\mathbb{N}}$ is non-increasing. This means that we
partition the set $[0,1]^d$ into disjoint sub-cubes
$\set{I_j}_{n_l<j\leq n_{l+1}}$ whose size (or \emph{scale}) is bounded by
$[\varepsilon_l, \delta_l]$. It is more natural to formulate convergence rate results in
terms of the total number $m$ of used scales rather than in the total number of
sub-cubes $N = N(m) = n_{m+1}$. Following  Remark
\ref{gen:ratesrem} and applying Lemma \ref{reg:approx} we therefore define
for a given continuous function $p^\dagger:[0,1]^d\rightarrow \mathbb{R}$
\begin{equation}\label{reg:sequences}
  m_k := \inf\set{ m\in\mathbb{N}~:~ \frac{m+1}{\sum_{\nu = 0}^m
  \omega^{-2}(\delta_\nu, p^\dagger)} \leq -2\sigma_k^2 \log \varepsilon_m
  }\;\text{ and } \; \eta_k := \sigma_k \sqrt{-2\log \varepsilon_{m_k}}.
\end{equation}
Here $\omega(\cdot, p^\dagger)$ denotes the modulus of continuity of
$p^\dagger$ (cf. Definition \ref{app:hoelder}). With this and the general
convergence rate result in Theorem \ref{gen:thmrates} we immediately obtain

\begin{corollary}\label{reg:convrate}
Let $u^\dagger\in\Ls{2}([0,1]^d)$ be a $J$-minimising solution of
\eqref{intro:lineqn} where $g \in \overline{\textnormal{span}{\Phi}}$ and that satisfies the
source condition \eqref{defs:solution:source} with source element $p^\dagger
\in C([0,1]^d)$.  Moreover, let $m_k$ and
$\eta_k$ be defined as in \eqref{reg:sequences}. If
\begin{equation*}
  \lim_{k\rightarrow\infty} \eta_k = 0\quad\text{ and }\quad \alpha_k :=
  e^{-\left(\frac{\kappa \eta_k}{\sigma_k}\right)^2} = \varepsilon_{m_k}^{-2\kappa^2}
  \in \ell^1(0,1)
\end{equation*}
for a constant $\kappa > 0$, then the SMRE $\hat u_k = \hat
u_{N(m_k)}(\alpha_k)$ almost surely satisfy \eqref{gen:rateeqn}.
\end{corollary}

\begin{example}\label{lutz:dyadicpart} We consider the system of all dyadic
  partitions $\mathcal{P} = \mathcal{P}_2$ of $[0,1]^d$ as in Example
  \ref{mrnorm:dyadicsetass}. In particular, we note that the assumptions of Lemma
  \ref{reg:approx} are fulfilled with $n_l = (2^{d(l+1)} - 1)\slash (2^d-1)$,
  $\delta_l = 2^{-l} \sqrt{d}$ and $\varepsilon_l = 2^{-ld\slash 2}$.

  If $p^\dagger\in \mathcal{H}_\beta([0,1]^d)$ for $0<\beta\leq 1$, then there
  exists a constant $Q = Q(p^\dagger) >0$ such that $\omega(\delta_l,
  p^\dagger)\leq Q \delta_l^\beta$. This shows that
  \begin{equation*}
    \frac{m+1}{\sum_{\nu = 0}^m
    \omega^{-2}(\delta_\nu, p^\dagger)} \leq Q^2 d^\beta(2^{2\beta} - 1 )
    \frac{m+1}{2^{2\beta (m+1)}-1}
  \end{equation*}
  for $m\in\mathbb{N}$ large enough. From this and \eqref{reg:sequences} it is easy to
  see, that
  \begin{equation*}
    m_k +1 \sim \frac{1}{2\beta \log 2}\log\left(\frac{Q^2 d^2 (2^{2\beta}
    -1)}{d \log 2 \sigma_k^2 } +1 \right)\;\text{ and }\; \eta_k \sim
    \sigma_k\sqrt{-\log \sigma_k}.
  \end{equation*}
  Thus, if there exists a constant $\kappa > 0$ such that
  \begin{equation*}
    \alpha_k = e^{-\left(\frac{\kappa \eta_k}{\sigma_k}\right)^2} =
    \sigma_k^{\kappa^2}
  \end{equation*}
  is summable and if the true  $J$-minimising solution  $u^\dagger$ satisfies
  the source condition \eqref{defs:solution:source} with  source element
  $p^\dagger \in \mathcal{H}_\beta([0,1])$, then it follows that the
  SMRE $\hat u_k = \hat u_{N(m_k)}(\alpha_k)$  almost surely satisfy
  \eqref{gen:rateeqn} with $\eta_k=\sigma_k\sqrt{-\log \sigma_k}$.
\end{example}

\subsection{TV-Regularisation}\label{tv}

In this section we will study SMR-estimation for the special case where $J$
denotes the \emph{total-variation semi-norm} of measurable, bi-variate
functions. This has a particular appeal for linear inverse problems arising in
imaging (such as deconvolution), since discontinuities along curves (edges, that
is) are not smoothed by minimising $J$.

Over the last years regularisation of (inverse) regression problems in a single
space dimension invoking the total-variation semi-norm has been studied
intensively and efficient numerical methods, such as the \emph{taut-string
algorithm} in  \cite{frick:DK01}, have been proposed (see e.g.
\cite{frick:DK01, frick:DavKovMei09, frick:MamGee97} and references therein). In two or more space
dimensions, however, the situation is much more involved and a generalisation
is difficult \citep[see e.g.][]{frick:HinHinKunOehSch03}.  We study here an
extension to the case of space dimension $2$ as well as to deconvolution by applying the results in
Section \ref{gen} to the following setting:

We assume henceforth that $\Omega\subset \mathbb{R}^2$ is an open and bounded
domain with Lipschitz-boundary $\partial \Omega$ and outer unit normal $\nu$.
Moreover,  we set $U = \L{2}$ and define $\text{BV}(\Omega)$ to be the collection of $u\in U$
whose derivative $\text{D} u$ (in the sense of distributions) is a signed
$\mathbb{R}^2$-valued Radon-measure with finite total-variation $\abs{\text{D} u}$, that is
\begin{equation*}
  \abs{\text{D} u}(\Omega)= \sup_{\substack{\psi \in C_0^1(\Omega, \mathbb{R}^2) \\
  \abs{\psi} \leq 1}} \int_\Omega \diw{\psi} u \diff x <\infty.
\end{equation*}
We note that the norm $\norm{u}_{\text{BV}}:= \norm{u}_{\Ls{1}} + \abs{\text{D} u}(\Omega)$
turns $\text{BV}(\Omega)$ into a Banach-space and that with this norm $\text{BV}(\Omega)$ is continuously
embedded into $\L{2}$. The embedding is even compact if $\L{2}$ is replaced by
$\L{p}$ with $p < 2$ (a proof of these embedding results can be found in
\cite[Thm. 2.5]{frick:AV94}. For an exhaustive treatment of $\text{BV}(\Omega)$ see
\cite{frick:EG92, frick:Z89}). With this, we define
\begin{equation*}
  J(u) = \begin{cases}
\abs{\text{D} u}(\Omega) & \text{ if }u\in\text{BV}(\Omega) \\
+\infty & \text{ else.}
\end{cases}
\end{equation*}
The functional $J$ is convex and proper and, as it was shown e.g. in
\cite[Thm. 2.3]{frick:AV94}, $J$ is lower semi-continuous on $\L{2}$. This
shows, that $J$ satisfies Assumption \ref{defs:basicass} (ii). Next, we examine
Assumption \ref{gen:assK}:

\begin{lemma}\label{tv:compact}
If there exists $n_0\in \mathbb{N}$ such that $\abs{\inner{K\mathbf{1}}{\phi_{n_0}}} >
0$ then Assumption \ref{gen:assK} holds. Here, $\mathbf{1}$ denotes the constant
$1$-function on $\Omega$.
\end{lemma}

\begin{proof}
 Let $c\in \mathbb{R}$ and $\set{u_k}_{k\in\mathbb{N}}\subset \Lambda(c)$. Then in
  particular it follows that $\sup_{k\in\mathbb{N}} J(u_{k_n}) \leq c < \infty$  and thus we find with
  Poincar\'e's inequality \citep[see][Thm. 5.11.1]{frick:Z89}
  \begin{equation*}
    \norm{u_k - \bar u_k}_{\Ls{2}} \leq c_1 J(u_k) \leq c_2 < \infty
  \end{equation*}
  for suitable constants $c_1, c_2 \in\mathbb{R}$, where $\bar u_k =
  \abs{\Omega}^{-1} \int_\Omega u_k(\tau) \textnormal{\,d} \tau $. Now choose $\phi
  \in \set{\phi_1,\dots,\phi_N}$ and observe that
  \begin{multline*}
    \frac{\abs{\bar u_k} \abs{\inner{\phi}{K\mathbf{1}}}}{\norm{\phi}} =
    \frac{\abs{\inner{\phi}{K \bar u_k}}}{\norm{\phi}}  \leq \frac{\abs{\inner{
    \phi }{K(\bar u_k - u_k)}}}{\norm{\phi}} + \frac{\abs{\inner{\phi}{K u_k}}}{\norm{\phi}} \\
    \leq \norm{K} \norm{u_k - \bar u_k}_{\Ls{2}} + \max_{1\leq n\leq N}
    \frac{\abs{\inner{Ku_k}{\phi_n}}}{\norm{\phi_n}}\leq \norm{K} c_2 + c.
  \end{multline*}
  Let $1\leq n_0\leq N$ be such that
  $\abs{\inner{K\mathbf{1}}{\phi_{n_0}}} =: \gamma > 0$. Then,
  $\abs{\bar u_n} \leq (\norm{K} c_2 + c)\norm{\phi_{n_0}} \slash \gamma =:c_3$
  and we find
  \begin{equation*}
    \norm{u_n}_{\Ls{2}}  \leq \left(\norm{u_n
    - \bar u_n}_{\Ls{2}} + \norm{ \bar u_n}_{\Ls{2}} \right)
    \leq c_2 + c_3 \abs{\Omega}.
  \end{equation*}.
\end{proof}

We note that the assumptions in Lemma \ref{tv:compact} already imply the weak
compactness of the sets \eqref{defs:comset} and thus guarantee existence of a
$J$-minimising solution of \eqref{intro:lineqn}. From the above cited embedding
properties of the space $\text{BV}(\Omega)$ it is easy to derive an improved version of the
consistency result in Theorem \ref{gen:consist}.

\begin{corollary}\label{tv:consist}
Let $g\in\overline{\textnormal{span}{\Phi}}$ and assume that $u^\dagger\in\text{BV}(\Omega)$ is the unique
$J$-minimising solution of \eqref{intro:lineqn}. Moreover, let
$\set{\alpha_k}_{k\in\mathbb{N}}$ and $\set{N_k}_{k\in\mathbb{N}}$ be as in Theorem
\ref{gen:consist} and define $\hat u_k = \hat u_{N_k}(\alpha_k)$. Then,
additionally to the assertions in Theorem \ref{gen:consist} we have that
\begin{equation*}
  \lim_{k\rightarrow\infty} \norm{\hat u_k -u^\dagger}_{\Ls{p}} = 0\quad\text{ a.s.}
\end{equation*}
for every $1\leq p<2$.
\end{corollary}

\begin{proof}
  From Theorem \ref{gen:consist} it follows that $\set{\hat u_k}_{k\in\mathbb{N}}$ is
  bounded a.s. in $\L{2}$ and that each weak cluster point is a $J$-minimising
  solution of \eqref{intro:lineqn}. Since we assumed that $u^\dagger$ is the
  unique $J$-minimising solution of \eqref{intro:lineqn}, it follows that $\hat
  u_k \rightharpoonup  u^\dagger$ in $\L{2}$ a.s. and therefore also in $\L{p}$
  for each $1\leq p<2$.

  Since $\Omega$ is assumed to be bounded, it follows that $\L{2}$ is
  continuously embedded into $\L{1}$. Thus, it follows from Theorem
  \ref{gen:consist} that almost surely $\sup_{k\in\mathbb{N}} \norm{\hat u_k}_{\text{BV}} <
  \infty$.  From the compact embedding $\text{BV}(\Omega)\hookrightarrow \L{p}$ for $1\leq p<
  2$, it hence follows that $\set{\hat u_k}_{k\in\mathbb{N}}$ is compact in $\L{p}$.  Thus,
  the assertion follows, since weak and strong limits coincide.
\end{proof}

Unfortunately, the above embedding technique can not be used in order to
improve the convergence rate result in Theorem \ref{gen:thmrates} to strong
$\Ls{p}$-convergence and thus we have to settle for the general results in
Theorem \ref{gen:thmrates}. Therefore, we aim for an interpretation of
convergence w.r.t. the Bregman-divergence in \eqref{gen:rateeqn}. We summarise:

\begin{lemma}\label{tv:subgr}
  One has $\xi\in\partial J(u)$ if and only if there exists
  $z\in\Ls{\infty}(\Omega, \mathbb{R}^2)$ with $\norm{z}_{\Ls{\infty}} \leq 1$ such
  that $\inner{z}{\nu}=0$ on $\partial \Omega$,
  \begin{equation*}
    \diw{z} = \xi\quad\text{ and }\quad \int_\Omega \xi u\diff x = \abs{\text{D}
    u}(\Omega).
  \end{equation*}
  If $\xi \in \partial J(u)$, then $D_J^\xi(v,u) = \abs{\text{D} v}(\Omega)
  -\int_\Omega \xi v \diff x$.
\end{lemma}
\begin{proof}
  The representation $D_J^\xi(v,u) = \abs{\text{D} v}(\Omega)
  -\int_\Omega \xi v \diff x$ directly follows from the
  definition of the Bregman-divergence and the first assertion of the Lemma. The
  latter was proved e.g. in \cite[Thm. 4.4.2]{frick:Fri08}.
\end{proof}

\begin{remark}\label{tv:angle}
The result in Lemma
\ref{tv:subgr} allows a geometrical interpretation of the
Bregman-divergence w.r.t. the functional $J$. As it was
worked out in \cite[Sec. 5.1]{frick:BFO+06}, one can show that
\begin{equation*}
  D_J^\xi(v,u) = \int_\Omega (1- \cos(\gamma(v,u,x))) \textnormal{\,d} \abs{\text{D} v}(x)
\end{equation*}
where $\gamma(v,u,x)$ denotes the angle between the unit normals of the
sub-levelsets of $u$ and $v$ at the point $x\in\Omega$.
\end{remark}

We recall that a function $u \in \text{BV}(\Omega)$ satisfies the source condition, if there
exists $\xi \in \textnormal{ran}(K^*)$ such that $\xi \in \partial J(u)$. It is important to
note, that in many applications the elements in $\textnormal{ran}(K^*)$ exhibit high
regularity such as continuity or smoothness. Thus it is of particular interest,
if such regular elements in $\partial J(u)$ exist. If $u$ is itself a smooth
function, application of Green's Formula and Lemma \ref{tv:subgr} yield
\citep[see also ][Lem.3.71]{frick:SchGraGroHalLen09}.
\begin{lemma}\label{tv:smoothsubgr}
Let $u\in C_0^1(\Omega)$ and set $E[u] = \set{x\in\Omega~:~ \nabla u(x) \not =
0}$. Assume that there exists $z\in C_0^1(\Omega, \mathbb{R}^2)$ with $\abs{z}\leq 1$
and
\begin{equation*}
  z(x) = -\frac{\nabla u(x)}{\abs{\nabla u(x)}}\quad\text{ for }x\in E[u].
\end{equation*}
Then, $\xi:=\diw{z}\in \partial J(u)$.
\end{lemma}

In many applications (such as imaging) the true solution $u\in\text{BV}(\Omega)$ is not
continuous, as e.g. if $u$ is the indicator function of a smooth set
$D\subset\Omega$. The following examples shows that in this case we still have
$\partial J(u)\cap C_0^\infty(\Omega) \not = \emptyset$. For the analytical
details we refer to \cite[Ex. 3.74]{frick:SchGraGroHalLen09}

\begin{example}\label{tv:char}
  Assume that $D\subset\Omega$ is a closed and bounded set with
  $C^\infty$-boundary $\partial D$ and set $u = \chi_D$. The outward unit-normal $n$ of $D$ then can
  be extended to a compactly supported $C^\infty$-vector field $z$ with
  $\abs{z}\leq 1$.
   Independent of the choice of the extension, we then have
   $\xi:=\diw{z}\in\partial J(u)$ and $\xi\in C^\infty_c(\Omega)$.

\end{example}

\begin{example}\label{tv:conv}
  We consider $\Omega = [0,1]^2$ and $V = \L{2}$. Moreover, we assume that
  $\mathcal{P}_2$ denotes the set of all dyadic partitions
  of $\Omega$ (cf. Example \ref{mrnorm:dyadicsetass}) and that $\Phi$ is
  the collection of indicator functions w.r.t. elements in $\mathcal{P}_2$.

  For a  function $k:\mathbb{R}^2 \rightarrow \mathbb{R}$, we consider the
  \emph{convolution operator} on $U$ defined by
  \begin{equation*}
    (Ku)(x) = \int_{\mathbb{R}^2} k(x-y)\bar u(y) \diff x\quad \text{ for }x \in \Omega
  \end{equation*}
  where $\bar u$ denotes the extension of $u$ on $\mathbb{R}^2$ by zero-padding. Assume
  further that $u^\dagger$ is the indicator function on a closed and bounded set
  $D\subset\Omega$ with $C^\infty$-boundary $\partial D$ and that $\xi \in
  \partial J(u^\dagger)$ is as in Example \ref{tv:char}. If the
  Fourier-transform $\mathcal{F}(k) =:\hat k$ of $k$ is non-zero a.e. in $\mathbb{R}^2$
  and if there exists $\beta\in(1,2]$ such that
  \begin{equation*}
    (1+\abs{\cdot}^2)^{-\beta\slash 2} \left(\hat \xi\slash \hat k\right) \in
    \Ls{2}(\mathbb{R}^2)\quad \text{ and }\quad \textnormal{supp}\left( p^\dagger :=
    \mathcal{F}^{-1}\left(\hat \xi\slash \hat k\right)\right) \subset \Omega,
  \end{equation*}
  then Assumption \ref{gen:assSE} is satisfied. To be more precise, we have
  that  $p^\dagger \in \mathcal{H}_{\beta-1}(\Omega)$ \cite[see][Thm.
  7.63]{frick:A75} and if there exists a constant $\kappa > 0$ such that
  $\alpha_k:=\sigma_k^{2\kappa}$ is summable it follows from Example
  \ref{lutz:dyadicpart} and Lemma \ref{tv:subgr} that
  \begin{equation*}
    \limsup_{k\rightarrow\infty} \frac{\abs{\text{D}\hat u_k}(\Omega) - \int_\Omega \xi \hat
    u_k \diff x}{\sigma_k \sqrt{-\log \sigma_k}}
    =  \limsup_{k\rightarrow\infty} \frac{\int_\Omega 1 - \cos(\gamma(\hat
    u_k, u^\dagger,x))\textnormal{\,d}\abs{\text{D} \hat u_k}(x)}{\sigma_k
    \sqrt{-\log \sigma_k }} < \infty\quad\text{ a.s.}
  \end{equation*}
  for the SMRE $\hat u_k = \hat u_{N_k}(\alpha_k)$ (where $N_k$ is as in Example
  \ref{lutz:dyadicpart}).
\end{example}

\section*{Acknowledgement}

K.F. is supported by the DFG-SNF Research Group FOR916 \emph{Statistical
Regularization} (Z-Project). P.M and A.M. are supported by the BMBF project
$03$MUPAH$6$ \emph{INVERS} and by the SFB755 \emph{Photonic Imaging on the
Nanoscale}. A.M. is supported by the SFB803 \emph{Functionality Controlled by
Organization in and between Membranes}. The authors would like to thank
L.~D{\"u}mbgen and A.~Tsybakov for stimulating discussions.

redpajama_set_name: RedPajamaArXiv


Work up a buzz around your latest promotions with our A4 strut cards.
If you're after high-impact advertising, printed strut cards are ideal retail displays. They're vibrant, fun and when designed correctly, shout your message loud and clear to everyone who walks by.
Strut cards or show cards work best when placed in prominent positions; they're perfect POS countertop display items. So just stick them somewhere obvious and watch them do their thing; engaging your customers and boosting your sales.
Our showcards are printed in full colour and depending on the quantity you choose are either printed direct to 2mm board (2000 micron) or are litho printed and mounted onto 2mm board with an easy to use rudder strut attached to the reverse. So they're ready and raring to go. Choose from either a Portrait or Landscape A4 strut cards.
We can even create you bespoke a4 die cut strut cards in any shape and size you can think of. So get creative and click here!
We aim to deliver your finished A4 strut cards within 3-5 working days of proof approval.
Designs can be uploaded at the checkout stage. Files should be uploaded in PDF format as single pages; our team can give you guidance as required. Free A4 showcard templates are available here.


text:
Supreme Court rules against 'Israeli' ethnicity on ID
Three-judge panel rejects appeal to force the state to register individuals as 'Israeli' instead of 'Jewish'
By Aaron Kalman	3 October 2013, 1:14 pm 8 Edit
Aaron Kalman is a former writer and breaking news editor for the Times of Israel
President of the Supreme Court, Asher Grunis (photo credit: Alex Kolomoisky/Flash90)
There is no such thing as Israeli ethnicity, the Supreme Court ruled as it rejected an appeal by a number of people requesting that their state-issued ID cards register their ethnicity as "Israeli" rather then "Jewish."
Headed by Supreme Court President Asher Grunis, the three-judge panel said Wednesday it was not the court's mandate to determine new categories of le'om, a Hebrew word translated as ethnicity or nationhood, the judges said in their ruling.
The appeal came after the group's initial petition was rejected in 2007 by judge Noam Sohlberg, then a district magistrate in the Jerusalem District Court.
The petition was led by Professor Uzzi Ornan, a Jerusalem-born 90-year-old linguist and social activist. When the state was formed in 1948 he refused to be registered as Jewish, claiming he had no religion and was of "Hebrew" ethnicity. The request was accepted.
In 2000 Ornan decided to change his ethnicity to "Israeli," but the Interior Ministry refused the request, causing the professor to go to court. In 2007 former minister Shulamit Aloni and other prominent activists joined Ornan in an appeal to the Jerusalem District Court.
Judge Uzi Fogelman wrote that rejecting the appeal did not "take away from the principal struggle of the appellants, from their personal views or from the discourse which will continue [to take place] in the public sphere."
"The natural place for these discussions isn't in the courtroom, but rather in other arenas of public debate and academic writing," Fogelman wrote.
The third judge, Hanan Melcer, said that in the current situation "citizenship was separate and ethnicity was separate." He wrote there was no place to unite the different ethnicities living in Israel under a new and inclusive ethnicity. Such a move, he stated, "was against both the Jewish nature and the democratic nature of the State."
In one key question Grunis voiced a minority opinion. Melcer and Fogelman both thought the theoretical question of forcing the state to provide new ethnicity options (as demanded by the public) on the ID card was one which could be debated in court, while the president said it was not a legal issue.
"In its ruling the court, in effect, agrees to totally ignore the obligations included in the Declaration of Independence, which promises full equality among all the state's citizens, regardless of religion, race or gender," Haaretz quoted Ornan as saying following the ruling.
"The government consensus that has developed ignores the existence of an Israeli people that was created with the Declaration of Independence," Ornan continued. "This consensus enables the Jewish majority to have full control over the country and to operate not for the benefit of Israeli citizens but for the benefit of the current political majority among the Jews."
Israel Supreme Court
Asher Grunis
Hanan Melcer
Uzzi Ornan
Uzi Vogelman

redpajama_set_name: RedPajamaCommonCrawl


text:
Cairenn Chasdub; ("Cairenn ricci-neri") fu, secondo la leggenda e la tradizione storica irlandese medievale, la figlia di Sachell Balb, re dei Sassoni, la seconda moglie del re supremo d'Irlanda Eochaid Mugmedon, e la madre di Niall dei Nove Ostaggi.

Quando era incinta di Niall, la prima moglie di Eochaid, Mongfind, era gelosa e la costrinse a eseguire lavori pesanti, sperando di farle abortire. Cairenn partorì accanto a un pozzo mentre attingeva acqua e, per paura di Mongfind, lasciò il bambino esposto agli uccelli. Ma il bambino fu salvato e allevato da un poeta chiamato Torna. Quando il bambino, Niall, crebbe, tornò a Tara, sollevò sua madre dal lavoro e divenne lui stesso Re Supremo.

Date le date di Niall (si suppone che sia morto tradizionalmente intorno alla fine del V secolo, anche se gli storici moderni lo collocano mezzo secolo dopo), è anacronistico che sua madre sia stata una sassone. O'Rahilly sostiene che il nome Cairenn deriva dal nome latino "Carina" e che sia plausibile che potesse essere stata una romano-britannica. Coerentemente, Geoffrey Keating la descrive non come una sassone ma come la "figlia del re di Gran Bretagna".

Note

Irlanda medievale
Mitologia irlandese

redpajama_set_name: RedPajamaWikipedia


text:
Grid 2 Steam CD-Key
Be fast, be first and be famous as the race returns in GRID 2, the sequel to the BAFTA-award winning, multi-million selling Race Driver: GRID.
Experience aggressive racing against advanced AI and become immersed in the race with GRID 2's new TrueFeel Handling system which powers edge of control exhilaration behind the wheel of every iconic car. The next generation of the EGO Game Technology Platform delivers genre-defining visuals and jaw-dropping damage as you prove yourself across three continents in a new, evolving world of motorsport. Earn fame, fans and fortune as you blaze your way to the top in intense, relentless races on licensed circuits, beautifully realised city streets and lethal mountain roads.
Show All Content
CD key Information:
Grid 2 Steam CD-Key is the serial number or product code which is a combination of letters and numbers that activates Grid 2, normally found on a sticker inside the game's case or printed on the game's quick reference card. The purchased Grid 2 Steam CD-Key global is used to register and activate the relevant game. Depending on the product, SCDKey.com provides this in the form of a scan of the code or the actual code in text format.
Note: All of our products are delivered digitally in the format of a Grid 2 Steam CD-Key which can be activated on one the relevant platform shown above. In stock. Welcome to order.


Introducing the miniSHARK kit, a powerful DSP module designed to fit the needs of floating point audio processing for OEM applications and custom products. From room correction to linear phase crossover filter, the miniSHARK palm size form factor is the perfect fit for to complete your product with a ready made module.
@ miniDSP, we believe in flexibility and open architecture. The concept of the miniSHARK kit is to provide an open platform where algorithm designers can easily load their custom IIR/FIR based filters on the DSP. Thanks to the onboard SD card, designers do not require a computer to configure the device nor to upgrade firmware. For real time configuration, the driverless USB connectivity allows control from both Windows and Mac environment.
STOCK UPDATE(21/03/2019): The miniSHARC kit is unfortunately out of stock as we ran out of modules. We hope to build a new batch in the comming weeks.
32bit floating point - Current support for 48k and 96k on 2 plug-ins.
Plug&Play USB driver and Software configurable via Mac/Win plug-in.
Once a plug-in redeemed, the download will automatically become available under your UserDownloads section. Please make sure to read the user manual for more details.
Power consumption depends on loaded DSP firmware.
Introducing the world of Digital Room Correction (DRC), a process where digital filters are used to correct speaker + room aberrations. A 3 step process yet an acoustical challenge where DSP & Math Gurus use all resources to solve this complex problem. The following lines will summarize the basics of room correction in a setup involving a PC/Mac with a measurement/filter generation software, a measurement microphone and an audio processor (OpenDRC).
In this application note, we will explain the difference between FIR ("finite impulse response") and IIR ("infinite impulse response") filtering.
rePhase is a Windows-based freeware program written by Thomas (aka "pos"), a long time miniDSP community member. rePhase generates finite impulse response (FIR) filters that "reverse" the phase shifts introduced by a loudspeaker crossover. rePhase can also generate linear-phase crossovers. With the aid of a real-time FIR filtering engine or "convolver" such as miniDSP's OpenDRC or miniSHARC, the result is a linear-phase loudspeaker system.
This tutorial will provide a walk-through of filter creation using Filter Hose to linearize a loudspeaker frequency and phase response. Data will be exported to MiniDSP OpenDRC.


Guru Nanak College, Chennai has advertised in THE HINDU newspaper for recruitment of Assistant Professor Plus Non-Faculty jobs vacancies. Interested and eligible job aspirants are requested to apply within 10 days from 07th April 2019. Check out further more details below.


text:
'Observations and Interpretations' Exhibition Starts
Observations and Interpretations
Exhibition starting Saturday 9th October
Lesley Miller and John Thirlwall are both painters.
Preview evening on Friday October 8th, 7pm to 8.30pm.
Lesley Miller
Lesley was born in Brixham and studied Art at Wolverhampton and Birmingham in the 60's.
She taught art in schools in London, Loughborough, Gateshead, Stoke upon Trent and Barton under Needwood, as well as raising 4 boys.
She worked on many practical art courses for teachers and students throughout the UK, cementing her reputation as a skilled painter, draughtsman and educationalist.
Lesley exhibited her work in various open exhibitions and had a one-woman show at the New Vic. She loved working from the life model and from flowers and had a special feeling for the landscape no matter where she was. Her work shows a flair for composition, colour, mood and surface texture, constantly remaining true to her belief in direct observation. Lesley owed a debt to many artists, from Cezanne and Matisse to the great masters of the Renaissance period.
Sadly Lesley died prematurely this year, and is much missed by her family, friends and colleagues in the art fraternity, and especially by her partner with whom she shared all of her hopes and dreams over 32 years.
John Thirlwall
John was born in South Shields and studied art at Sunderland and Liverpool in the 60's.
He taught art in schools in Nottingham, Sunderland and Manchester Polytechnic before becoming art adviser to Sunderland LEA and art inspector for Staffordshire CC.
John organised and taught on numerous practical courses for teachers and students throughout the UK, and also led many trips in Europe and Asia for teachers.
He has exhibited his work in numerous galleries throughout the UK in open exhibitions, shared exhibitions and one man shows. He is a great believer in the primacy of drawing, and loves working from the life model and from landscape features. He invests his work with a strong sense of tone, colour and surface texture. John acknowledges the debt he owes to great artists such as Cezanne, Matisse, Piero della Francesca and de Stael as well as many contemporary artists.
His life partner and muse Lesley died earlier this year, and his contribution to this show is dedicated to her. RIP my beautiful wife.
The Gallery will open on Saturday 9th October from 10 to 4pm. From then, opening will be Wednesday to Saturday 10am to 4pm, and the first Sunday in the month.


text:
What VR DreamZ Is About
Meet Our DreamZ Team
Developing Innovative Teaching with Virtual Reality
VR dreamz article.pdf
One of the core values at University of St. Augustine for Health Sciences is "promoting excellence and innovation in education," and Dr. Jon Edenfield, a 2000 graduate from one of the University's first Occupational Therapy cohorts, carried that innovative mindset into his practice. He is on the forefront of new technologies that will help children with developmental disabilities through virtual reality.
In January 2019, Stella Johnson, CEO of Hope Haven Children's Clinic in Jacksonville, FL, connected VR Dreamz, a virtual reality company, with Great Strides Rehabilitation Inc, a comprehensive pediatric therapy and educational center of excellence, and Dr. Edenfield's rehab center.
VR Dreams has approached the clinic because they wanted to create an application to be used by therapists, but they had no idea where to start.
"We had about 10-15 therapists come to a meeting and we brainstormed about 25 different potential applications for this VR," Dr. Edenfield said. "A lot of them having to do with various development disabilities."
At their initial meeting, Executive Director of VR Dreamz, Peter M. von Dyck, put the VR goggles on Dr. Edenfield and his team to show them the technology's capabilities.
The goggles immerse users in a whole new environment, allowing them to look around and explore, but VR Dreamz also have sensors that go on users' hands and feet. The sensors give the users feedback when they reach to touch or feel things within the virtual environment, making the experience even more real....
To read more about this new partnership click HERE
Look for VR DreamZ to be featured in The University of St. Augustine for Health Sciences' newsletter for Occupational Therapy month. Coming out soon!
Our MOSH event was a hit!
VR DreamZ and Timucuan Parks Foundation are featured on the First Coast News in Jax! Check out the video below!
VR DreamZ and Timucuan Parks Foundation talk upcoming project for brining Jax parks to hospital bound children. To Listen to the interview with NPR, click the picture below!
Teaming Up With
VRdreamZ had a great showcase at the 2017 Serving Up a Cure charity event. Great to see so much community interest and activity to help provide new solutions to help fight against, live with and beat cancer.
Partnering Up With
VR DreamZ is partnering with Timucuan Parks Foundation to bring a Virtual Reality TPF Park Experience to hospitalized children! Please help us achieve this by donating to the cause or contact us to learn more about how you can help!
VR DreamZ 2017


text:
Browse: Home » Distractions » 2015: The Year of Cities
2015: The Year of Cities
February 29, 2016 · by Haywire · in Distractions
Look who we happened to meet on the subway! It's Off Peak, Mini Metro, Yakuza 5, Cities: Skylines, and Tonight You Die.
Jazz cellist and game developer Cosmo D synthesizes two distinct spaces to set his subtly exhilarating, dreamlike game Off-Peak. We're treated to a train station – a space governed by rigid, utilitarian schedules and fueled by unending commerce – that doubles as a museum and its underlying democratic ideal in making art publically accessible.
These tensions between the world of commerce and the world of art lie at the heart of Off-Peak, evoking the writings of absurdist author Franz Kafka in which individuals seem unable to topple vague oppressors in surreal worlds that resist interpretation. Off-Peak's minimal first-person walker gameplay invites players to collect scattered pieces of a train ticket and thus carefully explore this surreal world.
Like Limits & Demonstrations or Thirty Flights of Loving, two other games partly about navigating a museum (and the latter also about a transportation hub), Off-Peak is concerned with our relation to art and cultural references embedded within its environment. Cosmo D provides a carnivalesque menagerie of characters and found objects carefully calibrated to stupefy and astonish. Culled together and exhibited for our contemplation include a colossal whale swimming through painted galaxies, a trio of bespectacled albino stalkers, giants playing board games, a serpentine Aztec relic, and real-life movie posters of the Polish school of design, including ones for movies The Legacy and Vertigo.
I think these Polish movie posters are the key text in unlocking Off-Peak. They come from artists conveying expressionist themes within an authoritarian world behind the Iron Curtain. Likewise, Off-Peak is about capitalism and its chokehold on both the creation and curation of art. Its setting overflows with displayed artworks, yet the musicians and artists you encounter admit to taking sabbaticals because such careers are not financially sustainable.
Perhaps such rarefied allusions will be lost to many, but at least Off-Peak engages with the kind of art that videogames rarely depict, asking players to consider a wealth of artistic and historical traditions difficult to ignore. Off-Peak is the rare kind of game that bridges videogames to broader discourses on art and its reception, and in so doing, moves the medium forward.
Miguel Penabella is a freelancer and comparative literature academic who worships at the temple of cinema but occasionally bears libations to videogames. His written offerings can be found on Kill Screen, First Person Scholar, and Unwinnable, all of which are archived on his blog, Invalid Memory.
Mini Metro spent the best part of a year in Early Access, finally releasing in November of 2015. It's half-way between a strategy game and a puzzle game, and puts you in charge of subway systems in various major cities across the world. Each game starts with three stations which you can connect together with subway lines and trains, with more stations popping up as you progress. Stations come in various shapes, and passengers will appear in the shape of the station they need to go to. New station types are also introduced as the game progresses. For every week of in-game time – about 2 minutes – you are given a new train and the choice of one of two bonus items, which come in the form of new lines, extra carriages and tunnels. These become crucial to keeping everything running efficiently.
The pace of the game is initially sedate, but as the speed at which passengers appear is constantly increasing, things get more and more frantic the longer you last, as you find yourself moving lines and trains around in order to desperately clear overcrowding at a station. As you become more familiar with the game's systems, you'll start surviving for longer as you develop strategies for streamlining your subway, and start noticing problems before they start. The different cities feature different layouts and come with subtly different tools: Tokyo's Shinkansen moves much faster than other trains, for example. These differences, and changes you can make to the game mode help keep things fresh, even though you're doing essentially the same thing every time. The visual and sound design are also notable. The clean underground map visuals work perfectly, and Disasterpeace's generative soundtrack builds up a soundscape as your trains move around. Everything feels of a piece, and it's the harmony of all these elements that makes the game so successful at what it does.
David Thatcher worked in the games industry as a QA technician for 10 years, and is now one half of the indie games studio TriCat Games, handling the majority of the art and audio tasks. His personal site is at giraffe.cat.
What makes Yakuza such a great series if you've never stepped into the shoes of Kazuma Kiryu before? As my Mom puts it, it's that the games are "very Japanese": Yakuza perfectly captures the day-to-day Japanese modern culture, and then wraps it up in the most gripping and entertaining Yakuza-based melodrama you could imagine. Yakuza 5 takes what makes the series great, and doubles down on it. The real standout are the sub-stories the main cast has. From driving taxis as Kazuma, to hunting game in the mountain as Taiga, these are fully-fledged quests and systems in and of themselves
Taxi driving is more entertaining than it has any right to be. Making sure the customers are happy by correctly indicating, slowing down smoothly and stopping at red lights, all while trying to keep up with their conversations and getting to the destination on time is a delightful challenge. These missions have the added benefit of levelling up your taxi to unlock decals, engine enhancements and sick rims allow you to take on the Devil Killers, a renegade group of engine-heads that are terrorizing the city in a high-speed Daytona/Ridge Racer-esque race.
You can find the same attention to detail at every corner of Yakuza 5. A stop at Club SEGA presents you not only with a playable Taiko no Tatsujin – a debut for this rhythm game outside of Japan – and an arcade version of Virtua Fighter 2, but also PuriKura photo booths and a multitude of crane games filled with Hatsune Miku figurines and cute plushies. This is only the tip of the minigame iceberg. This is only in one building. One location in one city, of five. You've yet to experience the ramen minigame, the shogi and mahjong leagues, the underground gambling area, pachinko parlours, darts, all the pool variants you can possibly think of – the list goes on. A literal checklist in the pause menu that tracks everything you can possibly do, mind.
Don't be surprised if you don't even reach 40% of game completion by the time the final act falls. The main story is only a small part of that percentage. And you'll come back after it's all over, just to breathe in that virtual Japanese air once again and experience something that you'll never get anywhere else.
Andy Rae is a mythical sloth-like beast that can be rarely sighted in Leeds, UK. When he's not in his natural sleeping state, he can be found talking about anime on the Key Frames podcast. The best way to capture this elusive creature is to place an amiibo under a box propped up by a stick.
At some point in each of my Cities: Skylines games I rename a neighborhood "Poop Plague Memorial Heights." This is because, at the same point in each game, something goes mysteriously wrong with my plumbing and everyone dies from sewage-related illness. The trash and bodies pile up, their removal hindered by my poorly-laid roads, and there's a bit of a scramble until I can right things again.
I've come to accept this as part of the rise and fall of my cities. Like a well-functioning water system, the game has an ebb and flow; there are problems and solutions and problems again. There's something delightful in figuring out where a situation originates – be it a lack of workers, a traffic snarl, or low property value – and righting it, only for the fix to ripple out into new, unexpected waves. Change an intersection, and green smiles and red frowns flicker across your city like a switchboard: there's better traffic but more noise; the rich part of town lost their park but can get to work easier. It's a gentle pull and tug, one that can go from soothing to demanding in an instant, but one that is always captivating.
Certain values implicit in the system can feel constraining at times, and the fact that all my citizens are white and most of them are blond gives me pause. But Cities: Skylines is a game about cities rather than people, about tinkering with roadways and zoning laws and seeing what happens. The sound design and colors make clear that the game is a big toy, and each new start is like emptying a box of Legos onto the carpet as a kid and spending hours lost in your imagination.
Riley MacLeod is the Managing Editor of Kotaku. His work has appeared at Offworld, Kill Screen, Unwinnable, Zam, and others.
Tonight You Die
I played Tonight You Die by Duende Games sometime during the summer of 2015; I played through it once and haven't touched it since, for it is a game that I don't want to experience twice.
It started like most other videogames do: By showing me its title shortly before you're allowed to take control over your character and explore the space around you. However Tonight You Die isn't only the game's title. It's the only form of exposition it gave me. Neither did I know who I was, nor why I was walking around a seemingly abandoned city at night. All I knew was that at some point, something will happen that is going to end my existence.
This sense of foreboding, combined with the uncertainty about what exactly it is that was threatening my life, turned what at first appeared to be a simple first person exploration game, into a full on mental assault. I can't say that I actually explored the space that Tonight You Die created for me. To me it felt more like an escape, even though I had no idea where to go. At no point did I feel safe; never did I think that there might be a way for me to release some of the pressure that was constantly building up in my chest.
It's a bit unusual to use the phrase "I was glad when it was over" in a positive context, but I was indeed glad when I was done playing Tonight You Die. From the abstract ugliness of its city, to the constantly growing noise of its soundtrack: It felt like the game didn't want me to exist. The fact that Tonight You Die communicates most of its ideas just by means of sound and space stood out the most for me. It's a great demonstration of how much you can accomplish just with spatial design and it's games like this that make me the most excited about the future of this medium.
Eric Merz spends most of his time making a videogame of his own. In fact, he should finally come up with a name for it. He does have a Twitter account and you can play his games on itch.io. He also occasionally writes about experimental games in German and used to be quite active on YouTube.
Tags: Cities: Skylines, Mini Metro, Off Peak, Tonight You Die, Yakuza 5
← Off The Grid: Inside: Before Birth
The Map is Not The Territory →


text:
O Rio Burdea é um rio da Romênia, afluente do Rio Vedea, localizado nos distritos de Argeş e Teleorman.

Rios da Roménia