# Approximation Theory of Wavelet Frame Based Image Restoration

Jian-Feng Cai111J. F. Cai is supported in part by Hong Kong Research Grants
Council (HKRGC) GRF grants 16309518, 16309219, 16310620, and 16306821, and by
the Project of Hetao Shenzhen-Hong Kong Science and Technology Innovation
Cooperation Zone (HZQB-KCZYB-2020083<EMAIL_ADDRESS>Jae Kyu Choi222J. K. Choi
is supported in part by the National Natural Science Foundation of China
(NSFC) Youth Program 11901436, the Shanghai Science and Technology Committee
20JC1413500, and the Fundamental Research Funds for the Central Universities.
<EMAIL_ADDRESS>Jianbin Yang333J. Yang is supported in part by the
National Natural Science Foundation of China (NSFC) 11771120 and the
Fundamental Research Funds for the Central Universities B200202005.
<EMAIL_ADDRESS>Department of Mathematics, The Hong Kong University of
Science and Technology, Hong Kong  HKUST Shenzhen-Hong Kong Collaborative
Innovation Research Institute, Futian, Shenzhen, China.  School of
Mathematical Sciences, Tongji University, Shanghai, 200092 China  Department
of Mathematics, Hohai University, Nanjing, 211100 China

###### Abstract

In this paper, we analyze the error estimate of a wavelet frame based image
restoration method from degraded and incomplete measurements. We present the
error between the underlying original discrete image and the approximate
solution which has the minimal $\ell_{1}$-norm of the canonical wavelet frame
coefficients among all possible solutions. Then we further connect the error
estimate for the discrete model to the approximation to the underlying
function from which the underlying image comes.

###### keywords:

Tight wavelet frame , framelet , image restoration , incomplete data recovery
, error estimate , $\ell_{1}$ minimization , uniform law of large numbers ,
covering number , asymptotic approximation analysis

##  1 Introduction

In many practical image restoration tasks, observed images or measurements are
often incomplete in the sense that features of interest in an image are
missing partially and/or corrupted by noise. The corresponding inverse problem
is to restore the underlying image ${\boldsymbol{f}}$ from its incomplete
measurements given by

$\displaystyle{\boldsymbol{g}}[{\boldsymbol{k}}]=\left\\{\begin{array}[]{cl}({\boldsymbol{{\mathcal{A}}}}{\boldsymbol{f}})[{\boldsymbol{k}}]+{\boldsymbol{\eta}}[{\boldsymbol{k}}],{}&{\boldsymbol{k}}\in{\boldsymbol{\Lambda}},\vspace{0.5em}\\\
\text{unknown},{}&{\boldsymbol{k}}\in\boldsymbol{\Omega}\setminus{\boldsymbol{\Lambda}}.\end{array}\right.$
(1.3)

In Eq. 1.3, ${\boldsymbol{\eta}}$ is a measurement error which is assumed to
be uncorrelated with
$\left({\boldsymbol{{\mathcal{A}}}}{\boldsymbol{f}}\right)\big{|}_{{\boldsymbol{\Lambda}}}$,
and ${\boldsymbol{{\mathcal{A}}}}$ is some linear operator describing the
process of imaging, acquisition, and communication. As convention, we consider
discrete images as real-valued functions on a two dimensional regular grid
$\boldsymbol{\Omega}\subseteq{\mathbb{Z}}^{2}$, and ${\boldsymbol{\Lambda}}$
is a subset of $\boldsymbol{\Omega}$ where ${\boldsymbol{g}}$ is available or
reliable. Nevertheless, the discussions on other dimensions will be almost the
same with slight modifications. Note that this paper involves both functions
and their discrete counterparts. We shall use regular characters to denote
functions and use bold-faced characters to denote their discrete analogies.
For example, we use $u$ as an element in a function space, while we use
$\boldsymbol{u}$ to denote its corresponding discretized version (the type of
discretization will be made clear later).

The measurements could be part of (degraded) images, transmitted data, and
sensor data. The restoration of missing data from a given incomplete
measurement is an essential part of imaging science area where the final image
is utilized for the visual interpretation or for the automatic analysis [51].
In the literature, numerous methods have been proposed under many different
settings, e.g. [9, 14, 26, 42] for image inpainting, [27, 62, 64, 65] for
wavelet domain inpainting, [44, 45, 52] for compressed sensing MRI
restoration, [28, 36] for sparse view/angle CT restoration, and [19, 25] for
miscellaneous applications. That being said, we forgo to give detailed surveys
on these various applications and the interested reader should consult the
references mentioned above for details. Instead, assuming that

$\displaystyle{\mathcal{E}}\left({\boldsymbol{\eta}}\right)=\frac{1}{|{\boldsymbol{\Lambda}}|}\sum_{{\boldsymbol{k}}\in{\boldsymbol{\Lambda}}}{\boldsymbol{\eta}}[{\boldsymbol{k}}]=0~{}~{}~{}\text{and}~{}~{}~{}\mathrm{Var}\left({\boldsymbol{\eta}}\right)=\frac{1}{|{\boldsymbol{\Lambda}}|}\sum_{{\boldsymbol{k}}\in{\boldsymbol{\Lambda}}}{\boldsymbol{\eta}}[{\boldsymbol{k}}]^{2}=\eta^{2},$
(1.4)

we focus on establishing the approximation analysis of the following wavelet
frame analysis based approach [17, 42, 58]:

$\displaystyle\min_{\boldsymbol{u}\in[0,M]^{\boldsymbol{\Omega}}}\left\|\boldsymbol{\lambda}\cdot{\boldsymbol{{\mathcal{W}}}}\boldsymbol{u}\right\|_{1}~{}~{}~{}\text{subject
to}~{}~{}\frac{1}{|{\boldsymbol{\Lambda}}|}\sum_{{\boldsymbol{k}}\in{\boldsymbol{\Lambda}}}\left|({\boldsymbol{{\mathcal{A}}}}\boldsymbol{u})[{\boldsymbol{k}}]-{\boldsymbol{g}}[{\boldsymbol{k}}]\right|^{2}\leq\eta^{2}.$
(1.5)

In Eq. 1.5, ${\boldsymbol{{\mathcal{W}}}}$ is some wavelet frame transform,
and
$\left\|\boldsymbol{\lambda}\cdot{\boldsymbol{{\mathcal{W}}}}\boldsymbol{u}\right\|_{1}$
is the weighted $\ell_{1}$-norm of the wavelet frame coefficients of
$\boldsymbol{u}$ which promotes the regularity. Since the key features of
image are in general modelled as singularities of piecewise smooth function,
we only consider the images of low regularity throughout this paper. For the
clarity of presentation, the detailed definition and explanation on this
weighted $\ell_{1}$-norm will be postponed until Section 2.

The settings of Eq. 1.3 considered in this paper are as follows:

  1. 1.

$\boldsymbol{\Omega}=\left\\{0,1,\cdots,N-1\right\\}^{2}$, where
$N\in{\mathbb{N}}$,

  2. 2.

${\boldsymbol{\Lambda}}\subsetneq\boldsymbol{\Omega}$,
$|{\boldsymbol{\Lambda}}|=m$, and ${\boldsymbol{\Lambda}}$ is uniformly
randomly chosen from all $m$-subsets of $\boldsymbol{\Omega}$,

  3. 3.

$\sigma_{\min}({\boldsymbol{{\mathcal{A}}}})>0$ and both
$\sigma_{\min}({\boldsymbol{{\mathcal{A}}}})$ and
$\left\|{\boldsymbol{{\mathcal{A}}}}\right\|_{\infty}$ are independent of
$|\boldsymbol{\Omega}|$, where $\sigma_{\min}({\boldsymbol{{\mathcal{A}}}})$
denotes the smallest singular value of ${\boldsymbol{{\mathcal{A}}}}$ and
$\left\|{\boldsymbol{{\mathcal{A}}}}\right\|_{\infty}$ denotes the operator
norm induced by the $\ell_{\infty}$ norm.

We denote by $\rho:=m/|\boldsymbol{\Omega}|$ the density of the pixels
available. In addition, we assume that the operator
${\boldsymbol{{\mathcal{A}}}}$, the measurement ${\boldsymbol{g}}$ and the
error ${\boldsymbol{\eta}}$ are given and fixed, even though
${\boldsymbol{{\mathcal{A}}}}$ and ${\boldsymbol{\eta}}$ can be viewed as
particular realizations of some random variables, e.g. the Gaussian or
Bernoulli sensing matrix for ${\boldsymbol{{\mathcal{A}}}}$ and the i.i.d.
white Gaussian noise for ${\boldsymbol{\eta}}$. Hence, the only random
variable we consider is the data set ${\boldsymbol{\Lambda}}$ which is
uniformly randomly drawn from all $m$-subsets of $\boldsymbol{\Omega}$.
Related examples include the wavelet inpainting [27, 62, 64, 65] to restore an
image from a degraded and randomly missed data due to the unreliable
transmission channel, the simultaneous deblurring and inpainting due to e.g.
simultaneous out-of-focusing (or camera shaking) and dust spots or cracks in
film [47], and the image restoration in the presence of Gaussian and impulsive
noise [5, 6, 11, 12, 13, 25, 47, 51], etc.

Obviously, Eq. 1.5 takes the wavelet frame based image inpainting
(${\boldsymbol{{\mathcal{A}}}}={\boldsymbol{{\mathcal{I}}}}$ being the
identity operator) whose approximation property is studied in [18] as a
special case. Thus, our goal is to extend the approximation analysis in [18]
to the generic image restoration tasks Eq. 1.3. To begin with, we assume that
${\boldsymbol{f}}\in[0,M]^{\boldsymbol{\Omega}}$ and
$\left\|\boldsymbol{\lambda}\cdot{\boldsymbol{{\mathcal{W}}}}{\boldsymbol{f}}\right\|_{1}<\infty$.
The first condition enforces the range of pixel values on ${\boldsymbol{f}}$,
which is typically set to be $M=255$ for the grayscale images, and the second
condition enforces some regularity on ${\boldsymbol{f}}$. Let
$\boldsymbol{u}^{{\boldsymbol{\Lambda}}}$ be the solution to Eq. 1.5, which is
possible as Eq. 1.5 admits at least one solution with the minimal weighted
$\ell_{1}$-norm of wavelet frame coefficients subject to the constraint [4].
For $\rho=1$, we have

$\displaystyle\frac{1}{|\boldsymbol{\Omega}|}\left\|\boldsymbol{u}^{{\boldsymbol{\Lambda}}}-{\boldsymbol{f}}\right\|_{\ell_{2}(\boldsymbol{\Omega})}^{2}\leq\frac{2\sigma_{\min}^{-2}({\boldsymbol{{\mathcal{A}}}})}{|\boldsymbol{\Omega}|}\left(\left\|{\boldsymbol{{\mathcal{A}}}}\boldsymbol{u}^{{\boldsymbol{\Lambda}}}-{\boldsymbol{g}}\right\|_{\ell_{2}(\boldsymbol{\Omega})}^{2}+\left\|{\boldsymbol{g}}-{\boldsymbol{{\mathcal{A}}}}{\boldsymbol{f}}\right\|_{\ell_{2}(\boldsymbol{\Omega})}^{2}\right)\leq
4\sigma_{\min}^{-2}({\boldsymbol{{\mathcal{A}}}})\eta^{2},$

which means that if $\rho=1$ and $\eta=0$, the unique solution to Eq. 1.5 is
the original image ${\boldsymbol{f}}$. Hence, we aim to focus on analyzing
what happens when $\rho<1$ and $\eta>0$. More precisely, we will show that,
under some mild assumptions, the following inequality

$\displaystyle\frac{1}{|\boldsymbol{\Omega}|}\left\|\boldsymbol{u}^{{\boldsymbol{\Lambda}}}-{\boldsymbol{f}}\right\|_{\ell_{2}(\boldsymbol{\Omega})}^{2}\leq
C_{1}\rho^{-1/2}|\boldsymbol{\Omega}|^{-\gamma}\left(\log_{2}|\boldsymbol{\Omega}|\right)^{3/2}+C_{2}\eta^{2}$
(1.6)

holds with probability at least $1-|\boldsymbol{\Omega}|^{-1}$. In Eq. 1.6,
$\gamma$ is a positive constant related to the regularity of
${\boldsymbol{f}}$, and $C_{1}$ and $C_{2}$ are constants independent of
$|\boldsymbol{\Omega}|$, $\rho$, and $\eta$. Briefly speaking, as long as the
data set is sufficiently large, one has a pretty good chance to restore
${\boldsymbol{f}}$ by solving Eq. 1.5.

In the literature, there are efficient numerical algorithms developed to solve
Eq. 1.5 with a guaranteed convergence to minimizer [17, 34, 47]. These
numerical algorithms aim to find a sparse approximation of the underlying
image using a properly chosen wavelet frame transform. Then a sparsity
promoting regularization term (such as the widely used $\ell_{1}$-norm) is
used to regularizing smooth image components while preserving image
singularities such as edges and ridges. Hence, one may consider the
approximation analysis of the numerical algorithms in the context of
compressed sensing (CS) (e.g. [19, 20, 21, 41]). However, we would like to
mention that our setting of Eq. 1.5 is different from that of CS. First of
all, we only assume the decay of wavelet frame coefficients
${\boldsymbol{{\mathcal{W}}}}{\boldsymbol{f}}$ in the sense that
$\left\|\boldsymbol{\lambda}\cdot{\boldsymbol{{\mathcal{W}}}}{\boldsymbol{f}}\right\|_{1}$
is bounded rather than the explicit sparsity of ${\boldsymbol{f}}$ and/or
${\boldsymbol{{\mathcal{W}}}}{\boldsymbol{f}}$, so that we can impose a low
regularity assumption on ${\boldsymbol{f}}$. Second and most importantly, the
“sensing matrix” of Eq. 1.3 does not satisfy the conditions required for the
theoretical analysis of CS. In our setting, the sensing matrix is
${\boldsymbol{{\mathcal{R}}}}_{{\boldsymbol{\Lambda}}}{\boldsymbol{{\mathcal{A}}}}$,
where ${\boldsymbol{{\mathcal{R}}}}_{{\boldsymbol{\Lambda}}}$ denotes the
projection onto ${\boldsymbol{\Lambda}}$;
${\boldsymbol{{\mathcal{R}}}}_{{\boldsymbol{\Lambda}}}{\boldsymbol{f}}[{\boldsymbol{k}}]={\boldsymbol{f}}[{\boldsymbol{k}}]$
for ${\boldsymbol{k}}\in{\boldsymbol{\Lambda}}$, and
${\boldsymbol{{\mathcal{R}}}}_{{\boldsymbol{\Lambda}}}{\boldsymbol{f}}[{\boldsymbol{k}}]=0$
for ${\boldsymbol{k}}\in\boldsymbol{\Omega}\setminus{\boldsymbol{\Lambda}}$.
Since ${\boldsymbol{\Lambda}}$ is randomly chosen from all $m$-subsets of
$\boldsymbol{\Omega}$ with a given fixed $m$,
${\boldsymbol{{\mathcal{R}}}}_{{\boldsymbol{\Lambda}}}$ does not satisfy the
concentration inequality in [54], and
${\boldsymbol{{\mathcal{R}}}}_{{\boldsymbol{\Lambda}}}{\boldsymbol{{\mathcal{A}}}}$
may not satisfy the restricted isometry property condition in general, all of
which mean that there may not be information in the measurement
${\boldsymbol{g}}$ sufficient for the exact restoration [18]. Instead, the
main tools are the uniform law of large numbers and an estimation of covering
number [29] of the hypothesis space, which are widely used in classical
empirical process [59] and statistical learning theory [60]. We further
mention that our error analysis uses the newly involved estimation for
covering number. More precisely, even though we also use the special structure
of the set and the max-flow min-cut theorem in graph theory to estimate
covering number, we improve the estimate in [18, Theorem 2.4] by relaxing the
constraint on the radius in the covering number.

As a byproduct of the approximation analysis, we can further connect the
approximation property of Eq. 1.5 to the asymptotic approximation to the
underlying function in terms of the shift invariant space generated by a
scaled compactly supported basis function. Such an asymptotic approximation is
extensively studied in terms of the Strang-Fix condition [31, 40, 49, 63].
Notice that these asymptotic approximations require a certain order of
regularity of underlying function in terms of e.g. the Sobolev space [2], even
in the case of $\ell_{1}$ minimization approach in [40, 63]. Meanwhile, our
asymptotic approximation uses the decay condition of wavelet frame
coefficients of underlying function and the Bessel property of the shifts of
scaled basis function only, as an extension of [18] for the wavelet frame
based image inpainting to the generic image restoration tasks.

The rest of this paper is organized as follows. The explicit formulation of
Eq. 1.6 is presented in Section 2. More precisely, we begin with introducing
basic preliminaries of wavelet frames in Section 2.1. The error estimates for
Eq. 1.5 in the discrete setting is given in Section 2.2, and in Section 2.3,
we further establish the connection to function approximations in terms of the
multiresolution approximation. Finally, all technical details are presented in
Section 3, and Section 4 concludes this paper with relevant future works.

##  2 Approximation error of wavelet frame based image restoration

###  2.1 Preliminaries of wavelet frames

We begin with a brief introduction on wavelet tight frames. For details, one
may consult [30, 31, 55] for theories of frames and wavelet frames, [57] for a
short survey on the theory and applications of frames, and [37, 38] for more
detailed surveys.

A countable set $\left\\{\varphi_{n}:n\in{\mathbb{Z}}\right\\}\subseteq
L_{2}({\mathbb{R}}^{d})$ with $d\in{\mathbb{N}}$ is called a tight frame of
$L_{2}({\mathbb{R}}^{d})$ if

$\displaystyle\left\|f\right\|_{L_{2}({\mathbb{R}}^{d})}^{2}=\sum_{n\in{\mathbb{Z}}}\left|\left\langle
f,\varphi_{n}\right\rangle\right|^{2}~{}~{}~{}~{}~{}\text{for
all}~{}~{}~{}f\in L_{2}({\mathbb{R}}^{d}),$ (2.1)

where $\langle\cdot,\cdot\rangle$ is the inner product on
$L_{2}({\mathbb{R}}^{d})$, and $\langle f,\varphi_{n}\rangle$ is called the
canonical coefficient of $f$.

For given
${\boldsymbol{\Psi}}=\left\\{\psi_{1},\cdots,\psi_{r}\right\\}\subseteq
L_{2}({\mathbb{R}}^{d})$ and $J\in{\mathbb{N}}$, the corresponding quasi-
affine system ${\mathscr{X}}^{J}({\boldsymbol{\Psi}})$ generated by
${\boldsymbol{\Psi}}$ is defined by the collection of the dilations and the
shifts of the elements in ${\boldsymbol{\Psi}}$:

$\displaystyle{\mathscr{X}}^{J}({\boldsymbol{\Psi}})=\left\\{\psi_{\alpha,l,{\boldsymbol{k}}}:1\leq\alpha\leq
r,~{}l\in{\mathbb{Z}},~{}{\boldsymbol{k}}\in{\mathbb{Z}}^{d}\right\\}$ (2.2)

with $\psi_{\alpha,l,{\boldsymbol{k}}}$ being defined as

$\displaystyle\psi_{\alpha,l,{\boldsymbol{k}}}=\left\\{\begin{array}[]{cl}2^{\frac{ld}{2}}\psi_{\alpha}(2^{l}\cdot-{\boldsymbol{k}}){}{}&~{}~{}l\geq
J;\vspace{0.5em}\\\
2^{\left(l-\frac{J}{2}\right)d}\psi_{\alpha}(2^{l}\cdot-2^{l-J}{\boldsymbol{k}}){}{}&~{}~{}l<J.\end{array}\right.$
(2.5)

When ${\mathscr{X}}^{J}({\boldsymbol{\Psi}})$ forms a tight frame of
$L_{2}({\mathbb{R}}^{d})$, each $\psi_{1},\cdots,\psi_{r}$ is called a (tight)
framelet and the entire system ${\mathscr{X}}^{J}({\boldsymbol{\Psi}})$ is
called a (tight) wavelet frame. In particular when $J=0$, we simply write
${\mathscr{X}}({\boldsymbol{\Psi}})={\mathscr{X}}^{0}({\boldsymbol{\Psi}})$.
Note that in the literature, the affine system is widely used, which
corresponds to the decimate wavelet (frame) transform. The quasi-affine
system, which corresponds to the undecimated wavelet (frame) transformation,
was first introduced and analyzed in [55]. Throughout this paper, we only
discuss the quasi-affine system Eq. 2.5 because it generally performs better
in image restoration than the widely used affine system, and the connection to
the underlying function in continuum is more natural [15, 16, 39]. The
interested reader can find further details on the affine wavelet frame systems
and its connections to the quasi-affine wavelet frame systems in [23, 37, 55].

The constructions of framelets ${\boldsymbol{\Psi}}$, which are desirably
(anti-)symmetric and compactly supported functions, are usually based on a
multiresolution analysis (MRA) generated by some refinable function $\phi$
with a refinement mask ${\boldsymbol{a}}_{0}$ such that

$\displaystyle\phi=2^{d}\sum_{{\boldsymbol{k}}\in{\mathbb{Z}}^{d}}{\boldsymbol{a}}_{0}[{\boldsymbol{k}}]\phi(2\cdot-{\boldsymbol{k}}).$
(2.6)

The idea of an MRA based construction of
${\boldsymbol{\Psi}}=\left\\{\psi_{1},\cdots,\psi_{r}\right\\}\subseteq
L_{2}({\mathbb{R}}^{d})$ is to find finitely supported masks
${\boldsymbol{a}}_{l}$ such that

$\displaystyle\psi_{\alpha}=2^{d}\sum_{{\boldsymbol{k}}\in{\mathbb{Z}}^{d}}{\boldsymbol{a}}_{\alpha}[{\boldsymbol{k}}]\phi(2\cdot-{\boldsymbol{k}})~{}~{}~{}~{}~{}\alpha=1,\cdots,r.$
(2.7)

The sequences ${\boldsymbol{a}}_{1},\cdots,{\boldsymbol{a}}_{r}$ are called
wavelet frame mask or the high pass filters of the system, and the refinement
mask ${\boldsymbol{a}}_{0}$ is also called the low-pass filter.

The unitary extension principle (UEP) of [55] provides a general theory of the
construction of MRA based tight wavelet frames. Briefly speaking, as long as
$\left\\{{\boldsymbol{a}}_{0},{\boldsymbol{a}}_{1},\cdots,{\boldsymbol{a}}_{r}\right\\}$
are compactly supported and their Fourier series

$\displaystyle\widehat{{\boldsymbol{a}}}_{\alpha}({\boldsymbol{\xi}})=\sum_{{\boldsymbol{k}}\in{\mathbb{Z}}^{d}}{\boldsymbol{a}}_{\alpha}[{\boldsymbol{k}}]e^{-i{\boldsymbol{\xi}}\cdot{\boldsymbol{k}}},~{}~{}~{}~{}~{}~{}\alpha=0,\cdots,r,~{}~{}~{}{\boldsymbol{\xi}}\in{\mathbb{R}}^{d}$

satisfy

$\displaystyle\sum_{\alpha=0}^{r}\left|\widehat{{\boldsymbol{a}}}_{\alpha}({\boldsymbol{\xi}})\right|^{2}=1~{}~{}~{}~{}\text{and}~{}~{}~{}~{}\sum_{\alpha=0}^{r}\widehat{{\boldsymbol{a}}}_{\alpha}({\boldsymbol{\xi}})\overline{\widehat{{\boldsymbol{a}}}}_{\alpha}({\boldsymbol{\xi}}+\boldsymbol{\nu})=0$
(2.8)

for all
$\boldsymbol{\nu}\in\left\\{0,\pi\right\\}^{d}\setminus\left\\{{\mathbf{0}}\right\\}$
and ${\boldsymbol{\xi}}\in[-\pi,\pi]^{d}$, the quasi-affine system
${\mathscr{X}}({\boldsymbol{\Psi}})$ with
${\boldsymbol{\Psi}}=\left\\{\psi_{1},\cdots,\psi_{r}\right\\}$ defined by Eq.
2.7 forms a tight frame of $L_{2}({\mathbb{R}}^{d})$, and the filters
$\left\\{{\boldsymbol{a}}_{0},{\boldsymbol{a}}_{1},\cdots,{\boldsymbol{a}}_{r}\right\\}$
form a discrete tight frame on $\ell_{2}({\mathbb{Z}}^{d})$ [37].

One of the most widely used examples is the piecewise linear B-spline [31] for
$L_{2}({\mathbb{R}})$, which has one refinable function and two framelets with
the associated filters

$\displaystyle{\boldsymbol{a}}_{0}=\frac{1}{4}\big{[}\begin{array}[]{ccc}1&2&1\end{array}\big{]},~{}~{}~{}~{}{\boldsymbol{a}}_{1}=\frac{\sqrt{2}}{4}\big{[}\begin{array}[]{ccc}1&0&-1\end{array}\big{]},~{}~{}\text{and}~{}~{}{\boldsymbol{a}}_{2}=\frac{1}{4}\big{[}\begin{array}[]{ccc}-1&2&-1\end{array}\big{]}.$

Indeed, it can be shown that the above
$\left\\{{\boldsymbol{a}}_{0},{\boldsymbol{a}}_{1},{\boldsymbol{a}}_{2}\right\\}$
satisfies Eq. 2.8, so that ${\mathscr{X}}({\boldsymbol{\Psi}})$ with
${\boldsymbol{\Psi}}=\left\\{\psi_{1},\psi_{2}\right\\}$ defined by Eq. 2.7
forms a tight frame on $L_{2}({\mathbb{R}})$.

One possible way to construct a tight frame on $L_{2}({\mathbb{R}}^{2})$ is by
taking tensor products of univariate tight framelets [15, 16, 30, 37]. Given a
set of univariate masks
$\big{\\{}{\boldsymbol{a}}_{0},{\boldsymbol{a}}_{1},\cdots,{\boldsymbol{a}}_{r}\big{\\}}$,
we define two dimensional masks
${\boldsymbol{a}}_{\boldsymbol{\alpha}}[{\boldsymbol{k}}]$ with
$\boldsymbol{\alpha}=(\alpha_{1},\alpha_{2})$ and
${\boldsymbol{k}}=(k_{1},k_{2})$ as

$\displaystyle{\boldsymbol{a}}_{\boldsymbol{\alpha}}[{\boldsymbol{k}}]={\boldsymbol{a}}_{\alpha_{1}}[k_{1}]{\boldsymbol{a}}_{\alpha_{2}}[k_{2}],~{}~{}~{}~{}~{}~{}0\leq\alpha_{1},\alpha_{2}\leq
r,~{}~{}{\boldsymbol{k}}=(k_{1},k_{2})\in{\mathbb{Z}}^{2}$

so that the corresponding two dimensional refinable function and framelets are
defined as

$\displaystyle\psi_{\boldsymbol{\alpha}}(\boldsymbol{x})=\psi_{\alpha_{1}}(x_{1})\psi_{\alpha_{2}}(x_{2}),~{}~{}~{}~{}~{}0\leq\alpha_{1},\alpha_{2}\leq
r,~{}~{}\boldsymbol{x}=(x_{1},x_{2})\in{\mathbb{R}}^{2}$

with $\psi_{0}=\phi$ for convenience. If the univariate masks
$\left\\{{\boldsymbol{a}}_{l}:l=0,\cdots,r\right\\}$ are constructed from UEP,
then it can be verified that
$\left\\{{\boldsymbol{a}}_{\boldsymbol{\alpha}}:\boldsymbol{\alpha}\in\\{0,\cdots,r\\}^{2}\right\\}$
satisfies Eq. 2.8 and thus ${\mathscr{X}}({\boldsymbol{\Psi}})$ with

$\displaystyle{\boldsymbol{\Psi}}=\left\\{\psi_{\boldsymbol{\alpha}}:\boldsymbol{\alpha}\in\\{0,\cdots,r\\}^{2}\setminus\\{{\mathbf{0}}\\}\right\\}$

forms a tight frame for $L_{2}({\mathbb{R}}^{2})$.

The advantage of framelet is that we can easily derive the discrete tight
frame system by framelet decomposition and reconstruction algorithms of [31].
Throughout this paper, we only consider the MRA based tensor product wavelet
frame system on $\ell_{2}(\boldsymbol{\Omega})$ with
$\boldsymbol{\Omega}=\left\\{0,\cdots,N-1\right\\}^{2}$ for simplicity. For
$l\geq 0$ we construct filters ${\boldsymbol{a}}_{l,\boldsymbol{\alpha}}$ by

$\displaystyle{\boldsymbol{a}}_{l,\boldsymbol{\alpha}}=\widetilde{{\boldsymbol{a}}}_{l,\boldsymbol{\alpha}}\ast\widetilde{{\boldsymbol{a}}}_{l-1,{\mathbf{0}}}\ast\cdots\ast\widetilde{{\boldsymbol{a}}}_{0,{\mathbf{0}}}~{}~{}\text{with}~{}~{}\widetilde{{\boldsymbol{a}}}_{l,\boldsymbol{\alpha}}[{\boldsymbol{k}}]=\left\\{\begin{array}[]{cl}{\boldsymbol{a}}_{\boldsymbol{\alpha}}[2^{-l}{\boldsymbol{k}}],&{\boldsymbol{k}}\in
2^{l}{\mathbb{Z}}^{2};\vspace{0.5em}\\\ 0,&{\boldsymbol{k}}\notin
2^{l}{\mathbb{Z}}^{2},\end{array}\right.$ (2.11)

where
${\boldsymbol{a}}_{0,\boldsymbol{\alpha}}={\boldsymbol{a}}_{\boldsymbol{\alpha}}$,
and $\ast$ denotes the standard discrete convolution on ${\mathbb{Z}}^{2}$.

Let $\boldsymbol{u}\in\ell_{2}(\boldsymbol{\Omega})$. To define an appropriate
discrete framelet transform, or an analysis operator (see, e.g., [37]), we
will impose the periodic boundary conditions. Throughout this paper, we
identify $\ell_{p}(\boldsymbol{\Omega})$ with the space of $\ell_{p}$
sequences on ${\mathbb{Z}}^{2}$ with fundamental period on each variable to be
$N$. We introduce the following periodization operator
${\boldsymbol{{\mathcal{P}}}}_{J}:\ell_{1}({\mathbb{Z}}^{2})\to\ell_{1}(\boldsymbol{\Omega})$:

$\displaystyle{\boldsymbol{{\mathcal{P}}}}_{N}\left(\boldsymbol{u}\right)[{\boldsymbol{k}}]=\sum_{{\boldsymbol{k}}^{\prime}\in{\mathbb{Z}}^{2}}\boldsymbol{u}[{\boldsymbol{k}}+N{\boldsymbol{k}}^{\prime}]~{}~{}~{}~{}~{}~{}~{}{\boldsymbol{k}}\in\boldsymbol{\Omega}.$

Then for ${\boldsymbol{a}}\in\ell_{1}({\mathbb{Z}}^{2})$ and
$\boldsymbol{u}\in\ell_{2}(\boldsymbol{\Omega})$, we define the convolution
${\boldsymbol{a}}\circledast\boldsymbol{u}$ as

$\displaystyle\left({\boldsymbol{a}}\circledast\boldsymbol{u}\right)[{\boldsymbol{k}}]=\left\langle{\boldsymbol{{\mathcal{P}}}}_{N}({\boldsymbol{a}})[{\boldsymbol{k}}-\cdot],\boldsymbol{u}\right\rangle=\sum_{\boldsymbol{n}\in\boldsymbol{\Omega}}{\boldsymbol{{\mathcal{P}}}}_{N}\left({\boldsymbol{a}}\right)[{\boldsymbol{k}}-\boldsymbol{n}]\boldsymbol{u}[\boldsymbol{n}],~{}~{}~{}~{}~{}{\boldsymbol{k}}\in\boldsymbol{\Omega}.$
(2.12)

Using the filters defined as Eq. 2.11, we define the two dimensional fast
(discrete) framelet transform, or the analysis operator (see, e.g., [37]) with
$L$ levels of decomposition as

$\displaystyle{\boldsymbol{{\mathcal{W}}}}\boldsymbol{u}=\big{\\{}{\boldsymbol{{\mathcal{W}}}}_{l,\boldsymbol{\alpha}}\boldsymbol{u}:(l,\boldsymbol{\alpha})\in\big{(}\left\\{0,\cdots,L-1\right\\}\times{\mathbb{B}}\big{)}\cup\left\\{(L-1,{\mathbf{0}})\right\\}\big{\\}}.$
(2.13)

where
${\mathbb{B}}=\left\\{0,\cdots,r\right\\}^{2}\setminus\left\\{{\mathbf{0}}\right\\}$
is the framelet band. Then ${\boldsymbol{{\mathcal{W}}}}$ is a linear operator
with the frame coefficients
${\boldsymbol{{\mathcal{W}}}}_{l,\boldsymbol{\alpha}}\boldsymbol{u}\in\ell_{2}(\boldsymbol{\Omega})$
of $\boldsymbol{u}$ at level $l$ and band $\boldsymbol{\alpha}$ being defined
as

$\displaystyle{\boldsymbol{{\mathcal{W}}}}_{l,\boldsymbol{\alpha}}\boldsymbol{u}={\boldsymbol{a}}_{l,\boldsymbol{\alpha}}[-\cdot]\circledast\boldsymbol{u},$

where the discrete convolution $\circledast$ is defined as Eq. 2.12. The
synthesis framelet transform is denoted as ${\boldsymbol{{\mathcal{W}}}}^{T}$,
the adjoint of ${\boldsymbol{{\mathcal{W}}}}$. Since we use a tight wavelet
frame, we have the following perfect reconstruction formula

$\displaystyle\boldsymbol{u}={\boldsymbol{{\mathcal{W}}}}^{T}{\boldsymbol{{\mathcal{W}}}}\boldsymbol{u}$
(2.14)

for all $\boldsymbol{u}\in\ell_{2}(\boldsymbol{\Omega})$.

Finally, using this analysis operator ${\boldsymbol{{\mathcal{W}}}}$, we
define
$\left\|\boldsymbol{\lambda}\cdot{\boldsymbol{{\mathcal{W}}}}\boldsymbol{u}\right\|_{1}$
by

$\displaystyle\left\|\boldsymbol{\lambda}\cdot{\boldsymbol{{\mathcal{W}}}}\boldsymbol{u}\right\|_{1}=\sum_{{\boldsymbol{k}}\in\boldsymbol{\Omega}}\sum_{l=0}^{L-1}\sum_{\boldsymbol{\alpha}\in{\mathbb{B}}}\lambda_{l,\boldsymbol{\alpha}}[{\boldsymbol{k}}]\left|\big{(}{\boldsymbol{{\mathcal{W}}}}_{l,\boldsymbol{\alpha}}\boldsymbol{u}\big{)}[{\boldsymbol{k}}]\right|.$
(2.15)

In particular, if $\lambda_{l,\boldsymbol{\alpha}}[{\boldsymbol{k}}]=1$ for
all $(l,\boldsymbol{\alpha},{\boldsymbol{k}})$, we simply write it as
$\left\|{\boldsymbol{{\mathcal{W}}}}\boldsymbol{u}\right\|_{1}$:

$\displaystyle\left\|{\boldsymbol{{\mathcal{W}}}}\boldsymbol{u}\right\|_{1}=\sum_{{\boldsymbol{k}}\in\boldsymbol{\Omega}}\sum_{l=0}^{L-1}\sum_{\boldsymbol{\alpha}\in{\mathbb{B}}}\left|\big{(}{\boldsymbol{{\mathcal{W}}}}_{l,\boldsymbol{\alpha}}\boldsymbol{u}\big{)}[{\boldsymbol{k}}]\right|.$
(2.16)

As we shall see later, the parameter $\boldsymbol{\lambda}$ in Eq. 2.15 is
related to the decay of wavelet frame coefficients, thereby to control the
regularity of $\boldsymbol{u}$.

###  2.2 Error analysis of discrete model Eq. 1.5

Throughout the rest of this paper, we denote
${\boldsymbol{\Psi}}=\\{\psi_{\boldsymbol{\alpha}}:\boldsymbol{\alpha}\in{\mathbb{B}}\\}$
as the set of framelets, $\phi$ (or $\psi_{{\mathbf{0}}}$) as the
corresponding refinable function, and
$\\{{\boldsymbol{a}}_{\boldsymbol{\alpha}}:\boldsymbol{\alpha}\in{\mathbb{B}}\cup\left\\{{\mathbf{0}}\right\\}\\}$
as the associated filters. In this paper, we focus on the tensor product
B-spline wavelet frame systems constructed by [55], and $\phi$ is a tensor
product B-spline function. We shall refer to $\psi_{\boldsymbol{\alpha}}$ for
$\boldsymbol{\alpha}\in{\mathbb{B}}$ as the tensor product framelets. Note,
however, that the analysis can be generalized to the generic MRA based wavelet
frame systems whenever the corresponding refinable function is compactly
supported with
$\int_{{\mathbb{R}}^{2}}\phi(\boldsymbol{x}){\mathrm{d}}\boldsymbol{x}=1$,
Lipschitz continuous, and forms a Riesz basis on the closed shift invariant
space
$\bigvee\left\\{\phi(\cdot-{\boldsymbol{k}}):{\boldsymbol{k}}\in{\mathbb{Z}}^{2}\right\\}$
[18].

Let $\boldsymbol{u}^{{\boldsymbol{\Lambda}}}$ be a solution to Eq. 1.5 with
the weighted $\ell_{1}$-norm of wavelet frame coefficients defined as Eq.
2.15. Recall that $\boldsymbol{\Omega}=\left\\{0,1,\cdots,N-1\right\\}^{2}$
and ${\boldsymbol{\Lambda}}$ is a data set uniformly randomly drawn from all
$m$-subsets of $\boldsymbol{\Omega}$. Denote by $\rho=m/|\boldsymbol{\Omega}|$
the density of the pixels available. To draw an error between
$\boldsymbol{u}^{{\boldsymbol{\Lambda}}}$ and the underlying image
${\boldsymbol{f}}$, we assume that the linear operator
${\boldsymbol{{\mathcal{A}}}}$, and the parameter
$\boldsymbol{\lambda}:=\left\\{\lambda_{l,\boldsymbol{\alpha}}[{\boldsymbol{k}}]:l=0,\cdots,L-1,~{}\boldsymbol{\alpha}\in{\mathbb{B}},~{}{\boldsymbol{k}}\in\boldsymbol{\Omega}\right\\}$
satisfy the followings:

  1. A1.

$\sigma_{\min}({\boldsymbol{{\mathcal{A}}}})>0$, and both
$\sigma_{\min}({\boldsymbol{{\mathcal{A}}}})$ and
$\left\|{\boldsymbol{{\mathcal{A}}}}\right\|_{\infty}$ are independent of
$|\boldsymbol{\Omega}|$, i.e. independent of $N$.

  2. A2.

$\boldsymbol{\lambda}=\left\\{\lambda_{l,\boldsymbol{\alpha}}[{\boldsymbol{k}}]:l=0,\cdots,L-1,~{}\boldsymbol{\alpha}\in{\mathbb{B}},~{}{\boldsymbol{k}}\in\boldsymbol{\Omega}\right\\}$
satisfies
$\lambda_{l,\boldsymbol{\alpha}}[{\boldsymbol{k}}]=2^{\beta\Upsilon(l,\boldsymbol{\alpha},{\boldsymbol{k}})}$
where $\beta\geq-1$ and $\Upsilon:\Gamma\to{\mathbb{N}}$ is a positive
integer-valued funciton such that

$\displaystyle\max\left\\{\Upsilon(l,\boldsymbol{\alpha},{\boldsymbol{k}}):(l,\boldsymbol{\alpha},{\boldsymbol{k}})\in\Gamma\right\\}\leq\frac{1}{2}\log_{2}|\boldsymbol{\Omega}|$
(2.17)

with
$\Gamma=\left\\{(l,\boldsymbol{\alpha},{\boldsymbol{k}}):l=0,\cdots,L-1,~{}\boldsymbol{\alpha}\in{\mathbb{B}},~{}{\boldsymbol{k}}\in\boldsymbol{\Omega}\right\\}$.

######  Example 2.1.

Before we continue, we present some examples related to A1.

  1. 1.

Image inpainting: in this case, we have
${\boldsymbol{{\mathcal{A}}}}={\boldsymbol{{\mathcal{I}}}}$, i.e.
$\sigma_{\min}\left({\boldsymbol{{\mathcal{I}}}}\right)=\left\|{\boldsymbol{{\mathcal{I}}}}\right\|_{\infty}=1$.

  2. 2.

Simultaneous Gaussian deblurring and image inpainting: let
${\boldsymbol{{\mathcal{A}}}}\boldsymbol{u}={\boldsymbol{a}}\circledast\boldsymbol{u}$
where ${\boldsymbol{a}}$ is defined as

$\displaystyle{\boldsymbol{a}}[{\boldsymbol{k}}]=\frac{C}{2\pi\sigma^{2}}\exp\left\\{-\frac{\left|{\boldsymbol{k}}\right|^{2}}{2\sigma^{2}}\right\\},~{}~{}~{}~{}~{}{\boldsymbol{k}}\in{\mathbb{Z}}^{2},$

for $\sigma>0$ and a normalizing constant $C>0$ is such that
$\left\|{\boldsymbol{a}}\right\|_{\ell_{1}({\mathbb{Z}}^{2})}=1$. Obviously,
we have
$\left\|{\boldsymbol{{\mathcal{A}}}}\right\|_{\infty}=\left\|{\boldsymbol{a}}\right\|_{\ell_{1}({\mathbb{Z}}^{2})}=1$.
In addition, by Poisson summation formula (e.g. [53]), we have

$\displaystyle\widehat{{\boldsymbol{a}}}(\boldsymbol{\omega})=C\sum_{\boldsymbol{\omega}^{\prime}\in{\mathbb{Z}}^{2}}\exp\left\\{-\frac{\sigma^{2}\left|\boldsymbol{\omega}-2\pi\boldsymbol{\omega}^{\prime}\right|^{2}}{2}\right\\}\geq
C\exp\left\\{-\sigma^{2}\pi^{2}\right\\},~{}~{}~{}\boldsymbol{\omega}\in[-\pi,\pi]^{2}.$

Hence, we can set
$\sigma_{\min}\left({\boldsymbol{{\mathcal{A}}}}\right)=C\exp\left\\{-\sigma^{2}\pi^{2}\right\\}>0$,
which is independent of $|\boldsymbol{\Omega}|$.

  3. 3.

Wavelet inpainting: let ${\boldsymbol{{\mathcal{A}}}}$ be a two dimensional
orthonormal wavelet basis transform
(${\boldsymbol{{\mathcal{A}}}}^{T}{\boldsymbol{{\mathcal{A}}}}={\boldsymbol{{\mathcal{A}}}}{\boldsymbol{{\mathcal{A}}}}^{T}={\boldsymbol{{\mathcal{I}}}}$)
with filter banks
$\left\\{{\boldsymbol{h}}_{\boldsymbol{\beta}}:\boldsymbol{\beta}\in\left\\{0,1\right\\}^{2}\right\\}$
generated by the tensor product of a real-valued univariate conjugate mirror
filter ${\boldsymbol{h}}$:

$\displaystyle{\boldsymbol{h}}_{\boldsymbol{\beta}}[{\boldsymbol{k}}]={\boldsymbol{h}}_{\beta_{1}}[k_{1}]{\boldsymbol{h}}_{\beta_{2}}[k_{2}],~{}~{}~{}~{}~{}{\boldsymbol{k}}\in{\mathbb{Z}}^{2},~{}~{}~{}\boldsymbol{\beta}=(\beta_{1},\beta_{2})\in\left\\{0,1\right\\}^{2}$

with ${\boldsymbol{h}}_{0}={\boldsymbol{h}}$ and
${\boldsymbol{h}}_{1}[k]=(-1)^{1-k}{\boldsymbol{h}}[1-k]$. Then
$\left\|{\boldsymbol{{\mathcal{A}}}}\right\|_{\infty}=\left\|{\boldsymbol{h}}\right\|_{\ell_{1}({\mathbb{Z}})}^{2}$
and
$\sigma_{\min}\left({\boldsymbol{{\mathcal{A}}}}\right)=\sigma_{\max}\left({\boldsymbol{{\mathcal{A}}}}\right)=1$.

######  Remark 2.2.

Together with the assumption on ${\boldsymbol{f}}$ that
$\left\|\boldsymbol{\lambda}\cdot{\boldsymbol{{\mathcal{W}}}}{\boldsymbol{f}}\right\|_{1}<\infty$,
A2 is related to the decay of the canonical wavelet frame coefficients
${\boldsymbol{{\mathcal{W}}}}{\boldsymbol{f}}$. Notice that the decay of
${\boldsymbol{{\mathcal{W}}}}{\boldsymbol{f}}$ is further related to the
regularity of ${\boldsymbol{f}}$, which will be clearer in the context of
asymptotic function approximation. See Section 2.3 for details.

Under the above assumptions, we note that the underlying true image
${\boldsymbol{f}}$ satisfies the constraints in Eq. 1.5 with
$\left\|\boldsymbol{\lambda}\cdot{\boldsymbol{{\mathcal{W}}}}{\boldsymbol{f}}\right\|_{1}<\infty$.
In addition, since $\boldsymbol{u}^{{\boldsymbol{\Lambda}}}$ is a solution to
Eq. 1.5, its weighted $\ell_{1}$-norm
$\left\|\boldsymbol{\lambda}\cdot{\boldsymbol{{\mathcal{W}}}}\boldsymbol{u}^{{\boldsymbol{\Lambda}}}\right\|_{1}$
attains the minimum subject to the constraints, and in particular,
$\left\|\boldsymbol{\lambda}\cdot{\boldsymbol{{\mathcal{W}}}}\boldsymbol{u}^{{\boldsymbol{\Lambda}}}\right\|_{1}\leq\left\|\boldsymbol{\lambda}\cdot{\boldsymbol{{\mathcal{W}}}}{\boldsymbol{f}}\right\|_{1}$.
This leads us to consider the following set

$\displaystyle{\mathscr{M}}=\left\\{\boldsymbol{u}\in\ell_{\infty}(\boldsymbol{\Omega}):\left\|\boldsymbol{\lambda}\cdot{\boldsymbol{{\mathcal{W}}}}\boldsymbol{u}\right\|_{1}\leq\left\|\boldsymbol{\lambda}\cdot{\boldsymbol{{\mathcal{W}}}}{\boldsymbol{f}}\right\|_{1},~{}\frac{1}{|{\boldsymbol{\Lambda}}|}\sum_{{\boldsymbol{k}}\in{\boldsymbol{\Lambda}}}\left|({\boldsymbol{{\mathcal{A}}}}\boldsymbol{u})[{\boldsymbol{k}}]-{\boldsymbol{g}}[{\boldsymbol{k}}]\right|^{2}\leq\eta^{2},~{}\boldsymbol{u}\in[0,M]^{\boldsymbol{\Omega}}\right\\}$
(2.18)

as an involved hypothesis space. In Eq. 2.18, $M>0$ is a positive constant
related to the boundedness of each pixel value, $\eta>0$ is a fixed positive
constant related to the bound of measurement error, and the weighted
$\ell_{1}$-norm of wavelet frame coefficients
$\left\|\boldsymbol{\lambda}\cdot{\boldsymbol{{\mathcal{W}}}}\boldsymbol{u}\right\|_{1}$
is defined as Eq. 2.15.

Our error estimate is based on the characterization of the capacity of the
hypothesis space [18]. Among such capacities including VC dimension [60],
$V_{\gamma}$-dimension and $P_{\gamma}$-dimension [3], Rademacher complexities
[7, 50], and covering number [29], we choose the covering number because it is
the most convenient for metric spaces [18].

######  Definition 2.3.

Let ${\mathscr{M}}\subseteq{\mathbb{R}}^{\boldsymbol{\Omega}}$ and $r>0$ be
given. The covering number ${\mathcal{N}}({\mathscr{M}},r)$ is defined as

$\displaystyle{\mathcal{N}}\left({\mathscr{M}},r\right)=\inf\left\\{K\in{\mathbb{N}}:\exists~{}\boldsymbol{u}_{1},\cdots,\boldsymbol{u}_{K}\in{\mathscr{M}}~{}~{}\text{s.t.}~{}~{}{\mathscr{M}}\subseteq\bigcup_{j=1}^{K}\left\\{\boldsymbol{u}\in{\mathscr{M}}:\left\|\boldsymbol{u}-\boldsymbol{u}_{j}\right\|_{\ell_{\infty}(\boldsymbol{\Omega})}\leq
r\right\\}\right\\},$

i.e. the minimal number of $\ell_{\infty}$ balls with radius $r$ in
${\mathscr{M}}$ that covers ${\mathscr{M}}$.

With the above notation, we can present the first relation between the
solution $\boldsymbol{u}^{{\boldsymbol{\Lambda}}}$ to Eq. 1.5 and the
underlying image ${\boldsymbol{f}}$. Following the idea of statistical
learning theory [60], we first establish the probability of the following
event

$\displaystyle\frac{1}{|\boldsymbol{\Omega}|}\left\|\boldsymbol{u}^{{\boldsymbol{\Lambda}}}-{\boldsymbol{f}}\right\|_{\ell_{2}(\boldsymbol{\Omega})}^{2}\leq\epsilon+\frac{16}{3}\sigma_{\min}^{-2}({\boldsymbol{{\mathcal{A}}}})\eta^{2}$

for an arbitrary $\epsilon>0$ in terms of the covering number with the radius
related to $\epsilon$. The proof is postponed to Section 3.1

######  Theorem 2.4.

Let ${\mathscr{M}}$ be defined as in Eq. 2.18 and
$\boldsymbol{u}^{{\boldsymbol{\Lambda}}}$ be a solution to Eq. 1.5. Then for
an arbitrary $\epsilon>0$, the following inequality

$\displaystyle\mathbb{P}\left\\{\frac{1}{|\boldsymbol{\Omega}|}\left\|\boldsymbol{u}^{{\boldsymbol{\Lambda}}}-{\boldsymbol{f}}\right\|_{\ell_{2}(\boldsymbol{\Omega})}^{2}\leq\epsilon+\frac{16}{3}\sigma_{\min}^{-2}({\boldsymbol{{\mathcal{A}}}})\eta^{2}\right\\}\geq
1-{\mathcal{N}}\left({\mathscr{M}},\frac{\sigma_{\min}^{2}({\boldsymbol{{\mathcal{A}}}})\epsilon}{12\left\|{\boldsymbol{{\mathcal{A}}}}\right\|_{\infty}^{2}M}\right)\exp\left\\{-\frac{3m\sigma_{\min}^{2}({\boldsymbol{{\mathcal{A}}}})\epsilon}{256\left\|{\boldsymbol{{\mathcal{A}}}}\right\|_{\infty}^{2}M^{2}}\right\\}$

holds for an arbitrary $m$, where $m=|{\boldsymbol{\Lambda}}|$ denotes the
number of samples.

######  Remark 2.5.

Notice that the proof of Theorem 2.4 is completed if we estimate the
probability of the event

$\displaystyle\frac{1}{|\boldsymbol{\Omega}|}\left\|{\boldsymbol{{\mathcal{A}}}}\boldsymbol{u}^{{\boldsymbol{\Lambda}}}-{\boldsymbol{{\mathcal{A}}}}{\boldsymbol{f}}\right\|_{\ell_{2}(\boldsymbol{\Omega})}^{2}\leq\sigma_{\min}^{2}\left({\boldsymbol{{\mathcal{A}}}}\right)\epsilon+\frac{16}{3}\eta^{2}.$

In this case, we need to use the uniform boundedness constraint
($\boldsymbol{u}[{\boldsymbol{k}}]\in[0,M]$ for all
${\boldsymbol{k}}\in\boldsymbol{\Omega}$), from which we need an assumption on
$\left\|{\boldsymbol{{\mathcal{A}}}}\right\|_{\infty}$. See Section 3.1 for
details.

By Theorem 2.4, our error estimate will be completed if we estimate the
covering number ${\mathcal{N}}\left({\mathscr{M}},r\right)$. Intuitively,
since ${\mathscr{M}}$ lies in an $\ell_{\infty}$ ball
$\big{\\{}\boldsymbol{u}\in\ell_{\infty}(\boldsymbol{\Omega}):\left\|\boldsymbol{u}\right\|_{\ell_{\infty}(\boldsymbol{\Omega})}\leq
M\big{\\}}$, it is obvious that

$\displaystyle{\mathcal{N}}({\mathscr{M}},r)\leq\left(\frac{2M}{r}\right)^{|\boldsymbol{\Omega}|}$
(2.19)

as given in [29]. However, since the above estimation Eq. 2.19 is not tight
enough to derive an error estimate, we need to find a tighter upper bound for
${\mathcal{N}}({\mathscr{M}},r)$ to obtain a reasonable error bound. To do
this, we adopt the idea given in [18]; using the discrete total variation, we
connect the wavelet frame coefficients
${\boldsymbol{{\mathcal{W}}}}\boldsymbol{u}$ with the regularity of
$\boldsymbol{u}$. Specifically, we define the discrete gradient of
$\boldsymbol{u}\in{\mathbb{R}}^{\boldsymbol{\Omega}}$ as

$\displaystyle\boldsymbol{\nabla}\boldsymbol{u}=\left\\{\boldsymbol{u}[{\boldsymbol{k}}+{\boldsymbol{e}}_{j}]-\boldsymbol{u}[{\boldsymbol{k}}]:j=1,2,~{}{\boldsymbol{k}}\in\boldsymbol{\Omega},~{}\&~{}{\boldsymbol{k}}+{\boldsymbol{e}}_{j}\in\boldsymbol{\Omega}\right\\},$
(2.20)

where ${\boldsymbol{e}}_{1}=(1,0)$ and ${\boldsymbol{e}}_{2}=(0,1)$. The
discrete total variation
$\left\|\boldsymbol{\nabla}\boldsymbol{u}\right\|_{1}$ is defined as

$\displaystyle\left\|\boldsymbol{\nabla}\boldsymbol{u}\right\|_{1}:=\sum_{j=1}^{2}\sum_{\stackrel{{\scriptstyle{\boldsymbol{k}}\in\boldsymbol{\Omega}}}{{{\boldsymbol{k}}+{\boldsymbol{e}}_{j}\in\boldsymbol{\Omega}}}}\left|\boldsymbol{u}[{\boldsymbol{k}}+{\boldsymbol{e}}_{j}]-\boldsymbol{u}[{\boldsymbol{k}}]\right|.$
(2.21)

Under this setting, we present Lemma 2.6 whose proof is postponed to Section
3.2.

######  Lemma 2.6.

Let ${\boldsymbol{{\mathcal{W}}}}$ be a tensor product B-spline wavelet frame
transform defined as Eq. 2.13. Then there exists a constant
$C_{{\boldsymbol{{\mathcal{W}}}}}\geq 1$ which is independent of
$|\boldsymbol{\Omega}|$ and $L$ such that

$\displaystyle\left\|\nabla\boldsymbol{u}\right\|_{1}\leq
C_{{\boldsymbol{{\mathcal{W}}}}}\left\|{\boldsymbol{{\mathcal{W}}}}\boldsymbol{u}\right\|_{1}$
(2.22)

for all $\boldsymbol{u}\in{\mathbb{R}}^{\boldsymbol{\Omega}}$. In Eq. 2.22,
$\left\|\boldsymbol{\nabla}\boldsymbol{u}\right\|_{1}$ is defined as Eq. 2.21,
and $\left\|{\boldsymbol{{\mathcal{W}}}}\boldsymbol{u}\right\|_{1}$ is defined
as Eq. 2.16.

Lemma 2.6 tells us that, given that
$\boldsymbol{\lambda}=\left\\{\lambda_{l,\boldsymbol{\alpha}}[{\boldsymbol{k}}]\right\\}$
satisfies A2, for $\boldsymbol{u}\in{\mathscr{M}}$, we have

$\displaystyle\left\|\boldsymbol{\nabla}\boldsymbol{u}\right\|_{1}$
$\displaystyle\leq
C_{{\boldsymbol{{\mathcal{W}}}}}\left\|{\boldsymbol{{\mathcal{W}}}}\boldsymbol{u}\right\|_{1}=C_{{\boldsymbol{{\mathcal{W}}}}}\sum_{{\boldsymbol{k}}\in\boldsymbol{\Omega}}\sum_{l=0}^{L-1}\sum_{\boldsymbol{\alpha}\in{\mathbb{B}}}\left|\left({\boldsymbol{{\mathcal{W}}}}_{l,\boldsymbol{\alpha}}\boldsymbol{u}\right)[{\boldsymbol{k}}]\right|$
$\displaystyle\leq
C_{{\boldsymbol{{\mathcal{W}}}}}2^{\max\left\\{-\beta,0\right\\}\max\left\\{\Upsilon(l,\boldsymbol{\alpha},{\boldsymbol{k}}):(l,\boldsymbol{\alpha},{\boldsymbol{k}})\in\Gamma\right\\}}\sum_{{\boldsymbol{k}}\in\boldsymbol{\Omega}}\sum_{l=0}^{L-1}\sum_{\boldsymbol{\alpha}\in{\mathbb{B}}}2^{\beta\Upsilon(l,\boldsymbol{\alpha},{\boldsymbol{k}})}\left|\left({\boldsymbol{{\mathcal{W}}}}_{l,\boldsymbol{\alpha}}\boldsymbol{u}\right)[{\boldsymbol{k}}]\right|$
$\displaystyle\leq
C_{{\boldsymbol{{\mathcal{W}}}}}|\boldsymbol{\Omega}|^{\frac{\max\\{1-\beta,0\\}}{2}}\left\|\boldsymbol{\lambda}\cdot{\boldsymbol{{\mathcal{W}}}}{\boldsymbol{f}}\right\|_{1}.$

Hence, we can further relax the set ${\mathscr{M}}$ into

$\displaystyle\widetilde{{\mathscr{M}}}=\left\\{\boldsymbol{u}\in\ell_{\infty}(\boldsymbol{\Omega}):\left\|\nabla\boldsymbol{u}\right\|_{1}\leq
C_{{\boldsymbol{{\mathcal{W}}}}}|\boldsymbol{\Omega}|^{\frac{\max\\{1-\beta,0\\}}{2}}\left\|\boldsymbol{\lambda}\cdot{\boldsymbol{{\mathcal{W}}}}{\boldsymbol{f}}\right\|_{1},~{}\left\|\boldsymbol{u}\right\|_{\ell_{\infty}(\boldsymbol{\Omega})}\leq
M\right\\}.$ (2.23)

Then with the set $\widetilde{{\mathscr{M}}}$ defined above, we present
Theorem 2.7 for the estimation of covering number. Similar to [18, Theorem
2.4], our estimate is also based on the quantized total variation minimization
(e.g. [1, 24]) and the max-flow min-cut theorem [32] to introduce a new upper
bound of the covering number.

######  Theorem 2.7.

Let ${\boldsymbol{{\mathcal{W}}}}$ be a tensor product B-spline wavelet frame
transform defined as Eq. 2.13. Assume that A2 is satisfied with
$-1\leq\beta\leq 1$ and
$\left\|\boldsymbol{\lambda}\cdot{\boldsymbol{{\mathcal{W}}}}{\boldsymbol{f}}\right\|_{1}\leq
C_{{\boldsymbol{f}}}|\boldsymbol{\Omega}|^{1/2}$. Let ${\mathscr{M}}$ be
defined as Eq. 2.18. For $r\geq|\boldsymbol{\Omega}|^{-a}$ with $a\geq 1$, we
have

$\displaystyle\ln{\mathcal{N}}({\mathscr{M}},r)\leq\frac{C_{a}|\boldsymbol{\Omega}|^{\frac{\max\\{1-\beta,1\\}}{2}}}{r}\log_{2}|\boldsymbol{\Omega}|,$

where
$C_{a}=20M(4a+\max\\{1-\beta,1\\})C_{{\boldsymbol{{\mathcal{W}}}}}C_{{\boldsymbol{f}}}(1+C_{{\boldsymbol{{\mathcal{W}}}}}C_{{\boldsymbol{f}}})$.

######  Proof 1.

See Section 3.3.

With the aid of Theorems 2.4 and 2.7, we can establish the explicit
formulation of Eq. 1.6 in Theorem 2.8. Briefly speaking, for a fixed $\rho$,
as long as the resolution of an image is sufficiently high, the wavelet frame
based restoration model Eq. 1.5 has a good chance to restore the original
image within the measurement error. In addition, for a fixed
$|\boldsymbol{\Omega}|$, the error gets smaller as $\rho\nearrow 1$, which
coincides with our common sense. Finally, Theorem 2.8 takes the results in
[18] as a special case because
$\left\|{\boldsymbol{{\mathcal{I}}}}\right\|_{\infty}=\sigma_{\min}({\boldsymbol{{\mathcal{I}}}})=1$.

######  Theorem 2.8.

Let ${\boldsymbol{{\mathcal{W}}}}$ be a tensor product B-spline wavelet frame
transform. Assume that ${\boldsymbol{{\mathcal{A}}}}$ satisfies A1,
$\boldsymbol{\lambda}$ satisfies A2 with $-1<\beta<1$, and
${\boldsymbol{f}}\in[0,M]^{\boldsymbol{\Omega}}$ satisfies
$\left\|\boldsymbol{\lambda}\cdot{\boldsymbol{{\mathcal{W}}}}{\boldsymbol{f}}\right\|_{1}\leq
C_{{\boldsymbol{f}}}|\boldsymbol{\Omega}|^{1/2}$. Let
$\boldsymbol{u}^{{\boldsymbol{\Lambda}}}$ be a solution to Eq. 1.5. Then the
following inequality

$\displaystyle\frac{1}{|\boldsymbol{\Omega}|}\left\|\boldsymbol{u}^{{\boldsymbol{\Lambda}}}-{\boldsymbol{f}}\right\|_{\ell_{2}(\boldsymbol{\Omega})}^{2}\leq\widetilde{c}\rho^{-\frac{1}{2}}|\boldsymbol{\Omega}|^{-\frac{\min\\{1+\beta,1\\}}{4}}\left(\log_{2}|\boldsymbol{\Omega}|\right)^{3/2}+\frac{16}{3}\sigma_{\min}^{-2}({\boldsymbol{{\mathcal{A}}}})\eta^{2}$
(2.24)

holds with probability at least $1-|\boldsymbol{\Omega}|^{-1}$. In Eq. 2.24,
$\widetilde{c}$ is defined as

$\displaystyle\widetilde{c}=\frac{64\left\|{\boldsymbol{{\mathcal{A}}}}\right\|_{\infty}^{2}M^{2}}{3\sigma_{\min}^{2}({\boldsymbol{{\mathcal{A}}}})}\left[4+3\sqrt{5(4a+\max\\{1-\beta,1\\})C_{{\boldsymbol{{\mathcal{W}}}}}C_{{\boldsymbol{f}}}(1+C_{{\boldsymbol{{\mathcal{W}}}}}C_{{\boldsymbol{f}}})}\right],$

for some fixed $a\geq 1$. In words, $\widetilde{c}$ is independent of
$|\boldsymbol{\Omega}|$, $L$, $\rho$, and $\eta$.

######  Proof 2.

First of all, for any $\epsilon>0$, we can choose $a\geq 1$ such that
$\epsilon\geq\frac{12\left\|{\boldsymbol{{\mathcal{A}}}}\right\|_{\infty}^{2}M}{\sigma_{\min}^{2}({\boldsymbol{{\mathcal{A}}}})}|\boldsymbol{\Omega}|^{-a}$.
With
$r=\frac{\sigma_{\min}^{2}({\boldsymbol{{\mathcal{A}}}})\epsilon}{12\left\|{\boldsymbol{{\mathcal{A}}}}\right\|_{\infty}^{2}M}\geq|\boldsymbol{\Omega}|^{-a}$,
Theorems 2.4 and 2.7 give us that the inequality

$\displaystyle\frac{1}{|\boldsymbol{\Omega}|}\left\|\boldsymbol{u}^{{\boldsymbol{\Lambda}}}-{\boldsymbol{f}}\right\|_{\ell_{2}(\boldsymbol{\Omega})}^{2}\leq\epsilon+\frac{16}{3}\sigma_{\min}^{-2}({\boldsymbol{{\mathcal{A}}}})\eta^{2}$

holds with probability at least

$\displaystyle 1$
$\displaystyle-{\mathcal{N}}\left({\mathscr{M}},\frac{\sigma_{\min}^{2}({\boldsymbol{{\mathcal{A}}}})\epsilon}{12\left\|{\boldsymbol{{\mathcal{A}}}}\right\|_{\infty}^{2}M}\right)\exp\left\\{-\frac{3m\sigma_{\min}^{2}({\boldsymbol{{\mathcal{A}}}})\epsilon}{256\left\|{\boldsymbol{{\mathcal{A}}}}\right\|_{\infty}^{2}M^{2}}\right\\}$
$\displaystyle\geq
1-\exp\left\\{\frac{240\left\|{\boldsymbol{{\mathcal{A}}}}\right\|_{\infty}^{2}M^{2}(4a+b)C_{{\boldsymbol{{\mathcal{W}}}}}C_{{\boldsymbol{f}}}(1+C_{{\boldsymbol{{\mathcal{W}}}}}C_{{\boldsymbol{f}}})|\Omega|^{b/2}\log_{2}|\boldsymbol{\Omega}|}{\sigma_{\min}^{2}({\boldsymbol{{\mathcal{A}}}})\epsilon}-\frac{3m\sigma_{\min}^{2}({\boldsymbol{{\mathcal{A}}}})\epsilon}{256\left\|{\boldsymbol{{\mathcal{A}}}}\right\|_{\infty}^{2}M^{2}}\right\\}.$

In the above, we use $b=\max\\{1-\beta,1\\}$ for notational simplicity. Hence,
if we choose a special $\epsilon^{*}$ to be the unique positive solution to
the following equation

$\displaystyle\frac{240\left\|{\boldsymbol{{\mathcal{A}}}}\right\|_{\infty}^{2}M^{2}(4a+b)C_{{\boldsymbol{{\mathcal{W}}}}}C_{{\boldsymbol{f}}}(1+C_{{\boldsymbol{{\mathcal{W}}}}}C_{{\boldsymbol{f}}})|\Omega|^{b/2}\log_{2}|\boldsymbol{\Omega}|}{\sigma_{\min}^{2}({\boldsymbol{{\mathcal{A}}}})\epsilon}-\frac{3m\sigma_{\min}^{2}({\boldsymbol{{\mathcal{A}}}})\epsilon}{256\left\|{\boldsymbol{{\mathcal{A}}}}\right\|_{\infty}^{2}M^{2}}=\ln\frac{1}{|\boldsymbol{\Omega}|},$
(2.25)

we have

$\displaystyle\frac{1}{|\boldsymbol{\Omega}|}\left\|\boldsymbol{u}^{{\boldsymbol{\Lambda}}}-{\boldsymbol{f}}\right\|_{\ell_{2}(\boldsymbol{\Omega})}^{2}\leq\epsilon^{*}+\frac{16}{3}\sigma_{\min}^{-2}({\boldsymbol{{\mathcal{A}}}})\eta^{2}$

with probability at least $1-|\boldsymbol{\Omega}|^{-1}$. Indeed, solving Eq.
2.25 yields Eq. 2.24:

$\displaystyle\epsilon^{*}$
$\displaystyle=\frac{128\left\|{\boldsymbol{{\mathcal{A}}}}\right\|_{\infty}^{2}M^{2}}{3m\sigma_{\min}^{2}({\boldsymbol{{\mathcal{A}}}})}\left[\ln|\boldsymbol{\Omega}|+\sqrt{\ln^{2}|\boldsymbol{\Omega}|+\frac{45}{4}m(4a+b)C_{{\boldsymbol{{\mathcal{W}}}}}C_{{\boldsymbol{f}}}(1+C_{{\boldsymbol{{\mathcal{W}}}}}C_{{\boldsymbol{f}}})|\boldsymbol{\Omega}|^{b/2}\log_{2}|\boldsymbol{\Omega}|}\right]$
$\displaystyle\leq\frac{64\left\|{\boldsymbol{{\mathcal{A}}}}\right\|_{\infty}^{2}M^{2}}{3m\sigma_{\min}^{2}({\boldsymbol{{\mathcal{A}}}})}\left[4\ln|\boldsymbol{\Omega}|+3\sqrt{5m(4a+b)C_{{\boldsymbol{{\mathcal{W}}}}}C_{{\boldsymbol{f}}}(1+C_{{\boldsymbol{{\mathcal{W}}}}}C_{{\boldsymbol{f}}})(1+C_{{\boldsymbol{{\mathcal{W}}}}}C_{{\boldsymbol{f}}})|\boldsymbol{\Omega}|^{b/2}\log_{2}|\boldsymbol{\Omega}|}\right]$
$\displaystyle\leq\frac{64\left\|{\boldsymbol{{\mathcal{A}}}}\right\|_{\infty}^{2}M^{2}}{3\sigma_{\min}^{2}({\boldsymbol{{\mathcal{A}}}})}\left[4+3\sqrt{5(4a+b)C_{{\boldsymbol{{\mathcal{W}}}}}C_{{\boldsymbol{f}}}(1+C_{{\boldsymbol{{\mathcal{W}}}}}C_{{\boldsymbol{f}}})}\right]\rho^{-\frac{1}{2}}|\boldsymbol{\Omega}|^{\frac{b-2}{4}}\left(\log_{2}|\boldsymbol{\Omega}|\right)^{3/2},$

as $b-2=-\min\\{1+\beta,1\\}$. In addition, from the definition of
$\epsilon^{*}$, we have

$\displaystyle\epsilon^{*}$
$\displaystyle\geq\frac{128\left\|{\boldsymbol{{\mathcal{A}}}}\right\|_{\infty}^{2}M^{2}}{\sigma_{\min}^{2}({\boldsymbol{{\mathcal{A}}}})\sqrt{m}}\sqrt{C_{{\boldsymbol{{\mathcal{W}}}}}C_{{\boldsymbol{f}}}(1+C_{{\boldsymbol{{\mathcal{W}}}}}C_{{\boldsymbol{f}}})|\boldsymbol{\Omega}|^{b/2}\log_{2}|\boldsymbol{\Omega}|}$
$\displaystyle\geq\frac{16\left\|{\boldsymbol{{\mathcal{A}}}}\right\|_{\infty}^{2}M}{\sigma_{\min}^{2}({\boldsymbol{{\mathcal{A}}}})}\sqrt{C_{{\boldsymbol{{\mathcal{W}}}}}C_{{\boldsymbol{f}}}(1+C_{{\boldsymbol{{\mathcal{W}}}}}C_{{\boldsymbol{f}}})}\rho^{-\frac{1}{2}}\sqrt{\log_{2}|\boldsymbol{\Omega}|}|\boldsymbol{\Omega}|^{\frac{b-2}{4}}\geq\frac{12\left\|{\boldsymbol{{\mathcal{A}}}}\right\|_{\infty}^{2}M}{\sigma_{\min}^{2}({\boldsymbol{{\mathcal{A}}}})}|\boldsymbol{\Omega}|^{-a}.$

In the final inequality, we use the fact that for $\beta\in(-1,1)$, we have
$b-2=-\min\\{1+\beta,1\\}\in(-1,0)$ while $a\geq 1$. This completes the proof.
$\square$

######  Remark 2.9.

From the proof of Theorem 2.8, we can see that the constant $a\geq 1$ is to
apply Theorem 2.7 to Theorem 2.4. Notice that the lower bound of the
probability of

$\displaystyle\frac{1}{|\boldsymbol{\Omega}|}\left\|\boldsymbol{u}^{{\boldsymbol{\Lambda}}}-{\boldsymbol{f}}\right\|_{\ell_{2}(\boldsymbol{\Omega})}^{2}\leq\epsilon+\frac{16}{3}\sigma_{\min}^{-2}\left({\boldsymbol{{\mathcal{A}}}}\right)\eta^{2}$

decreases as $\epsilon>0$ decreases. Meanwhile, we estimate the critical
$\epsilon^{*}>0$ (i.e. the positive solution to Eq. 2.25) by fixing the
probability to be no smaller than $1-|\boldsymbol{\Omega}|^{-1}$, which in
turn increases the upper bound (or the confidence interval) of
$\epsilon^{*}>0$ as reflected by the constant $a\geq 1$. Nevertheless, we
forgo the effect of $a\geq 1$ in Eq. 2.24 to the error estimate in order not
to dilute the focus of this paper. In fact, $a\geq 1$ becomes fixed once we
fix the admissible lower bound of $\epsilon>0$ in Theorem 2.4 to apply Theorem
2.7.

To conclude, we present some numerical results to demonstrate the theoretical
error bound in Eq. 2.24 and the empirical restoration error under different
settings of $|\boldsymbol{\Omega}|$ and $\rho$. Specifically, we fix $N=2^{J}$
and $\eta=0$, and we consider the following noise-free case

$\displaystyle\min_{\boldsymbol{u}\in[0,M]^{\boldsymbol{\Omega}}}~{}\left\|\boldsymbol{\lambda}\cdot{\boldsymbol{{\mathcal{W}}}}\boldsymbol{u}\right\|_{1}~{}~{}~{}\text{subject
to}~{}~{}~{}\left({\boldsymbol{{\mathcal{A}}}}\boldsymbol{u}\right)[{\boldsymbol{k}}]={\boldsymbol{g}}[{\boldsymbol{k}}],~{}~{}{\boldsymbol{k}}\in{\boldsymbol{\Lambda}},$
(2.26)

so that Eq. 2.24 takes the form of

$\displaystyle\frac{1}{2^{2J}}\left\|\boldsymbol{u}^{{\boldsymbol{\Lambda}}}-{\boldsymbol{f}}\right\|_{\ell_{2}(\boldsymbol{\Omega})}^{2}\leq\widetilde{c}\rho^{-1/2}J^{3/2}2^{-J\min\left\\{\frac{1+\beta}{2},\frac{1}{2}\right\\}}$
(2.27)

with probability at least $1-2^{-2J}$.

In this simulation, two types of ${\boldsymbol{{\mathcal{A}}}}$ are used; one
is the identity operator ${\boldsymbol{{\mathcal{I}}}}$ (i.e. the image
inpainting) and the other is a convolution operator with a low-pass filter
generated by the Matlab built-in function “fspecial(‘gaussian’,$9$,$1$)” (i.e.
the simultaneous deblurring and inpainting). More precisely, we generate a
piecewise linear phantom as an underlying true image ${\boldsymbol{f}}$, and
we implement the simulation for each ${\boldsymbol{{\mathcal{A}}}}$ as
follows. To see the behavior of error with respect to the sample density
$\rho$, we fix $N=512$ (i.e. $J=9$), and for each
$\rho\in\left\\{0.2,0.3,0.4,0.5,0.6,0.7,0.8\right\\}$, we test Eq. 2.26 with
$100$ realizations of ${\boldsymbol{\Lambda}}$. To see the behavior of error
with respect to $|\boldsymbol{\Omega}|$, we fix $\rho=0.5$, and for each
$J\in\left\\{5,6,7,8,9,10\right\\}$ (or the resolution $J$), we again test Eq.
2.26 with $100$ realizations of ${\boldsymbol{\Lambda}}$. In any case, we
choose ${\boldsymbol{{\mathcal{W}}}}$ to be the tensor product piecewise
linear B-spline wavelet frame with $1$ level of decomposition, and Eq. 2.26 is
solved by the split Bregman algorithm [17]. Finally, we choose the largest
empirical error to compare with the smallest theoretical error in Eq. 2.27 by
setting $\beta=0$ in Eq. 2.27. In particular, it is in general difficult to
determine the constants explicitly, we calculate the above error by assuming
that the equality holds in the worst case, i.e. in the lowest sample density,
or the lowest resolution case. The results are presented in Figs. 1 and 2
respectively. Specifically, Figs. 1a and 2a show the results when $N=512$ is
fixed and $\rho$ is varying, and Figs. 1b and 2b demonstrate when $\rho=0.5$
is fixed and $N$ is varying. We can easily see that, in any case, the
empirical restoration error does not exceed the theoretical error in Eq. 2.27,
which empirically demonstrates that Theorem 2.8 provides a reasonable upper
bound for the restoration error with high probability.

(a)

(b)

Figure 1: Simulation results for the image inpainting. Fig. 1a describes the
simulation results when $N=512$ is fixed, and Fig. 1b depicts the simulation
results when $\rho=0.5$ is fixed.

(a)

(b)

Figure 2: Simulation results for the simultaneous deblurring and inpainting.
Fig. 2a describes the simulation results when $N=512$ is fixed, and Fig. 2b
depicts the simulation results when $\rho=0.5$ is fixed.

###  2.3 Asymptotic function approximation via MRA

In this section, we apply Theorem 2.8 to further connect with the function
approximation given that the underlying true image is obtained by the samples
of a function. All functions we consider are defined on $\Omega=[0,1)^{2}$,
and we consider the $2^{J}\times 2^{J}$ Cartesian grid $\boldsymbol{\Omega}$
defined as

$\displaystyle\boldsymbol{\Omega}=\left\\{0,1,\cdots,2^{J}-1\right\\}^{2}\simeq
2^{-J}{\mathbb{Z}}^{2}\cap\Omega.$

In other words, we implicitly identify the $2^{J}\times 2^{J}$ grid
$\boldsymbol{\Omega}$ with the $2^{J}\times 2^{J}$ mesh of $\Omega$. For the
consistency with the discrete image cases, we identify $L_{p}(\Omega)$ with
the space of $L_{p}$ functions on ${\mathbb{R}}^{2}$ with fundamental period
on each variable to be $1$. For the wavelet frame decomposition (e.g. [31,
37]) of $f\in L_{2}(\Omega)$, we write

$\displaystyle
f=\sum_{l\in{\mathbb{Z}}}\sum_{{\boldsymbol{k}}\in\boldsymbol{\Omega}}\sum_{\boldsymbol{\alpha}\in{\mathbb{B}}}\langle
f,\psi_{\boldsymbol{\alpha},l,{\boldsymbol{k}}}\rangle\psi_{\boldsymbol{\alpha},l,{\boldsymbol{k}}}$

by identifying $\psi_{\boldsymbol{\alpha},l,{\boldsymbol{k}}}$ with its
periodized version

$\displaystyle\psi_{\boldsymbol{\alpha},l,{\boldsymbol{k}}}^{\mathrm{per}}=\sum_{{\boldsymbol{k}}^{\prime}\in{\mathbb{Z}}^{2}}\psi_{\boldsymbol{\alpha},l,{\boldsymbol{k}}}(\cdot+2^{\max\\{l,J\\}}{\boldsymbol{k}}^{\prime})$

with a slight abuse of notation.

In the literature of wavelet frame, the discrete image ${\boldsymbol{f}}$ is
interpreted as discrete sampling of an underlying function $f\in
L_{2}(\Omega)$ via the inner product with the corresponding refinable function
$\phi$. More precisely, let
$\phi_{J,{\boldsymbol{k}}}=2^{J}\phi(2^{J}\cdot-{\boldsymbol{k}})$. Then we
can write ${\boldsymbol{f}}$ as

$\displaystyle{\boldsymbol{f}}[{\boldsymbol{k}}]=2^{J}\left\langle
f,\phi_{J,{\boldsymbol{k}}}\right\rangle.$ (2.28)

With this ${\boldsymbol{f}}$, we implicitly use the following interpolated
function

$\displaystyle
f_{J}=\sum_{{\boldsymbol{k}}\in\boldsymbol{\Omega}}{\boldsymbol{f}}[{\boldsymbol{k}}]\phi(2^{J}\cdot-{\boldsymbol{k}})=\sum_{{\boldsymbol{k}}\in\boldsymbol{\Omega}}\left\langle
f,\phi_{J,{\boldsymbol{k}}}\right\rangle\phi_{J,{\boldsymbol{k}}}$ (2.29)

to approximate $f$.

There are extensive studies on the approximation order of $f_{J}$ in Eq. 2.29
to the original $f$, and most of them are based on certain properties of the
refinable function $\phi$. Relevant works include the wavelet frame based
scattered data restoration [63] and the wavelet frame based image
denoising/inpainting [40]. Briefly speaking, these works commonly assume the
Strang-Fix condition on $\phi$ (e.g. [31, 49]) to approximate the underlying
function in the Sobolev space of a certain order. Meanwhile, the underlying
function that we concern in this paper does not satisfy certain order of
regularity. Instead, we only impose some decay condition of the wavelet frame
coefficients for the analysis of the approximation order. More precisely, we
assume that there is $\beta\geq-1$ such that

$\displaystyle C_{f}:=\sum_{l=J-L}^{\infty}2^{\beta
l}\sum_{{\boldsymbol{k}}\in\boldsymbol{\Omega}}\sum_{\boldsymbol{\alpha}\in{\mathbb{B}}}\big{|}\langle
f,\psi_{\boldsymbol{\alpha},l,{\boldsymbol{k}}}\rangle\big{|}<\infty.$ (2.30)

Note that the above decay condition links to the regularity of the underlying
function $f$ when the wavelet frame system satisfies some mild conditions [10,
18, 46].

Under the decay condition given in Eq. 2.30, we present the following
approximation of underlying function in Theorem 2.10. Briefly speaking, as
long as the image resolution is sufficiently large, the approximated function
constructed from the restored image gives a good approximation of the
underlying function where the underlying true image comes from.

######  Theorem 2.10.

Let ${\boldsymbol{{\mathcal{W}}}}$ be a tensor product B-spline wavelet frame
transform. Assume that A1 is satisfied, and
$\boldsymbol{\lambda}=\left\\{\lambda_{l,\boldsymbol{\alpha}}[{\boldsymbol{k}}]:l=0,\cdots,L-1,~{}\boldsymbol{\alpha}\in{\mathbb{B}},~{}{\boldsymbol{k}}\in\boldsymbol{\Omega}\right\\}$
is defined as

$\displaystyle\lambda_{l,\boldsymbol{\alpha}}[{\boldsymbol{k}}]=2^{\beta(J-l-1)},~{}~{}~{}~{}~{}l=0,\cdots,L-1,~{}\boldsymbol{\alpha}\in{\mathbb{B}},~{}{\boldsymbol{k}}\in\boldsymbol{\Omega},$
(2.31)

and the underlying function $f\in L_{2}(\Omega)$ satisfies Eq. 2.30 with
$-1<\beta<1$. Let $\boldsymbol{u}^{{\boldsymbol{\Lambda}}}$ be a solution to
Eq. 1.5 with ${\boldsymbol{g}}$ in Eq. 1.3 generated by ${\boldsymbol{f}}$ in
Eq. 2.28. If $f(\boldsymbol{x})\in[0,M]$ a.e. $\boldsymbol{x}\in\Omega$, we
have the followings:

  1. 1.

The inequality

$\displaystyle\frac{1}{2^{2J}}\left\|\boldsymbol{u}^{{\boldsymbol{\Lambda}}}-{\boldsymbol{f}}\right\|_{\ell_{2}(\boldsymbol{\Omega})}^{2}\leq\widetilde{c}\rho^{-\frac{1}{2}}J^{3/2}2^{-J\min\left\\{\frac{1+\beta}{2},\frac{1}{2}\right\\}}+\frac{16}{3}\sigma_{\min}^{-2}({\boldsymbol{{\mathcal{A}}}})\eta^{2}$
(2.32)

holds with probability at least $1-2^{-2J}$, where $\widetilde{c}$ is a
constant independent of $J$ (i.e. independent of $|\boldsymbol{\Omega}|$),
$L$, $\rho$, and $\eta$.

  2. 2.

Let $u_{J}^{{\boldsymbol{\Lambda}}}$ be defined as

$\displaystyle
u_{J}^{{\boldsymbol{\Lambda}}}=\sum_{{\boldsymbol{k}}\in\boldsymbol{\Omega}}\boldsymbol{u}^{{\boldsymbol{\Lambda}}}[{\boldsymbol{k}}]\phi(2^{J}\cdot-{\boldsymbol{k}}).$

Then

$\displaystyle\left\|u_{J}^{{\boldsymbol{\Lambda}}}-f\right\|_{L_{2}(\Omega)}^{2}\leq
C_{1}\rho^{-\frac{1}{2}}J^{3/2}2^{-J\min\left\\{\frac{1+\beta}{2},\frac{1}{2}\right\\}}+C_{2}\eta^{2}+C_{3}2^{-(\beta+1)J}$
(2.33)

holds with probability at least $1-2^{-2J}$, where $C_{1}$, $C_{2}$, and
$C_{3}$ are three positive constants independent of $J$, $L$, $\rho$, and
$\eta$.

######  Remark 2.11.

Before proving Theorem 2.10, we would like to mention that, whenever
$J\in{\mathbb{N}}$ satisfies

$\displaystyle J\geq-\frac{2\log_{2}\eta}{\beta+1},$

Eq. 2.33 can be further written as

$\displaystyle\left\|u_{J}^{{\boldsymbol{\Lambda}}}-f\right\|_{L_{2}(\Omega)}^{2}\leq
C_{1}\rho^{-\frac{1}{2}}J^{3/2}2^{-J\min\left\\{\frac{1+\beta}{2},\frac{1}{2}\right\\}}+\left(C_{2}+C_{3}\right)\eta^{2}.$

In other words, whenever the mesh is sufficiently dense (i.e. $J$ is
sufficiently large), the $L_{2}$ distance between the interpolation of the
restored image and the original unknown function is bounded by the restoration
error of the discrete image restoration problem Eq. 1.5 only.

The rest is devoted to the proof of Theorem 2.10. To begin with, we introduce
the following lemma on the Bessel property of
$\left\\{\phi(2^{J}\cdot-{\boldsymbol{k}}):{\boldsymbol{k}}\in\boldsymbol{\Omega}\right\\}$.

######  Lemma 2.12.

Let $\phi$ be a tensor product B-spline of order $n$. For $J\in{\mathbb{N}}$,
we have the followings.

  1. 1.

For $u\in L_{2}(\Omega)$, we have

$\displaystyle\sum_{{\boldsymbol{k}}\in\boldsymbol{\Omega}}\left|\left\langle
u,\phi(2^{J}\cdot-{\boldsymbol{k}})\right\rangle\right|^{2}\leq\frac{n^{2}}{2^{2J}}\left\|u\right\|_{L_{2}(\Omega)}^{2}.$
(2.34)

  2. 2.

For $\boldsymbol{u}\in\ell_{2}(\boldsymbol{\Omega})$, we have

$\displaystyle\left\|\sum_{{\boldsymbol{k}}\in\boldsymbol{\Omega}}\boldsymbol{u}[{\boldsymbol{k}}]\phi(2^{J}\cdot-{\boldsymbol{k}})\right\|_{L_{2}(\Omega)}^{2}\leq\frac{n^{2}}{2^{2J}}\left\|\boldsymbol{u}\right\|_{\ell_{2}(\boldsymbol{\Omega})}^{2}.$
(2.35)

######  Proof 3.

Notice that $0\leq\phi\leq 1$, and the direct computation shows that
$\left\|\phi\right\|_{L_{2}({\mathbb{R}}^{2})}^{2}\leq 1$, and
$\left\|\phi(2^{J}\cdot-{\boldsymbol{k}})\right\|_{L_{2}({\mathbb{R}}^{2})}^{2}\leq
2^{-2J}$. Then by the Schwarz inequality, we have

$\displaystyle\left|\left\langle
u,\phi(2^{J}\cdot-{\boldsymbol{k}})\right\rangle\right|\leq
2^{-J}\left(\int_{\Omega}\left|u(\boldsymbol{x})\right|^{2}1_{{\mathbf{S}}_{{\boldsymbol{k}}}}(\boldsymbol{x}){\mathrm{d}}\boldsymbol{x}\right)^{1/2}$

where
${\mathbf{S}}_{{\boldsymbol{k}}}=\mathrm{supp}\left(\phi(2^{J}\cdot-{\boldsymbol{k}})\right)$.
Since $\sum 1_{{\mathbf{S}}_{{\boldsymbol{k}}}}=n^{2}$, we have

$\displaystyle\sum_{{\boldsymbol{k}}\in\boldsymbol{\Omega}}\left|\left\langle
u,\phi(2^{J}\cdot-{\boldsymbol{k}})\right\rangle\right|^{2}\leq
2^{-2J}\int_{\Omega}\left|u(\boldsymbol{x})\right|^{2}\left(\sum_{{\boldsymbol{k}}\in\boldsymbol{\Omega}}1_{{\mathbf{S}}_{{\boldsymbol{k}}}}(\boldsymbol{x})\right){\mathrm{d}}\boldsymbol{x}=\frac{n^{2}}{2^{2J}}\left\|u\right\|_{L_{2}(\Omega)}^{2},$

which proves Eq. 2.34.

For Eq. 2.35, let $v\in L_{2}(\Omega)$. We have

$\displaystyle\left\langle\sum_{{\boldsymbol{k}}\in\boldsymbol{\Omega}}\boldsymbol{u}[{\boldsymbol{k}}]\phi(2^{J}\cdot-{\boldsymbol{k}}),v\right\rangle=\sum_{{\boldsymbol{k}}\in\boldsymbol{\Omega}}\boldsymbol{u}[{\boldsymbol{k}}]\left\langle\phi(2^{J}\cdot-{\boldsymbol{k}}),v\right\rangle.$

By the Schwarz inequality, we have

$\displaystyle\sum_{{\boldsymbol{k}}\in\boldsymbol{\Omega}}\left|\boldsymbol{u}[{\boldsymbol{k}}]\right|\left|\left\langle\phi(2^{J}\cdot-{\boldsymbol{k}}),v\right\rangle\right|\leq\left(\sum_{{\boldsymbol{k}}\in\boldsymbol{\Omega}}\left|\boldsymbol{u}[{\boldsymbol{k}}]\right|^{2}\right)^{1/2}\left(\sum_{{\boldsymbol{k}}\in\boldsymbol{\Omega}}\left|\left\langle\phi(2^{J}\cdot-{\boldsymbol{k}}),v\right\rangle\right|^{2}\right)^{1/2}.$

By Eq. 2.34, we further have

$\displaystyle\left|\left\langle\sum_{{\boldsymbol{k}}\in\boldsymbol{\Omega}}\boldsymbol{u}[{\boldsymbol{k}}]\phi(2^{J}\cdot-{\boldsymbol{k}}),v\right\rangle\right|\leq\left(\sum_{{\boldsymbol{k}}\in\boldsymbol{\Omega}}\left|\boldsymbol{u}[{\boldsymbol{k}}]\right|^{2}\right)^{1/2}\frac{n}{2^{J}}\left\|v\right\|_{L_{2}(\Omega)}.$

Since $v\in L_{2}(\Omega)$ is arbitrary, we have Eq. 2.35 by the converse of
Hölder’s inequality with $p=q=2$ (e.g. [43]). This completes the proof.
$\square$

######  Proof of Theorem 2.10 1.

Notice that in this case, we have $|\boldsymbol{\Omega}|=2^{2J}$. In addition,
for $\boldsymbol{\lambda}$ defined as Eq. 2.31, we have

$\displaystyle\Upsilon(l,\boldsymbol{\alpha},{\boldsymbol{k}})=J-l-1<J:=\frac{1}{2}\log_{2}|\boldsymbol{\Omega}|,~{}~{}l=0,\cdots,L-1,~{}\boldsymbol{\alpha}\in{\mathbb{B}},~{}{\boldsymbol{k}}\in\boldsymbol{\Omega},$

which shows that our choice of $\boldsymbol{\lambda}$ satisfies A2. When the
wavelet frame transform is applied to ${\boldsymbol{f}}$ in Eq. 2.28, the
refinable equations Eqs. 2.6 and 2.7 and the definitions of
${\mathscr{X}}^{J}({\boldsymbol{\Psi}})$ Eqs. 2.2 and 2.5 lead to

$\displaystyle\big{(}{\boldsymbol{{\mathcal{W}}}}_{l,\boldsymbol{\alpha}}{\boldsymbol{f}}\big{)}[{\boldsymbol{k}}]=2^{J}\langle
f,\psi_{\boldsymbol{\alpha},J-1-l,{\boldsymbol{k}}}\rangle,~{}~{}~{}~{}~{}\boldsymbol{\alpha}\in{\mathbb{B}}\cup\left\\{{\mathbf{0}}\right\\},~{}~{}~{}0\leq
l\leq L-1$

with $\psi_{{\mathbf{0}},l,{\boldsymbol{k}}}=\phi_{l,{\boldsymbol{k}}}$ for
simplicity. Then together with Eq. 2.30, we have

$\displaystyle\left\|\boldsymbol{\lambda}\cdot{\boldsymbol{{\mathcal{W}}}}{\boldsymbol{f}}\right\|_{1}\leq
2^{J}\sum_{l=J-L}^{\infty}2^{\beta
l}\sum_{{\boldsymbol{k}}\in\boldsymbol{\Omega}}\sum_{\boldsymbol{\alpha}\in{\mathbb{B}}}\big{|}\langle
f,\psi_{\boldsymbol{\alpha},l,{\boldsymbol{k}}}\rangle\big{|}=C_{f}2^{J},$

which shows that
$\left\|\boldsymbol{\lambda}\cdot{\boldsymbol{{\mathcal{W}}}}{\boldsymbol{f}}\right\|_{1}\leq
C_{{\boldsymbol{f}}}2^{J}$ with $C_{{\boldsymbol{f}}}=C_{f}$. Hence, since we
have
$\left\|{\boldsymbol{f}}\right\|_{\ell_{\infty}(\boldsymbol{\Omega})}\leq\left\|f\right\|_{L_{\infty}(\Omega)}\leq
M$ by Hölder’s inequality (e.g. [43]), Eq. 2.32 follows from Theorem 2.8 by
setting

$\displaystyle\widetilde{c}=\frac{64M^{2}\left\|{\boldsymbol{{\mathcal{A}}}}\right\|_{\infty}^{2}}{3\sigma_{\min}^{2}({\boldsymbol{{\mathcal{A}}}})}\left[4+3\sqrt{5(4a+\max\\{1-\beta,1\\})C_{{\boldsymbol{{\mathcal{W}}}}}C_{f}(1+C_{{\boldsymbol{{\mathcal{W}}}}}C_{f})}\right]\sqrt{2},$

for some $a\geq 1$, which is independent of $J$, $L$, $\rho$, and $\eta$.

For Eq. 2.33, note that we have

$\displaystyle\left\|u_{J}^{{\boldsymbol{\Lambda}}}-f\right\|_{L_{2}(\Omega)}\leq\left\|u_{J}^{{\boldsymbol{\Lambda}}}-f_{J}\right\|_{L_{2}(\Omega)}+\left\|f_{J}-f\right\|_{L_{2}(\Omega)}\leq\frac{n}{2^{J}}\left\|\boldsymbol{u}^{{\boldsymbol{\Lambda}}}-{\boldsymbol{f}}\right\|_{\ell_{2}(\boldsymbol{\Omega})}+\left\|f_{J}-f\right\|_{L_{2}(\Omega)},$

where the last inequality comes from Eq. 2.35 in Lemma 2.12, and $n$ denotes
the order of $\phi$ (the tensor product B-spline used). Hence, we have

$\displaystyle\left\|u_{J}^{{\boldsymbol{\Lambda}}}-f\right\|_{L_{2}(\Omega)}^{2}\leq
2\left(\frac{n^{2}}{2^{2J}}\left\|\boldsymbol{u}^{{\boldsymbol{\Lambda}}}-{\boldsymbol{f}}\right\|_{\ell_{2}(\boldsymbol{\Omega})}^{2}+\left\|f_{J}-f\right\|_{L_{2}(\Omega)}^{2}\right),$

and by Eq. 2.32, the proof is completed when we estimate
$\left\|f_{J}-f\right\|_{L_{2}(\Omega)}^{2}$. The standard wavelet frame
decomposition gives

$\displaystyle f=\sum_{{\boldsymbol{k}}\in\boldsymbol{\Omega}}\langle
f,\phi_{J,{\boldsymbol{k}}}\rangle\phi_{J,{\boldsymbol{k}}}+\sum_{l=J}^{\infty}\sum_{{\boldsymbol{k}}\in\boldsymbol{\Omega}}\sum_{\boldsymbol{\alpha}\in{\mathbb{B}}}\langle
f,\psi_{\boldsymbol{\alpha},l,{\boldsymbol{k}}}\rangle\psi_{\boldsymbol{\alpha},l,{\boldsymbol{k}}}.$

Then the Bessel property of ${\mathscr{X}}^{J}({\boldsymbol{\Psi}})$ gives

$\displaystyle\left\|f-f_{J}\right\|_{L_{2}(\Omega)}^{2}\leq\sum_{l=J}^{\infty}\sum_{{\boldsymbol{k}}\in\boldsymbol{\Omega}}\sum_{\boldsymbol{\alpha}\in{\mathbb{B}}}\big{|}\langle
f,\psi_{\boldsymbol{\alpha},l,{\boldsymbol{k}}}\rangle\big{|}^{2}.$

Note that by Hölder’s inequality, we have

$\displaystyle\big{|}\langle
f,\psi_{\boldsymbol{\alpha},l,{\boldsymbol{k}}}\rangle\big{|}\leq\left\|f\right\|_{L_{\infty}(\Omega)}\left\|\psi_{\boldsymbol{\alpha},l,{\boldsymbol{k}}}\right\|_{L_{1}({\mathbb{R}}^{2})}=2^{-l}\left\|f\right\|_{L_{\infty}(\Omega)}\left\|\psi_{\boldsymbol{\alpha}}\right\|_{L_{1}({\mathbb{R}}^{2})}\leq
2^{-l}M\left\|\psi_{\boldsymbol{\alpha}}\right\|_{L_{1}({\mathbb{R}}^{2})},$

for all $l\geq J$, and this leads to

$\displaystyle\left\|f-f_{J}\right\|_{L_{2}(\Omega)}^{2}$ $\displaystyle\leq
M\left(\max_{\boldsymbol{\alpha}\in{\mathbb{B}}}\left\|\psi_{\boldsymbol{\alpha}}\right\|_{L_{1}({\mathbb{R}}^{2})}\right)\sum_{l=J}^{\infty}2^{-l}\sum_{{\boldsymbol{k}}\in\boldsymbol{\Omega}}\sum_{\boldsymbol{\alpha}\in{\mathbb{B}}}\big{|}\langle
f,\psi_{\boldsymbol{\alpha},l,{\boldsymbol{k}}}\rangle\big{|}$
$\displaystyle\leq
M\left(\max_{\boldsymbol{\alpha}\in{\mathbb{B}}}\left\|\psi_{\boldsymbol{\alpha}}\right\|_{L_{1}({\mathbb{R}}^{2})}\right)\sum_{l=J}^{\infty}2^{-l}\frac{2^{(\beta+1)l}}{2^{(\beta+1)J}}\sum_{{\boldsymbol{k}}\in\boldsymbol{\Omega}}\sum_{\boldsymbol{\alpha}\in{\mathbb{B}}}\big{|}\langle
f,\psi_{\boldsymbol{\alpha},l,{\boldsymbol{k}}}\rangle\big{|}$
$\displaystyle\leq
M\left(\max_{\boldsymbol{\alpha}\in{\mathbb{B}}}\left\|\psi_{\boldsymbol{\alpha}}\right\|_{L_{1}({\mathbb{R}}^{2})}\right)2^{-(\beta+1)J}\sum_{l=J-L}^{\infty}2^{\beta
l}\sum_{{\boldsymbol{k}}\in\boldsymbol{\Omega}}\sum_{\boldsymbol{\alpha}\in{\mathbb{B}}}\big{|}\langle
f,\psi_{\boldsymbol{\alpha},l,{\boldsymbol{k}}}\rangle\big{|}$
$\displaystyle=C_{f}M\left(\max_{\boldsymbol{\alpha}\in{\mathbb{B}}}\left\|\psi_{\boldsymbol{\alpha}}\right\|_{L_{1}({\mathbb{R}}^{2})}\right)2^{-(\beta+1)J}.$

Therefore, by letting

$\displaystyle
C_{1}=2n^{2}\widetilde{c},~{}~{}C_{2}=\frac{32}{3}\sigma_{\min}^{-2}({\boldsymbol{{\mathcal{A}}}})n^{2},~{}~{}\text{and}~{}~{}C_{3}=2C_{f}M\left(\max_{\boldsymbol{\alpha}\in{\mathbb{B}}}\left\|\psi_{\boldsymbol{\alpha}}\right\|_{L_{1}({\mathbb{R}}^{2})}\right)$

all of which are independent of $J$, $L$, $\rho$, and $\eta$, we obtain Eq.
2.33, and this concludes Theorem 2.10. $\square$

##  3 Technical proofs

This section is devoted to the technical details left in Section 2. More
precisely, we present the proofs of Theorem 2.4, Lemma 2.6, and Theorem 2.7.

###  3.1 Proof of Theorem 2.4

To prove Theorem 2.4, we need some technical lemmas and propositions. The idea
follows the same line as in [18, Theorem 2.3.], which is mainly based on the
idea of statistical learning [29]. However, since our problem involves a
linear operator
${\boldsymbol{{\mathcal{A}}}}\neq{\boldsymbol{{\mathcal{I}}}}$, we still
include the proof for the completeness. We first introduce the following ratio
probability inequality, which can be derived from Bernstein inequality [29,
60].

######  Lemma 3.13.

Assume that a random variable $\xi$ on a probability space ${\mathscr{X}}$
satisfies $\mu:=\mathbb{E}\xi\geq 0$ and $\left|\xi-\mu\right|\leq B$ almost
surely. If $\mathbb{E}\xi^{2}\leq c\mathbb{E}\xi$ for some $c>0$, the
following inequality

$\displaystyle\mathbb{P}\left\\{{\boldsymbol{z}}\in{\mathscr{X}}^{m}:\frac{\mu-\frac{1}{m}\sum_{i=1}^{m}\xi(z_{i})}{\sqrt{\mu+\epsilon}}>\gamma\sqrt{\epsilon}\right\\}\leq\exp\left\\{-\frac{3\gamma^{2}m\epsilon}{6c+2B}\right\\}$

holds for arbitrary $\epsilon>0$ and $0<\gamma\leq 1$.

Let ${\boldsymbol{\zeta}}$ be a random variable which is drawn from the
uniform distribution on $\boldsymbol{\Omega}$. For
$\boldsymbol{u}\in{\mathscr{M}}$, we introduce
$\xi=\left|({\boldsymbol{{\mathcal{A}}}}\boldsymbol{u})[{\boldsymbol{\zeta}}]-({\boldsymbol{{\mathcal{A}}}}{\boldsymbol{f}})[{\boldsymbol{\zeta}}]\right|^{2}$.
Then $\xi$ is a random variable which is drawn from the uniform distribution
on $\boldsymbol{\Omega}$, and satisfies
$0\leq\xi\leq\left\|{\boldsymbol{{\mathcal{A}}}}\right\|_{\infty}^{2}M^{2}$.
Define

$\displaystyle{\mathcal{E}}(\boldsymbol{u})=\mathbb{E}\xi=\mathbb{E}\left(\left|({\boldsymbol{{\mathcal{A}}}}\boldsymbol{u})[{\boldsymbol{\zeta}}]-({\boldsymbol{{\mathcal{A}}}}{\boldsymbol{f}})[{\boldsymbol{\zeta}}]\right|^{2}\right)=\frac{1}{|\boldsymbol{\Omega}|}\sum_{{\boldsymbol{k}}\in\boldsymbol{\Omega}}\left|({\boldsymbol{{\mathcal{A}}}}\boldsymbol{u})[{\boldsymbol{k}}]-({\boldsymbol{{\mathcal{A}}}}{\boldsymbol{f}})[{\boldsymbol{k}}]\right|^{2}.$
(3.1)

We also define ${\mathcal{E}}_{{\boldsymbol{\Lambda}}}(\boldsymbol{u})$ as a
conditional expectation of $\xi$ given ${\boldsymbol{\Lambda}}$:

$\displaystyle{\mathcal{E}}_{{\boldsymbol{\Lambda}}}(\boldsymbol{u})=\mathbb{E}\left(\xi\big{|}{\boldsymbol{\Lambda}}\right)=\frac{1}{|{\boldsymbol{\Lambda}}|}\sum_{{\boldsymbol{k}}\in{\boldsymbol{\Lambda}}}\left|({\boldsymbol{{\mathcal{A}}}}\boldsymbol{u})[{\boldsymbol{k}}]-({\boldsymbol{{\mathcal{A}}}}{\boldsymbol{f}})[{\boldsymbol{k}}]\right|^{2}.$
(3.2)

Then we have the following lemma.

######  Lemma 3.14.

Let ${\mathscr{M}}$ be defined as Eq. 2.18. For
$\boldsymbol{u}_{1},\boldsymbol{u}_{2}\in{\mathscr{M}}$, we have

$\displaystyle\left|{\mathcal{E}}(\boldsymbol{u}_{1})-{\mathcal{E}}(\boldsymbol{u}_{2})\right|$
$\displaystyle\leq
2\left\|{\boldsymbol{{\mathcal{A}}}}\right\|_{\infty}^{2}M\left\|\boldsymbol{u}_{1}-\boldsymbol{u}_{2}\right\|_{\ell_{\infty}(\boldsymbol{\Omega})}$
(3.3)
$\displaystyle\left|{\mathcal{E}}_{{\boldsymbol{\Lambda}}}(\boldsymbol{u}_{1})-{\mathcal{E}}_{{\boldsymbol{\Lambda}}}(\boldsymbol{u}_{2})\right|$
$\displaystyle\leq
2\left\|{\boldsymbol{{\mathcal{A}}}}\right\|_{\infty}^{2}M\left\|\boldsymbol{u}_{1}-\boldsymbol{u}_{2}\right\|_{\ell_{\infty}(\boldsymbol{\Omega})}.$
(3.4)

######  Proof 4.

We have

$\displaystyle\left|{\mathcal{E}}(\boldsymbol{u}_{1})-{\mathcal{E}}(\boldsymbol{u}_{2})\right|$
$\displaystyle=\frac{1}{|\boldsymbol{\Omega}|}\left|\sum_{{\boldsymbol{k}}\in\boldsymbol{\Omega}}\left|({\boldsymbol{{\mathcal{A}}}}\boldsymbol{u}_{1})[{\boldsymbol{k}}]-({\boldsymbol{{\mathcal{A}}}}{\boldsymbol{f}})[{\boldsymbol{k}}]\right|^{2}-\sum_{{\boldsymbol{k}}\in\boldsymbol{\Omega}}\left|({\boldsymbol{{\mathcal{A}}}}\boldsymbol{u}_{2})[{\boldsymbol{k}}]-({\boldsymbol{{\mathcal{A}}}}{\boldsymbol{f}})[{\boldsymbol{k}}]\right|^{2}\right|$
$\displaystyle\leq\frac{1}{|\boldsymbol{\Omega}|}\sum_{{\boldsymbol{k}}\in\boldsymbol{\Omega}}\left|({\boldsymbol{{\mathcal{A}}}}\boldsymbol{u}_{1})[{\boldsymbol{k}}]+({\boldsymbol{{\mathcal{A}}}}\boldsymbol{u}_{2})[{\boldsymbol{k}}]-2({\boldsymbol{{\mathcal{A}}}}{\boldsymbol{f}})[{\boldsymbol{k}}]\right|\left|({\boldsymbol{{\mathcal{A}}}}\boldsymbol{u}_{1})[{\boldsymbol{k}}]-({\boldsymbol{{\mathcal{A}}}}\boldsymbol{u}_{2})[{\boldsymbol{k}}]\right|$
$\displaystyle\leq\frac{1}{|\boldsymbol{\Omega}|}\left\|{\boldsymbol{{\mathcal{A}}}}\left(\boldsymbol{u}_{1}+\boldsymbol{u}_{2}-2{\boldsymbol{f}}\right)\right\|_{\ell_{\infty}(\boldsymbol{\Omega})}\left\|{\boldsymbol{{\mathcal{A}}}}\left(\boldsymbol{u}_{1}-\boldsymbol{u}_{2}\right)\right\|_{\ell_{1}(\boldsymbol{\Omega})}$
$\displaystyle\leq\left\|{\boldsymbol{{\mathcal{A}}}}\left(\boldsymbol{u}_{1}+\boldsymbol{u}_{2}-2{\boldsymbol{f}}\right)\right\|_{\ell_{\infty}(\boldsymbol{\Omega})}\left\|{\boldsymbol{{\mathcal{A}}}}\left(\boldsymbol{u}_{1}-\boldsymbol{u}_{2}\right)\right\|_{\ell_{\infty}(\boldsymbol{\Omega})}$
$\displaystyle\leq
2\left\|{\boldsymbol{{\mathcal{A}}}}\right\|_{\infty}^{2}M\left\|\boldsymbol{u}_{1}-\boldsymbol{u}_{2}\right\|_{\ell_{\infty}(\boldsymbol{\Omega})},$

where we have used the fact that
$\boldsymbol{u}_{1},\boldsymbol{u}_{2},{\boldsymbol{f}}\in[0,M]^{\boldsymbol{\Omega}}$
in the last inequality; that is,
$\left\|\boldsymbol{u}_{1}+\boldsymbol{u}_{2}-2{\boldsymbol{f}}\right\|_{\ell_{\infty}(\boldsymbol{\Omega})}\leq
2M$. Eq. 3.4 can be proved in the similar way by replacing
$\boldsymbol{\Omega}$ with ${\boldsymbol{\Lambda}}$. $\square$

With the aid of Lemmas 3.13 and 3.14, we can present the following ratio
probability inequality involving the space ${\mathscr{M}}$ defined as Eq.
2.18.

######  Proposition 3.15.

Let ${\mathscr{M}}$, ${\mathcal{E}}(\boldsymbol{u})$ and
${\mathcal{E}}_{{\boldsymbol{\Lambda}}}(\boldsymbol{u})$ be respectively
defined as Eq. 2.18, Eq. 3.1, and Eq. 3.2. Then for any $\epsilon>0$ and
$0<\gamma<1$, we have

$\displaystyle\mathbb{P}\left\\{\sup_{\boldsymbol{u}\in{\mathscr{M}}}\frac{{\mathcal{E}}(\boldsymbol{u})-{\mathcal{E}}_{{\boldsymbol{\Lambda}}}(\boldsymbol{u})}{\sqrt{{\mathcal{E}}(\boldsymbol{u})+\epsilon}}>4\gamma\sqrt{\epsilon}\right\\}\leq{\mathcal{N}}\left({\mathscr{M}},\frac{\gamma\epsilon}{2\left\|{\boldsymbol{{\mathcal{A}}}}\right\|_{\infty}^{2}M}\right)\exp\left\\{-\frac{3\gamma^{2}m\epsilon}{8\left\|{\boldsymbol{{\mathcal{A}}}}\right\|_{\infty}^{2}M^{2}}\right\\}$

where ${\mathcal{N}}({\mathscr{M}},r)$ is the covering number of
${\mathscr{M}}$ with respect to
$\left\|\cdot\right\|_{\ell_{\infty}(\boldsymbol{\Omega})}$.

######  Proof 5.

Let
$K={\mathcal{N}}\left({\mathscr{M}},\frac{\gamma\epsilon}{2\left\|{\boldsymbol{{\mathcal{A}}}}\right\|_{\infty}^{2}M}\right)$
and we choose
$\left\\{\boldsymbol{u}_{1},\cdots,\boldsymbol{u}_{K}\right\\}\subseteq{\mathscr{M}}$
such that

$\displaystyle{\mathscr{M}}\subseteq\bigcup_{j=1}^{K}\left\\{\boldsymbol{u}:\left\|\boldsymbol{u}-\boldsymbol{u}_{j}\right\|_{\ell_{\infty}(\boldsymbol{\Omega})}\leq\frac{\gamma\epsilon}{2\left\|{\boldsymbol{{\mathcal{A}}}}\right\|_{\infty}^{2}M}\right\\}.$

For each $j=1,\cdots,K$, we consider the random variable
$\xi=\left|({\boldsymbol{{\mathcal{A}}}}\boldsymbol{u}_{j})[{\boldsymbol{\zeta}}]-({\boldsymbol{{\mathcal{A}}}}{\boldsymbol{f}})[{\boldsymbol{\zeta}}]\right|^{2}$
where ${\boldsymbol{\zeta}}$ is a random variable drawn from the uniform
distribution on $\boldsymbol{\Omega}$. Note that $\xi$ is a random variable on
$\boldsymbol{\Omega}$, and

$\displaystyle\mu=\mathbb{E}\xi=\frac{1}{|\boldsymbol{\Omega}|}\sum_{{\boldsymbol{k}}\in\boldsymbol{\Omega}}\left|({\boldsymbol{{\mathcal{A}}}}\boldsymbol{u}_{j})[{\boldsymbol{k}}]-({\boldsymbol{{\mathcal{A}}}}{\boldsymbol{f}})[{\boldsymbol{k}}]\right|^{2}={\mathcal{E}}(\boldsymbol{u}_{j}).$

Then since $\boldsymbol{u}_{j}$, ${\boldsymbol{f}}\in{\mathscr{M}}$, we have
$0\leq\xi\leq\left\|{\boldsymbol{{\mathcal{A}}}}\right\|_{\infty}^{2}M^{2}$,
$\left|\xi-\mathbb{E}\xi\right|\leq\left\|{\boldsymbol{{\mathcal{A}}}}\right\|_{\infty}^{2}M^{2}$,
and

$\displaystyle\mathbb{E}\xi^{2}=\mathbb{E}\left(\left|({\boldsymbol{{\mathcal{A}}}}\boldsymbol{u}_{j})[{\boldsymbol{\zeta}}]-({\boldsymbol{{\mathcal{A}}}}{\boldsymbol{f}})[{\boldsymbol{\zeta}}]\right|^{4}\right)\leq\left\|{\boldsymbol{{\mathcal{A}}}}\right\|_{\infty}^{2}M^{2}\mathbb{E}\left(\left|({\boldsymbol{{\mathcal{A}}}}\boldsymbol{u}_{j})[{\boldsymbol{\zeta}}]-({\boldsymbol{{\mathcal{A}}}}{\boldsymbol{f}})[{\boldsymbol{\zeta}}]\right|^{2}\right)=\left\|{\boldsymbol{{\mathcal{A}}}}\right\|_{\infty}^{2}M^{2}\mathbb{E}\xi.$

In addition,

$\displaystyle\frac{1}{m}\sum_{{\boldsymbol{k}}\in{\boldsymbol{\Lambda}}}\xi({\boldsymbol{k}})=\frac{1}{|{\boldsymbol{\Lambda}}|}\sum_{{\boldsymbol{k}}\in{\boldsymbol{\Lambda}}}\left|({\boldsymbol{{\mathcal{A}}}}\boldsymbol{u}_{j})[{\boldsymbol{k}}]-({\boldsymbol{{\mathcal{A}}}}{\boldsymbol{f}})[{\boldsymbol{k}}]\right|^{2}={\mathcal{E}}_{{\boldsymbol{\Lambda}}}(\boldsymbol{u}_{j}).$

Applying Lemma 3.13 to $\xi$ with
$B=c=\left\|{\boldsymbol{{\mathcal{A}}}}\right\|_{\infty}^{2}M^{2}$, we have

$\displaystyle\mathbb{P}\left\\{\frac{{\mathcal{E}}(\boldsymbol{u}_{j})-{\mathcal{E}}_{{\boldsymbol{\Lambda}}}(\boldsymbol{u}_{j})}{\sqrt{{\mathcal{E}}(\boldsymbol{u}_{j})+\epsilon}}>\gamma\sqrt{\epsilon}\right\\}\leq\exp\left\\{-\frac{3\gamma^{2}m\epsilon}{8\left\|{\boldsymbol{{\mathcal{A}}}}\right\|_{\infty}^{2}M^{2}}\right\\}.$
(3.5)

For each $\boldsymbol{u}\in{\mathscr{M}}$, we can find $\boldsymbol{u}_{j}$
such that
$\left\|\boldsymbol{u}-\boldsymbol{u}_{j}\right\|_{\infty}\leq\frac{\gamma\epsilon}{2\left\|{\boldsymbol{{\mathcal{A}}}}\right\|_{\infty}^{2}M}$.
Then by Lemma 3.14, we have

$\displaystyle\left|{\mathcal{E}}_{{\boldsymbol{\Lambda}}}(\boldsymbol{u})-{\mathcal{E}}_{{\boldsymbol{\Lambda}}}(\boldsymbol{u}_{j})\right|$
$\displaystyle\leq
2\left\|{\boldsymbol{{\mathcal{A}}}}\right\|_{\infty}^{2}M\left\|\boldsymbol{u}-\boldsymbol{u}_{j}\right\|_{\ell_{\infty}(\boldsymbol{\Omega})}\leq\gamma\epsilon,$
$\displaystyle\left|{\mathcal{E}}(\boldsymbol{u})-{\mathcal{E}}(\boldsymbol{u}_{j})\right|$
$\displaystyle\leq
2\left\|{\boldsymbol{{\mathcal{A}}}}\right\|_{\infty}^{2}M\left\|\boldsymbol{u}-\boldsymbol{u}_{j}\right\|_{\ell_{\infty}(\boldsymbol{\Omega})}\leq\gamma\epsilon.$

In other words,

$\displaystyle\frac{\left|{\mathcal{E}}_{{\boldsymbol{\Lambda}}}(\boldsymbol{u})-{\mathcal{E}}_{{\boldsymbol{\Lambda}}}(\boldsymbol{u}_{j})\right|}{\sqrt{{\mathcal{E}}(\boldsymbol{u})+\epsilon}}\leq\gamma\sqrt{\epsilon}~{}~{}\text{and}~{}~{}\frac{\left|{\mathcal{E}}(\boldsymbol{u})-{\mathcal{E}}(\boldsymbol{u}_{j})\right|}{\sqrt{{\mathcal{E}}(\boldsymbol{u})+\epsilon}}\leq\gamma\sqrt{\epsilon}.$

In particular, the second inequality implies that

$\displaystyle{\mathcal{E}}(\boldsymbol{u}_{j})+\epsilon$
$\displaystyle={\mathcal{E}}(\boldsymbol{u}_{j})-{\mathcal{E}}(\boldsymbol{u})+{\mathcal{E}}(\boldsymbol{u})+\epsilon\leq\gamma\sqrt{\epsilon}\sqrt{{\mathcal{E}}(\boldsymbol{u})+\epsilon}+{\mathcal{E}}(\boldsymbol{u})+\epsilon$
$\displaystyle\leq\sqrt{\epsilon}\sqrt{{\mathcal{E}}(\boldsymbol{u})+\epsilon}\leq\frac{{\mathcal{E}}(\boldsymbol{u})+2\epsilon}{2}+{\mathcal{E}}(\boldsymbol{u})+\epsilon\leq
2\left({\mathcal{E}}(\boldsymbol{u})+\epsilon\right).$

Hence, for an arbitrary $\boldsymbol{u}\in{\mathscr{M}}$ with
$\left\|\boldsymbol{u}-\boldsymbol{u}_{j}\right\|_{\ell_{\infty}(\boldsymbol{\Omega})}\leq\frac{\gamma\epsilon}{2\left\|{\boldsymbol{{\mathcal{A}}}}\right\|_{\infty}^{2}M}$,
we have $\sqrt{{\mathcal{E}}(\boldsymbol{u}_{j})+\epsilon}\leq
2\sqrt{{\mathcal{E}}(\boldsymbol{u})+\epsilon}$.

Given that
$\frac{{\mathcal{E}}(\boldsymbol{u})-{\mathcal{E}}_{{\boldsymbol{\Lambda}}}(\boldsymbol{u})}{\sqrt{{\mathcal{E}}(\boldsymbol{u})+\epsilon}}>4\gamma\sqrt{\epsilon}$,
we have

$\displaystyle\frac{{\mathcal{E}}(\boldsymbol{u}_{j})-{\mathcal{E}}_{{\boldsymbol{\Lambda}}}(\boldsymbol{u}_{j})}{2\sqrt{{\mathcal{E}}(\boldsymbol{u})+\epsilon}}$
$\displaystyle\geq\frac{{\mathcal{E}}(\boldsymbol{u}_{j})-{\mathcal{E}}(\boldsymbol{u})}{2\sqrt{{\mathcal{E}}(\boldsymbol{u})+\epsilon}}+\frac{{\mathcal{E}}(\boldsymbol{u})-{\mathcal{E}}_{{\boldsymbol{\Lambda}}}(\boldsymbol{u})}{2\sqrt{{\mathcal{E}}(\boldsymbol{u})+\epsilon}}+\frac{{\mathcal{E}}_{{\boldsymbol{\Lambda}}}(\boldsymbol{u})-{\mathcal{E}}_{{\boldsymbol{\Lambda}}}(\boldsymbol{u}_{j})}{2\sqrt{{\mathcal{E}}(\boldsymbol{u})+\epsilon}}$
$\displaystyle>-\frac{\gamma\sqrt{\epsilon}}{2}+2\gamma\sqrt{\epsilon}-\frac{\gamma\sqrt{\epsilon}}{2}=\gamma\sqrt{\epsilon}.$

Then since we have $\sqrt{{\mathcal{E}}(\boldsymbol{u}_{j})+\epsilon}\leq
2\sqrt{{\mathcal{E}}(\boldsymbol{u})+\epsilon}$ for any
$\boldsymbol{u}\in{\mathscr{M}}$ with
$\left\|\boldsymbol{u}-\boldsymbol{u}_{j}\right\|_{\infty}\leq\frac{\gamma\epsilon}{2\left\|{\boldsymbol{{\mathcal{A}}}}\right\|_{\infty}^{2}M}$,
it follows that if
$\frac{{\mathcal{E}}(\boldsymbol{u})-{\mathcal{E}}_{{\boldsymbol{\Lambda}}}(\boldsymbol{u})}{\sqrt{{\mathcal{E}}(\boldsymbol{u})+\epsilon}}>4\gamma\sqrt{\epsilon}$
holds, then the following inequality

$\displaystyle\frac{{\mathcal{E}}(\boldsymbol{u}_{j})-{\mathcal{E}}_{{\boldsymbol{\Lambda}}}(\boldsymbol{u}_{j})}{\sqrt{{\mathcal{E}}(\boldsymbol{u}_{j})+\epsilon}}\geq\frac{{\mathcal{E}}(\boldsymbol{u}_{j})-{\mathcal{E}}_{{\boldsymbol{\Lambda}}}(\boldsymbol{u})}{2\sqrt{{\mathcal{E}}(\boldsymbol{u})+\epsilon}}>\gamma\sqrt{\epsilon}$

holds. Hence, for each fixed $j=1,\cdots,K$,

$\displaystyle\mathbb{P}\left\\{\sup_{\boldsymbol{u}\in\\{\left\|\boldsymbol{u}-\boldsymbol{u}_{j}\right\|_{\ell_{\infty}(\boldsymbol{\Omega})}\leq\frac{\gamma\epsilon}{2\left\|{\boldsymbol{{\mathcal{A}}}}\right\|_{\infty}^{2}M}\\}}\frac{{\mathcal{E}}(\boldsymbol{u})-{\mathcal{E}}_{{\boldsymbol{\Lambda}}}(\boldsymbol{u})}{\sqrt{{\mathcal{E}}(\boldsymbol{u})+\epsilon}}>4\gamma\sqrt{\epsilon}\right\\}\leq\mathbb{P}\left\\{\frac{{\mathcal{E}}(\boldsymbol{u}_{j})-{\mathcal{E}}_{{\boldsymbol{\Lambda}}}(\boldsymbol{u}_{j})}{\sqrt{{\mathcal{E}}(\boldsymbol{u}_{j})+\epsilon}}>\gamma\sqrt{\epsilon}\right\\}.$

Then since
${\mathscr{M}}\subseteq\cup_{j=1}^{K}\left\\{\boldsymbol{u}:\left\|\boldsymbol{u}-\boldsymbol{u}_{j}\right\|_{\ell_{\infty}(\boldsymbol{\Omega})}\leq\frac{\gamma\epsilon}{2\left\|{\boldsymbol{{\mathcal{A}}}}\right\|_{\infty}^{2}M}\right\\}$,
together with Eq. 3.5, we have

$\displaystyle\mathbb{P}\left\\{\sup_{\boldsymbol{u}\in{\mathscr{M}}}\frac{{\mathcal{E}}(\boldsymbol{u})-{\mathcal{E}}_{{\boldsymbol{\Lambda}}}(\boldsymbol{u})}{\sqrt{{\mathcal{E}}(\boldsymbol{u})+\epsilon}}>4\gamma\sqrt{\epsilon}\right\\}$
$\displaystyle\leq\sum_{j=1}^{K}\mathbb{P}\left\\{\sup_{\boldsymbol{u}\in\\{\left\|\boldsymbol{u}-\boldsymbol{u}_{j}\right\|_{\ell_{\infty}(\boldsymbol{\Omega})}\leq\frac{\gamma\epsilon}{2\left\|{\boldsymbol{{\mathcal{A}}}}\right\|_{\infty}^{2}M}\\}}\frac{{\mathcal{E}}(\boldsymbol{u})-{\mathcal{E}}_{{\boldsymbol{\Lambda}}}(\boldsymbol{u})}{\sqrt{{\mathcal{E}}(\boldsymbol{u})+\epsilon}}>4\gamma\sqrt{\epsilon}\right\\}$
$\displaystyle\leq\sum_{j=1}^{K}\mathbb{P}\left\\{\frac{{\mathcal{E}}(\boldsymbol{u}_{j})-{\mathcal{E}}_{{\boldsymbol{\Lambda}}}(\boldsymbol{u}_{j})}{\sqrt{{\mathcal{E}}(\boldsymbol{u}_{j})+\epsilon}}>\gamma\sqrt{\epsilon}\right\\}$
$\displaystyle\leq{\mathcal{N}}\left({\mathscr{M}},\frac{\gamma\epsilon}{2\left\|{\boldsymbol{{\mathcal{A}}}}\right\|_{\infty}^{2}M}\right)\exp\left\\{-\frac{3\gamma^{2}m\epsilon}{8\left\|{\boldsymbol{{\mathcal{A}}}}\right\|_{\infty}^{2}M^{2}}\right\\}.$

This concludes Proposition 3.15. $\square$

Now, we can provide the proof of Theorem 2.4.

######  Proof of Theorem 2.4 1.

By Proposition 3.15, for arbitrary $\epsilon>0$ and $0<\gamma<1$, the
inequality

$\displaystyle\sup_{\boldsymbol{u}\in{\mathscr{M}}}\frac{{\mathcal{E}}(\boldsymbol{u})-{\mathcal{E}}_{{\boldsymbol{\Lambda}}}(\boldsymbol{u})}{\sqrt{{\mathcal{E}}(\boldsymbol{u})+\epsilon}}\leq
4\gamma\sqrt{\epsilon}$

holds with probability at least

$\displaystyle
1-{\mathcal{N}}\left({\mathscr{M}},\frac{\gamma\epsilon}{2\left\|{\boldsymbol{{\mathcal{A}}}}\right\|_{\infty}^{2}M}\right)\exp\left\\{-\frac{3\gamma^{2}m\epsilon}{8\left\|{\boldsymbol{{\mathcal{A}}}}\right\|_{\infty}^{2}M^{2}}\right\\}.$

Therefore, for all $\boldsymbol{u}\in{\mathscr{M}}$, the inequality

$\displaystyle{\mathcal{E}}(\boldsymbol{u})-{\mathcal{E}}_{{\boldsymbol{\Lambda}}}(\boldsymbol{u})\leq
4\gamma\sqrt{\epsilon}\sqrt{{\mathcal{E}}(\boldsymbol{u})+\epsilon}$ (3.6)

holds with the same probability. Then by taking $\gamma=\sqrt{2}/8$ and
$\boldsymbol{u}=\boldsymbol{u}^{{\boldsymbol{\Lambda}}}\in{\mathscr{M}}$ in
Eq. 3.6, it follows that

$\displaystyle{\mathcal{E}}\left(\boldsymbol{u}^{{\boldsymbol{\Lambda}}}\right)-{\mathcal{E}}_{{\boldsymbol{\Lambda}}}\left(\boldsymbol{u}^{{\boldsymbol{\Lambda}}}\right)\leq\frac{1}{2}\sqrt{2\epsilon\left({\mathcal{E}}\left(\boldsymbol{u}^{{\boldsymbol{\Lambda}}}\right)+\epsilon\right)}$
(3.7)

holds with probability at least
$1-{\mathcal{N}}\left({\mathscr{M}},\frac{\epsilon}{8\sqrt{2}\left\|{\boldsymbol{{\mathcal{A}}}}\right\|_{\infty}^{2}M}\right)\exp\left\\{-\frac{3m\epsilon}{256\left\|{\boldsymbol{{\mathcal{A}}}}\right\|_{\infty}^{2}M^{2}}\right\\}$.
Besides, since

$\displaystyle{\mathcal{E}}_{{\boldsymbol{\Lambda}}}\left(\boldsymbol{u}^{{\boldsymbol{\Lambda}}}\right)\leq\frac{2}{|{\boldsymbol{\Lambda}}|}\sum_{{\boldsymbol{k}}\in{\boldsymbol{\Lambda}}}\left|({\boldsymbol{{\mathcal{A}}}}\boldsymbol{u}^{{\boldsymbol{\Lambda}}})[{\boldsymbol{k}}]-{\boldsymbol{g}}[{\boldsymbol{k}}]\right|^{2}+\frac{2}{|{\boldsymbol{\Lambda}}|}\sum_{{\boldsymbol{k}}\in{\boldsymbol{\Lambda}}}\left|{\boldsymbol{g}}[{\boldsymbol{k}}]-({\boldsymbol{{\mathcal{A}}}}{\boldsymbol{f}})[{\boldsymbol{k}}]\right|^{2}\leq
4\eta^{2},$ (3.8)

combining Eq. 3.7 and Eq. 3.8 yields

$\displaystyle{\mathscr{E}}\left(\boldsymbol{u}^{{\boldsymbol{\Lambda}}}\right)\leq\frac{1}{2}\sqrt{2\epsilon\left({\mathcal{E}}\left(\boldsymbol{u}^{{\boldsymbol{\Lambda}}}\right)+\epsilon\right)}+4\eta^{2}.$

Noting that
${\mathcal{N}}\left({\mathscr{M}},\frac{\epsilon}{8\sqrt{2}\left\|{\boldsymbol{{\mathcal{A}}}}\right\|_{\infty}^{2}M}\right)\leq{\mathcal{N}}\left({\mathscr{M}},\frac{\epsilon}{12\left\|{\boldsymbol{{\mathcal{A}}}}\right\|_{\infty}^{2}M}\right)$,
we have

$\displaystyle\mathbb{P}\left\\{{\mathcal{E}}\left(\boldsymbol{u}^{{\boldsymbol{\Lambda}}}\right)\leq\epsilon+\frac{16}{3}\eta^{2}\right\\}\geq
1-{\mathcal{N}}\left({\mathscr{M}},\frac{\epsilon}{12\left\|{\boldsymbol{{\mathcal{A}}}}\right\|_{\infty}^{2}M}\right)\exp\left\\{-\frac{3m\epsilon}{256\left\|{\boldsymbol{{\mathcal{A}}}}\right\|_{\infty}^{2}M^{2}}\right\\}.$

Finally, since

$\displaystyle\frac{1}{|\boldsymbol{\Omega}|}\left\|\boldsymbol{u}^{{\boldsymbol{\Lambda}}}-{\boldsymbol{f}}\right\|_{\ell_{2}(\boldsymbol{\Omega})}^{2}\leq\frac{\sigma_{\min}^{-2}({\boldsymbol{{\mathcal{A}}}})}{|\boldsymbol{\Omega}|}\sum_{{\boldsymbol{k}}\in\boldsymbol{\Omega}}\left|({\boldsymbol{{\mathcal{A}}}}\boldsymbol{u}^{{\boldsymbol{\Lambda}}})[{\boldsymbol{k}}]-({\boldsymbol{{\mathcal{A}}}}{\boldsymbol{f}})[{\boldsymbol{k}}]\right|^{2}=\sigma_{\min}^{-2}({\boldsymbol{{\mathcal{A}}}}){\mathcal{E}}\left(\boldsymbol{u}^{{\boldsymbol{\Lambda}}}\right),$

we therefore have

$\displaystyle\mathbb{P}\left\\{\frac{1}{|\boldsymbol{\Omega}|}\left\|\boldsymbol{u}^{{\boldsymbol{\Lambda}}}-{\boldsymbol{f}}\right\|_{\ell_{2}(\boldsymbol{\Omega})}^{2}\leq\epsilon+\frac{16}{3}\sigma_{\min}^{-2}({\boldsymbol{{\mathcal{A}}}})\eta^{2}\right\\}$
$\displaystyle\geq\mathbb{P}\left\\{{\mathcal{E}}\left(\boldsymbol{u}^{{\boldsymbol{\Lambda}}}\right)\leq\sigma_{\min}^{2}({\boldsymbol{{\mathcal{A}}}})\epsilon+\frac{16}{3}\eta^{2}\right\\}$
$\displaystyle\geq
1-{\mathcal{N}}\left({\mathscr{M}},\frac{\sigma_{\min}^{2}({\boldsymbol{{\mathcal{A}}}})\epsilon}{12\left\|{\boldsymbol{{\mathcal{A}}}}\right\|_{\infty}^{2}M}\right)\exp\left\\{-\frac{3m\sigma_{\min}^{2}({\boldsymbol{{\mathcal{A}}}})\epsilon}{256\left\|{\boldsymbol{{\mathcal{A}}}}\right\|_{\infty}^{2}M^{2}}\right\\}.$

This concludes Theorem 2.4. $\square$

###  3.2 Proof of Lemma 2.6

Before we prove Lemma 2.6, we first mention that the authors in [18] have
presented the similar results for the generic MRA based wavelet frame systems,
using the convergence rate of a stationary subdivision algorithm [22, 48, 61].
However, since our definition of $\ell_{1}$-norm of wavelet frame coefficients
does not include the low-pass filter coefficients, our proof is based on the
technique different from [18]. In fact, since we restrict ourselves to the
tensor product B-spline wavelet frame systems, our proof follows the line
described in [63], based on the definition of B-spline wavelet frame system in
[55].

We denote respectively by
$\boldsymbol{p}=\left[\begin{array}[]{cc}1&1\end{array}\right]$ one
dimensional $1$st order average filter and by
$\boldsymbol{q}=\left[\begin{array}[]{cc}1&-1\end{array}\right]$ one
dimensional $1$st order difference filter. Then we note that for
$\boldsymbol{u}\in{\mathbb{R}}^{\boldsymbol{\Omega}}$, the direct computation
gives

$\displaystyle\left\|\nabla\boldsymbol{u}\right\|_{1}\leq\left\|\boldsymbol{q}_{{\boldsymbol{e}}_{1}}[-\cdot]\circledast\boldsymbol{u}\right\|_{\ell_{1}(\boldsymbol{\Omega})}+\left\|\boldsymbol{q}_{{\boldsymbol{e}}_{2}}[-\cdot]\circledast\boldsymbol{u}\right\|_{\ell_{1}(\boldsymbol{\Omega})}$
(3.9)

where $\left\|\boldsymbol{\nabla}\boldsymbol{u}\right\|_{1}$ is defined as Eq.
2.21, and the convolution $\circledast$ is defined as Eq. 2.12. In Eq. 3.9,
$\boldsymbol{q}_{{\boldsymbol{e}}_{1}}$ and
$\boldsymbol{q}_{{\boldsymbol{e}}_{2}}$ with the standard basis
$\left\\{{\boldsymbol{e}}_{1},{\boldsymbol{e}}_{2}\right\\}$ for
${\mathbb{R}}^{2}$ is defined as

$\displaystyle\boldsymbol{q}_{{\boldsymbol{e}}_{1}}[{\boldsymbol{k}}]=\boldsymbol{q}[k_{1}]\boldsymbol{\delta}[k_{2}]~{}~{}~{}\text{and}~{}~{}~{}\boldsymbol{q}_{{\boldsymbol{e}}_{2}}[{\boldsymbol{k}}]=\boldsymbol{\delta}[k_{1}]\boldsymbol{q}[k_{2}]$
(3.10)

where $\boldsymbol{\delta}$ is the one dimensional discrete Dirac delta;
$\boldsymbol{\delta}[k]=1$ for $k=0$, and $\boldsymbol{\delta}[k]=0$ for
$k\neq 0$.

Now, we note that for $L\geq 1$, we have

$\displaystyle\sum_{{\boldsymbol{k}}\in\boldsymbol{\Omega}}\sum_{\boldsymbol{\alpha}\in{\mathbb{B}}}\left|\big{(}{\boldsymbol{{\mathcal{W}}}}_{0,\boldsymbol{\alpha}}\boldsymbol{u}\big{)}[{\boldsymbol{k}}]\right|\leq\sum_{{\boldsymbol{k}}\in\boldsymbol{\Omega}}\sum_{l=0}^{L-1}\sum_{\boldsymbol{\alpha}\in{\mathbb{B}}}\left|\big{(}{\boldsymbol{{\mathcal{W}}}}_{l,\boldsymbol{\alpha}}\boldsymbol{u}\big{)}[{\boldsymbol{k}}]\right|.$

Hence, Eq. 3.9 tells us that, if we find $C>0$ independent of $J$ such that

$\displaystyle\left\|\boldsymbol{q}_{{\boldsymbol{e}}_{1}}[-\cdot]\circledast\boldsymbol{u}\right\|_{\ell_{1}(\boldsymbol{\Omega})}+\left\|\boldsymbol{q}_{{\boldsymbol{e}}_{2}}[-\cdot]\circledast\boldsymbol{u}\right\|_{\ell_{1}(\boldsymbol{\Omega})}\leq
C\sum_{{\boldsymbol{k}}\in\boldsymbol{\Omega}}\sum_{\boldsymbol{\alpha}\in{\mathbb{B}}}\left|\big{(}{\boldsymbol{{\mathcal{W}}}}_{0,\boldsymbol{\alpha}}\boldsymbol{u}\big{)}[{\boldsymbol{k}}]\right|,$
(3.11)

we obtain Eq. 2.22, by simply setting
$C_{{\boldsymbol{{\mathcal{W}}}}}=\max\left\\{C,1\right\\}$.

Recall that the first equality of UEP Eq. 2.8 is rewritten as

$\displaystyle\sum_{\boldsymbol{\alpha}\in{\mathbb{B}}\cup\\{{\mathbf{0}}\\}}\left({\boldsymbol{a}}_{\boldsymbol{\alpha}}\ast{\boldsymbol{a}}_{\boldsymbol{\alpha}}[-\cdot]\right)[{\boldsymbol{k}}]=\boldsymbol{\delta}[{\boldsymbol{k}}]=\left\\{\begin{array}[]{rl}1{}&\text{if}~{}{\boldsymbol{k}}={\mathbf{0}};\\\
0{}&\text{if}~{}{\boldsymbol{k}}\neq{\mathbf{0}},\end{array}\right.$

where $\ast$ is the standard discrete convolution on ${\mathbb{Z}}^{2}$. Then
for $j=1,2$, we have

$\displaystyle\boldsymbol{q}_{{\boldsymbol{e}}_{j}}[-\cdot]\circledast\boldsymbol{u}=\sum_{\boldsymbol{\alpha}\in{\mathbb{B}}\cup\\{{\mathbf{0}}\\}}\left({\boldsymbol{a}}_{\boldsymbol{\alpha}}\ast{\boldsymbol{a}}_{\boldsymbol{\alpha}}[-\cdot]\right)\ast\boldsymbol{q}_{{\boldsymbol{e}}_{j}}[-\cdot]\circledast\boldsymbol{u},$

and by the discrete Young’s inequality (e.g. [8]), we have

$\displaystyle\left\|\boldsymbol{q}_{{\boldsymbol{e}}_{j}}[-\cdot]\circledast\boldsymbol{u}\right\|_{\ell_{1}(\boldsymbol{\Omega})}\leq\sum_{\boldsymbol{\alpha}\in{\mathbb{B}}\cup\\{{\mathbf{0}}\\}}\left\|{\boldsymbol{a}}_{\boldsymbol{\alpha}}\right\|_{\ell_{1}({\mathbb{Z}}^{2})}\left\|{\boldsymbol{a}}_{\boldsymbol{\alpha}}[-\cdot]\ast\boldsymbol{q}_{{\boldsymbol{e}}_{j}}[-\cdot]\circledast\boldsymbol{u}\right\|_{\ell_{1}(\boldsymbol{\Omega})}.$
(3.12)

From the definition of B-spline wavelet frame system, the Fourier series of
one dimensional filters ${\boldsymbol{a}}_{\alpha}$ is

$\displaystyle\widehat{{\boldsymbol{a}}}_{{\mathbf{0}}}(\xi)$
$\displaystyle=e^{-ij_{r}\frac{\xi}{2}}\cos^{r}\left(\frac{\xi_{1}}{2}\right),$
(3.13) $\displaystyle\widehat{{\boldsymbol{a}}}_{\alpha}(\xi)$
$\displaystyle=-i^{\alpha}e^{-ij_{r}\frac{\xi}{2}}\sqrt{\binom{r}{\alpha}}\cos^{r-\alpha}\left(\frac{\xi}{2}\right)\sin^{\alpha}\left(\frac{\xi}{2}\right),~{}~{}~{}~{}~{}\alpha=1,\cdots,r$
(3.14)

where $j_{r}=1$ if $r$ is odd; $j_{r}=0$ if $r$ is even. Noting that the
Fourier series of $\boldsymbol{p}$ and $\boldsymbol{q}$ are

$\displaystyle\widehat{\boldsymbol{p}}(\xi)=2e^{-i\frac{\xi}{2}}\cos\left(\frac{\xi}{2}\right),~{}~{}~{}~{}~{}\text{and}~{}~{}~{}~{}~{}\widehat{\boldsymbol{q}}(\xi)=-2ie^{i\frac{\xi}{2}}\sin\left(\frac{\xi}{2}\right),$

we define $\boldsymbol{p}^{\alpha}$ and $\boldsymbol{q}^{\alpha}$ with
$\alpha\in{\mathbb{N}}$ as

$\displaystyle\boldsymbol{p}^{\alpha}=\underbrace{\boldsymbol{p}\ast\boldsymbol{p}\ast\cdots\ast\boldsymbol{p}}_{\alpha\text{
times}}~{}~{}~{}~{}\text{and}~{}~{}~{}~{}\boldsymbol{q}^{\alpha}=\underbrace{\boldsymbol{q}\ast\boldsymbol{q}\ast\cdots\ast\boldsymbol{q}}_{\alpha\text{
times}},$

and we set $\boldsymbol{p}^{0}=\boldsymbol{q}^{0}=\boldsymbol{\delta}$, the
one dimensional discrete Dirac delta. Then by Eqs. 3.13 and 3.14, we have

$\displaystyle{\boldsymbol{a}}_{0}[k]$
$\displaystyle=2^{-r}\boldsymbol{p}^{r}[k-j_{r}]$ (3.15)
$\displaystyle{\boldsymbol{a}}_{\alpha}[k]$
$\displaystyle=(-1)^{\alpha+1}2^{-r}\sqrt{\binom{r}{\alpha}}\boldsymbol{p}^{r-\alpha}\ast\boldsymbol{q}^{\alpha}[k-j_{r}],~{}~{}\alpha=1,\cdots,r.$
(3.16)

Using Eqs. 3.15 and 3.16 and the discrete Young’s inequality, we have

$\displaystyle\left\|{\boldsymbol{a}}_{{\mathbf{0}}}\right\|_{\ell_{1}({\mathbb{Z}}^{2})}=1~{}~{}~{}~{}~{}\text{and}~{}~{}~{}~{}~{}\left\|{\boldsymbol{a}}_{\boldsymbol{\alpha}}\right\|_{\ell_{1}({\mathbb{Z}}^{2})}\leq\sqrt{\binom{{\boldsymbol{r}}}{\boldsymbol{\alpha}}}~{}~{}~{}~{}\boldsymbol{\alpha}\in{\mathbb{B}},$

where ${\boldsymbol{r}}=(r,r)$,
$\binom{\boldsymbol{\alpha}}{\boldsymbol{\beta}}=\binom{\alpha_{1}}{\beta_{1}}\binom{\alpha_{2}}{\beta_{2}}$
for multi-indices $\boldsymbol{\alpha}=(\alpha_{1},\alpha_{2})$,
$\boldsymbol{\beta}=(\beta_{1},\beta_{2})$, and the first equality comes from
the fact that
$\widehat{{\boldsymbol{a}}}_{{\mathbf{0}}}({\mathbf{0}})=\sum{\boldsymbol{a}}_{{\mathbf{0}}}[{\boldsymbol{k}}]=1$.
From $\binom{r}{0}=1$, Eq. 3.12 becomes

$\displaystyle\left\|\boldsymbol{q}_{{\boldsymbol{e}}_{j}}[-\cdot]\circledast\boldsymbol{u}\right\|_{\ell_{1}(\boldsymbol{\Omega})}\leq\sum_{\boldsymbol{\alpha}\in{\mathbb{B}}\cup\\{{\mathbf{0}}\\}}\sqrt{\binom{{\boldsymbol{r}}}{\boldsymbol{\alpha}}}\left\|{\boldsymbol{a}}_{\boldsymbol{\alpha}}[-\cdot]\ast\boldsymbol{q}_{{\boldsymbol{e}}_{j}}[-\cdot]\circledast\boldsymbol{u}\right\|_{\ell_{1}(\boldsymbol{\Omega})}.$

It is obvious that, for $\boldsymbol{\alpha}\in{\mathbb{B}}$, we have

$\displaystyle\left\|{\boldsymbol{a}}_{\boldsymbol{\alpha}}[-\cdot]\ast\boldsymbol{q}_{{\boldsymbol{e}}_{j}}[-\cdot]\circledast\boldsymbol{u}\right\|_{\ell_{1}(\boldsymbol{\Omega})}\leq\left\|\boldsymbol{q}_{{\boldsymbol{e}}_{j}}[-\cdot]\right\|_{\ell_{1}({\mathbb{Z}})}\left\|{\boldsymbol{a}}_{\boldsymbol{\alpha}}[-\cdot]\circledast\boldsymbol{u}\right\|_{\ell_{1}(\boldsymbol{\Omega})}=2\left\|{\boldsymbol{{\mathcal{W}}}}_{0,\boldsymbol{\alpha}}\boldsymbol{u}\right\|_{\ell_{1}(\boldsymbol{\Omega})}$

by the discrete Young’s inequality. Hence, we need to bound
$\left\|{\boldsymbol{a}}_{{\mathbf{0}}}[-\cdot]\ast\boldsymbol{q}_{{\boldsymbol{e}}_{j}}[-\cdot]\circledast\boldsymbol{u}\right\|_{\ell_{1}(\boldsymbol{\Omega})}$
by using
$\left\|{\boldsymbol{{\mathcal{W}}}}_{0,\boldsymbol{\alpha}}\boldsymbol{u}\right\|_{\ell_{1}(\boldsymbol{\Omega})}$
for some suitable $\boldsymbol{\alpha}\in{\mathbb{B}}$. To do this, we first
note that

$\displaystyle{\boldsymbol{a}}_{0}\ast\boldsymbol{q}[k]=r^{-\frac{1}{2}}\boldsymbol{p}\ast{\boldsymbol{a}}_{1}[k-j_{r}].$

Then by the discrete Young’s inequality, we have

$\displaystyle\left\|{\boldsymbol{a}}_{{\mathbf{0}}}[-\cdot]\ast\boldsymbol{q}_{{\boldsymbol{e}}_{j}}[-\cdot]\circledast\boldsymbol{u}\right\|_{\ell_{1}(\boldsymbol{\Omega})}\leq\frac{2}{\sqrt{r}}\left\|{\boldsymbol{a}}_{{\boldsymbol{e}}_{j}}[-\cdot]\circledast\boldsymbol{u}\right\|_{\ell_{1}(\boldsymbol{\Omega})}=\frac{2}{\sqrt{r}}\left\|{\boldsymbol{{\mathcal{W}}}}_{0,{\boldsymbol{e}}_{j}}\boldsymbol{u}\right\|_{\ell_{1}(\boldsymbol{\Omega})}.$

Combining these altogether, we have

$\displaystyle\left\|\boldsymbol{q}_{{\boldsymbol{e}}_{1}}[-\cdot]\circledast\boldsymbol{u}\right\|_{\ell_{1}(\boldsymbol{\Omega})}$
$\displaystyle+\left\|\boldsymbol{q}_{{\boldsymbol{e}}_{2}}[-\cdot]\circledast\boldsymbol{u}\right\|_{\ell_{1}(\boldsymbol{\Omega})}$
$\displaystyle\leq
4\sum_{\boldsymbol{\alpha}\in{\mathbb{B}}}\sqrt{\binom{{\boldsymbol{r}}}{\boldsymbol{\alpha}}}\left\|{\boldsymbol{{\mathcal{W}}}}_{0,\boldsymbol{\alpha}}\boldsymbol{u}\right\|_{\ell_{1}(\boldsymbol{\Omega})}+\frac{2}{\sqrt{r}}\left\|{\boldsymbol{{\mathcal{W}}}}_{0,{\boldsymbol{e}}_{1}}\boldsymbol{u}\right\|_{\ell_{1}(\boldsymbol{\Omega})}+\frac{2}{\sqrt{r}}\left\|{\boldsymbol{{\mathcal{W}}}}_{0,{\boldsymbol{e}}_{2}}\boldsymbol{u}\right\|_{\ell_{1}(\boldsymbol{\Omega})}$
$\displaystyle\leq
6\sum_{\boldsymbol{\alpha}\in{\mathbb{B}}}\sqrt{\binom{{\boldsymbol{r}}}{\boldsymbol{\alpha}}}\left\|{\boldsymbol{{\mathcal{W}}}}_{0,\boldsymbol{\alpha}}\boldsymbol{u}\right\|_{\ell_{1}(\boldsymbol{\Omega})},$

where the last inequality follows from the fact that $r\geq 1$ and
$\binom{r}{\alpha}\geq 1$. Therefore, letting

$\displaystyle
C=6\max_{\boldsymbol{\alpha}\in{\mathbb{B}}}\sqrt{\binom{{\boldsymbol{r}}}{\boldsymbol{\alpha}}},$

we obtain Eq. 3.11, and this concludes Lemma 2.6.

###  3.3 Proof of Theorem 2.7

Theorem 2.7 is to estimate the covering number. The proof follows the line
similar to [18, Theorem 2.4]. However, since we improve [18, Theorem 2.4] by
relaxing the constraint of the radius $r$, we include the detailed proof for
the sake of completeness. It is obvious that if
$\boldsymbol{u}\in[0,M]^{\boldsymbol{\Omega}}$, then
$\left\|\boldsymbol{u}\right\|_{\ell_{\infty}(\boldsymbol{\Omega})}\leq M$. In
addition, if A2 is satisfied, together with the definition of ${\mathscr{M}}$
in Eq. 2.18 and Lemma 2.6, we have

$\displaystyle\left\|\boldsymbol{\nabla}\boldsymbol{u}\right\|_{1}\leq
C_{{\boldsymbol{{\mathcal{W}}}}}\left\|{\boldsymbol{{\mathcal{W}}}}\boldsymbol{u}\right\|_{1}\leq
C_{{\boldsymbol{{\mathcal{W}}}}}2^{\max\\{-\beta,0\\}\max\\{\Upsilon(l,\boldsymbol{\alpha},{\boldsymbol{k}}):(l,\boldsymbol{\alpha},{\boldsymbol{k}})\in\Gamma\\}}\left\|\boldsymbol{\lambda}\cdot{\boldsymbol{{\mathcal{W}}}}\boldsymbol{u}\right\|_{1}.$

Since $\Upsilon:\Gamma\to{\mathbb{N}}$ satisfies Eq. 2.17, for
$\boldsymbol{u}\in{\mathscr{M}}$, we have

$\displaystyle\left\|\boldsymbol{\nabla}\boldsymbol{u}\right\|_{1}\leq
C_{{\boldsymbol{{\mathcal{W}}}}}|\boldsymbol{\Omega}|^{\frac{\max\\{-\beta,0\\}}{2}}\left\|\boldsymbol{\lambda}\cdot{\boldsymbol{{\mathcal{W}}}}{\boldsymbol{f}}\right\|_{1}.$

In other words, ${\mathscr{M}}\subseteq\widetilde{{\mathscr{M}}}$ and
${\mathcal{N}}\left({\mathscr{M}},r\right)\leq{\mathcal{N}}\left(\widetilde{{\mathscr{M}}},r\right)$
where $\widetilde{{\mathscr{M}}}$ is defined as Eq. 2.23. Hence, it suffices
to bound the covering number
${\mathcal{N}}\left(\widetilde{{\mathscr{M}}},r\right)$. In addition, it is
easy to see that if there exists a finite set
$F\subseteq\widetilde{{\mathscr{M}}}$ such that

$\displaystyle\widetilde{{\mathscr{M}}}\subseteq\bigcup_{\boldsymbol{q}\in
F}\left\\{\boldsymbol{u}:\left\|\boldsymbol{u}-\boldsymbol{q}\right\|_{\ell_{\infty}(\boldsymbol{\Omega})}\leq
r\right\\},$

we have
${\mathcal{N}}\left(\widetilde{{\mathscr{M}}},r\right)\leq\left|F\right|$.
What we need now is to construct an appropriate set $F$ by exploiting the
specific structure of $\widetilde{{\mathscr{M}}}$, so that $\left|F\right|$
has an appropriate upper bound.

For this purpose, let $\kappa=\lceil 2M/r\rceil$, and we define

$\displaystyle{\mathscr{R}}=\left\\{-\kappa r/2,(-\kappa+1)r/2,\cdots,\kappa
r/2\right\\}.$ (3.17)

By [18, Lemma 4.4], for each $\boldsymbol{u}\in\widetilde{{\mathscr{M}}}$,
there exists $Q(\boldsymbol{u})\in{\mathscr{R}}^{\boldsymbol{\Omega}}$ such
that

$\displaystyle\left\|\boldsymbol{u}-Q(\boldsymbol{u})\right\|_{\ell_{\infty}(\boldsymbol{\Omega})}\leq
r/2~{}~{}~{}\text{and}~{}~{}~{}\left\|\boldsymbol{\nabla}\left(Q(\boldsymbol{u})\right)\right\|_{1}\leq\left\|\boldsymbol{\nabla}\boldsymbol{u}\right\|_{1}.$

Let

$\displaystyle\widetilde{F}=\left\\{\boldsymbol{q}\in\ell_{\infty}(\boldsymbol{\Omega}):\boldsymbol{q}=Q(\boldsymbol{u})~{}~{}\text{for
some}~{}~{}\boldsymbol{u}\in\widetilde{{\mathscr{M}}}\right\\}\subseteq{\mathscr{R}}^{\boldsymbol{\Omega}}.$

Notice that for each $\boldsymbol{q}\in\widetilde{F}$, there may be more than
one $\boldsymbol{u}\in\widetilde{{\mathscr{M}}}$ such that
$\boldsymbol{q}=Q(\boldsymbol{u})$.

For each $\boldsymbol{q}\in\widetilde{F}$, choose
$\boldsymbol{u}_{\boldsymbol{q}}\in\widetilde{{\mathscr{M}}}$ such that
$\left\|\boldsymbol{u}_{\boldsymbol{q}}-\boldsymbol{q}\right\|_{\ell_{\infty}(\boldsymbol{\Omega})}\leq
r/2$, and define
$F=\left\\{\boldsymbol{u}_{\boldsymbol{q}}:\boldsymbol{q}\in\widetilde{F}\right\\}$.
For an arbitrary $\boldsymbol{u}\in\widetilde{{\mathscr{M}}}$, there exists
$\boldsymbol{q}\in\widetilde{F}$ such that
$\left\|\boldsymbol{u}-\boldsymbol{q}\right\|_{\ell_{\infty}(\boldsymbol{\Omega})}\leq
r/2$. This implies

$\displaystyle\left\|\boldsymbol{u}-\boldsymbol{u}_{\boldsymbol{q}}\right\|_{\ell_{\infty}(\boldsymbol{\Omega})}\leq\left\|\boldsymbol{u}-\boldsymbol{q}\right\|_{\ell_{\infty}(\boldsymbol{\Omega})}+\left\|\boldsymbol{q}-\boldsymbol{u}_{\boldsymbol{q}}\right\|_{\ell_{\infty}(\boldsymbol{\Omega})}\leq
r,$

by the definition of $\boldsymbol{u}_{\boldsymbol{q}}$. Therefore,

$\displaystyle\widetilde{{\mathscr{M}}}\subseteq\bigcup_{\boldsymbol{u}_{\boldsymbol{q}}\in
F}\left\\{\boldsymbol{u}:\left\|\boldsymbol{u}-\boldsymbol{u}_{\boldsymbol{q}}\right\|_{\ell_{\infty}(\boldsymbol{\Omega})}\leq
r\right\\}~{}~{}\text{and}~{}~{}{\mathcal{N}}\left(\widetilde{{\mathscr{M}}},r\right)\leq\left|F\right|\leq\left|\widetilde{F}\right|.$

Thus, the covering number
${\mathcal{N}}\left(\widetilde{{\mathscr{M}}},r\right)$ is bounded by any
upper bound of $\left|\widetilde{F}\right|$. Notice that each
$\boldsymbol{q}\in\widetilde{F}$ is uniquely determined by
$\boldsymbol{\nabla}\boldsymbol{q}$ and $\boldsymbol{q}[1,\cdots,1]$. Since
$\widetilde{F}$ is a subset of ${\mathscr{R}}^{\boldsymbol{\Omega}}$, there
are $2\kappa+1$ choices for $\boldsymbol{q}[1,\cdots,1]$. It remains to count
the number of choices in $\boldsymbol{\nabla}\boldsymbol{q}$. Define

$\displaystyle\boldsymbol{\nabla}\widetilde{F}=\left\\{\boldsymbol{\nabla}\boldsymbol{q}:\boldsymbol{q}\in\widetilde{F}\right\\}.$

Then we need to bound $\left|\boldsymbol{\nabla}\widetilde{F}\right|$.

To do this, we first consider the uniform upper bound of
$\left\|\boldsymbol{\nabla}\boldsymbol{q}\right\|_{1}$ for
$\boldsymbol{q}\in\widetilde{F}$. By the definition of $\widetilde{F}$ and
[18, Lemma 4.4], for each $\boldsymbol{q}\in\widetilde{F}$, there exists
$\boldsymbol{u}\in\widetilde{{\mathscr{M}}}$ such that
$\left\|\boldsymbol{\nabla}\boldsymbol{q}\right\|_{1}\leq\left\|\boldsymbol{\nabla}\boldsymbol{u}\right\|_{1}$.
Since
$\left\|\boldsymbol{\lambda}\cdot{\boldsymbol{{\mathcal{W}}}}{\boldsymbol{f}}\right\|_{1}\leq
C_{{\boldsymbol{f}}}|\boldsymbol{\Omega}|^{1/2}$ by assumption, we further
have

$\displaystyle\left\|\boldsymbol{\nabla}\boldsymbol{q}\right\|_{1}\leq\left\|\boldsymbol{\nabla}\boldsymbol{u}\right\|_{1}\leq
C_{{\boldsymbol{{\mathcal{W}}}}}C_{{\boldsymbol{f}}}\left|\boldsymbol{\Omega}\right|^{b/2}$

with $b=\max\\{1-\beta,1\\}$ for notational simplicity. Hence, for all
$\boldsymbol{q}\in\widetilde{F}$, we have
$\left\|\boldsymbol{\nabla}\boldsymbol{q}\right\|_{1}\leq Kr/2$, where

$\displaystyle
K=\left\lceil\frac{2C_{{\boldsymbol{{\mathcal{W}}}}}C_{{\boldsymbol{f}}}\left|\boldsymbol{\Omega}\right|^{b/2}}{r}\right\rceil.$

In addition, since $\boldsymbol{q}\in{\mathscr{R}}^{\boldsymbol{\Omega}}$,
each element of $\boldsymbol{\nabla}\boldsymbol{q}$ has to be a multiple of
$r/2$, which means that the range of $\boldsymbol{\nabla}\boldsymbol{q}$ is a
subset of $\left\\{-Kr/2,-(K-1)r/2,\cdots,Kr/2\right\\}^{2}$. Recall that
there are
$R=2\left(\left|\boldsymbol{\Omega}\right|-\left|\boldsymbol{\Omega}\right|^{1/2}\right)$
elements in $\boldsymbol{\nabla}\boldsymbol{q}$. Hence,
$\left|\boldsymbol{\nabla}\widetilde{F}\right|$ can be bounded by the number
of all possible integer solutions of the following inequality

$\displaystyle\left|x_{1}\right|+\left|x_{2}\right|+\cdots+\left|x_{R-1}\right|+\left|x_{R}\right|\leq
K.$

That is (e.g. [56]),

$\displaystyle\left|\boldsymbol{\nabla}\widetilde{F}\right|$
$\displaystyle\leq
1+\sum_{k=1}^{K}\sum_{s=1}^{\min\\{k,R\\}}2^{s}\binom{R}{R-s}\binom{k-1}{s-1}$
$\displaystyle\leq
1+\sum_{k=1}^{K}2^{k}\sum_{s=1}^{\min\\{k,R\\}}\binom{R}{R-s}\binom{k-1}{s-1}=1+\sum_{k=1}^{K}2^{k}\binom{R+k-1}{R-1}$
$\displaystyle\leq\binom{R+K-1}{R-1}\sum_{k=0}^{K}2^{k}\leq
2^{K+1}\binom{R+K-1}{K}\leq 2\left[2\left(R+K-1\right)\right]^{K}.$

Hence, we have

$\displaystyle\left|\widetilde{F}\right|\leq\left(4\kappa+2\right)\left[2\left(R+K-1\right)\right]^{K}.$

In other words, using $r\geq\left|\boldsymbol{\Omega}\right|^{-a}$ with $a\geq
1$ and $K-1\leq
2C_{{\boldsymbol{{\mathcal{W}}}}}C_{{\boldsymbol{f}}}|\boldsymbol{\Omega}|^{a+b/2}$,
we have

$\displaystyle\ln{\mathcal{N}}\left({\mathscr{M}},r\right)$
$\displaystyle\leq\frac{2C_{{\boldsymbol{{\mathcal{W}}}}}C_{{\boldsymbol{f}}}\left|\boldsymbol{\Omega}\right|^{b/2}}{r}\ln\left(2\left(R+K-1\right)\right)+\ln\left(\frac{8M}{r}+2\right)$
$\displaystyle\leq\frac{2C_{{\boldsymbol{{\mathcal{W}}}}}C_{{\boldsymbol{f}}}\left|\boldsymbol{\Omega}\right|^{b/2}}{r}\left[\ln\left(4\left|\boldsymbol{\Omega}\right|+\frac{4C_{{\boldsymbol{{\mathcal{W}}}}}C_{{\boldsymbol{f}}}\left|\boldsymbol{\Omega}\right|^{b/2}}{r}\right)+\ln\frac{10M}{r}\right]$
$\displaystyle\leq\frac{2C_{{\boldsymbol{{\mathcal{W}}}}}C_{{\boldsymbol{f}}}\left|\boldsymbol{\Omega}\right|^{b/2}}{r}\ln\left(\left(1+C_{{\boldsymbol{{\mathcal{W}}}}}C_{{\boldsymbol{f}}}\right)40M\left|\boldsymbol{\Omega}\right|^{2a+b/2}\right)$

where we use the fact that $a+b/2\geq 1$ from the choice of $a$ and $b$ in the
final inequality. Therefore, we have

$\displaystyle\ln{\mathcal{N}}\left({\mathscr{M}},r\right)\leq\frac{20M(4a+b)C_{{\boldsymbol{{\mathcal{W}}}}}C_{{\boldsymbol{f}}}\left(1+C_{{\boldsymbol{{\mathcal{W}}}}}C_{{\boldsymbol{f}}}\right)\left|\boldsymbol{\Omega}\right|^{b/2}}{r}\log_{2}\left|\boldsymbol{\Omega}\right|,$

and this completes the proof. $\square$

##  4 Conclusion

In this paper, we present an approximation analysis of wavelet frame based
restoration from degraded and incomplete measurements. By the combination of
the uniform law of large numbers and the estimation for its involved covering
number of a hypothesis space of the solution, we establish unified
approximation properties of the wavelet frame based image restoration model,
together with the improved estimate of covering number over the previous one
in [18]. In addition, thanks to the underlying multiresolution analysis
structure, we further connect the error analysis in the discrete setting to
the approximation of underlying function where the discrete data comes from.
For the future works, we plan to study an approximation property of wavelet
frame based image restoration from partial Fourier samples, where
${\boldsymbol{{\mathcal{A}}}}={\boldsymbol{{\mathscr{F}}}}$ (the unitary
discrete Fourier transform) satisfies
$\left\|{\boldsymbol{{\mathscr{F}}}}\right\|_{\infty}=|\boldsymbol{\Omega}|^{1/2}$
and
$\sigma_{\min}({\boldsymbol{{\mathscr{F}}}})=\sigma_{\max}({\boldsymbol{{\mathscr{F}}}})=1$
in our framework. We may also plan to establish an approximation of tight
frame based missing data restoration on the graph [33], and the
multiresolution approximation of functions on the manifold [35].

## References

## References

  * A. Chambolle and Pock [[2021] ©2021] A. Chambolle, A., Pock, T., [2021] ©2021.  Approximating the total variation with finite differences or finite elements, in: Geometric partial differential equations. Part II. Elsevier/North-Holland, Amsterdam. volume 22 of Handb. Numer. Anal., pp. 383–417.  doi:10.1016/bs.hna.2020.10.005.
  * Adams [1975] Adams, R.A., 1975.  Sobolev Spaces.  Academic Press [A subsidiary of Harcourt Brace Jovanovich, Publishers], New York-London.  Pure and Applied Mathematics, Vol. 65.
  * Alon et al. [1997] Alon, N., Ben-David, S., Cesa-Bianchi, N., Haussler, D., 1997\.  Scale-sensitive dimensions, uniform convergence, and learnability.  J. ACM 44, 615–31.  doi:10.1145/263867.263927.
  * Aubert and Kornprobst [2006] Aubert, G., Kornprobst, P., 2006\.  Mathematical Problems in Image Processing. Partial Differential Equations and the Calculus of Variations. Foreword by Olivier Faugeras. volume 147 of Appl. Math. Sci. 2nd ed., Springer, New York.
  * Bar et al. [2007] Bar, L., Brook, A., Sochen, N., Kiryati, N., 2007\.  Deblurring of color images corrupted by impulsive noise.  IEEE Trans. Image Process. 16, 1101–11.  doi:10.1109/TIP.2007.891805.
  * Bar et al. [2006] Bar, L., Kiryati, N., Sochen, N., 2006.  Image deblurring in the presence of impulsive noise.  Int, J. Comput. Vis. 70, 279–98.  doi:10.1007/s11263-006-6468-1.
  * Bartlett et al. [2006] Bartlett, P.L., Jordan, M.I., McAuliffe, J.D., 2006.  Convexity, classification, and risk bounds.  J. Amer. Statist. Assoc. 101, 138–56.  doi:10.1198/016214505000000907.
  * Beckner [1975] Beckner, W., 1975.  Inequalities in Fourier analysis.  Ann. of Math. (2) 102, 159–82.  doi:10.2307/1970980.
  * Bertalmio et al. [2003] Bertalmio, M., Vese, L., Sapiro, G., Osher, S., 2003\.  Simultaneous structure and texture image inpainting.  IEEE Trans. Image Process. 12, 882–9.  doi:10.1109/TIP.2003.815261.
  * Borup et al. [2004] Borup, L., Gribonval, R., Nielsen, M., 2004.  Bi-framelet systems with few vanishing moments characterize Besov spaces.  Appl. Comput. Harmon. Anal. 17, 3–28.  doi:10.1016/j.acha.2004.01.004.
  * Cai et al. [2008] Cai, J.F., Chan, R.H., Nikolova, M., 2008.  Two-phase approach for deblurring images corrupted by impulse plus Gaussian noise.  Inverse Probl. Imaging 2, 187–204.  doi:10.3934/ipi.2008.2.187.
  * Cai et al. [2010a] Cai, J.F., Chan, R.H., Nikolova, M., 2010a.  Fast two-phase image deblurring under impulse noise.  J. Math. Imaging Vision 36, 46–53.  doi:10.1007/s10851-009-0169-7.
  * Cai et al. [2009] Cai, J.F., Chan, R.H., Shen, L., Shen, Z., 2009.  Convergence analysis of tight framelet approach for missing data recovery.  Adv. Comput. Math. 31, 87–113.  doi:10.1007/s10444-008-9084-5.
  * Cai et al. [2010b] Cai, J.F., Chan, R.H., Shen, Z., 2010b.  Simultaneous cartoon and texture inpainting.  Inverse Probl. Imaging 4, 379–95.  doi:10.3934/ipi.2010.4.379.
  * Cai et al. [2012] Cai, J.F., Dong, B., Osher, S., Shen, Z., 2012\.  Image restoration: total variation, wavelet frames, and beyond.  J. Amer. Math. Soc. 25, 1033–89.  doi:10.1090/S0894-0347-2012-00740-1.
  * Cai et al. [2016] Cai, J.F., Dong, B., Shen, Z., 2016.  Image restoration: a wavelet frame based model for piecewise smooth functions and beyond.  Appl. Comput. Harmon. Anal. 41, 94–138.  doi:10.1016/j.acha.2015.06.009.
  * Cai et al. [2009/10] Cai, J.F., Osher, S., Shen, Z., 2009/10.  Split Bregman methods and frame based image restoration.  Multiscale Model. Simul. 8, 337–69.  doi:10.1137/090753504.
  * Cai et al. [2011] Cai, J.F., Shen, Z., Ye, G.B., 2011.  Approximation of frame based missing data recovery.  Appl. Comput. Harmon. Anal. 31, 185–204.  doi:10.1016/j.acha.2010.11.007.
  * Candès et al. [2006] Candès, E.J., Romberg, J., Tao, T., 2006.  Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information.  IEEE Trans. Inform. Theory 52, 489–509.  doi:10.1109/TIT.2005.862083.
  * Candés and Tao [2005] Candés, E.J., Tao, T., 2005\.  Decoding by linear programming.  IEEE Trans. Inform. Theory 51, 4203–15.  doi:10.1109/TIT.2005.858979.
  * Candés and Tao [2006] Candés, E.J., Tao, T., 2006\.  Near-optimal signal recovery from random projections: universal encoding strategies?  IEEE Trans. Inform. Theory 52, 5406–25.  doi:10.1109/TIT.2006.885507.
  * Cavaretta et al. [1991] Cavaretta, A.S., Dahmen, W., Micchelli, C.A., 1991.  Stationary subdivision.  Mem. Amer. Math. Soc. 93, vi+186.  doi:10.1090/memo/0453.
  * Chai and Shen [2007] Chai, A., Shen, Z., 2007.  Deconvolution: a wavelet frame approach.  Numer. Math. 106, 529–87.  doi:10.1007/s00211-007-0075-0.
  * Chambolle and Darbon [2009] Chambolle, A., Darbon, J., 2009\.  On total variation minimization and surface evolution using parametric maximum flows.  Int. J. of Comput Vis. 84, 288\.  doi:10.1007/s11263-009-0238-9.
  * Chan et al. [2005] Chan, R.H., Ho, C.W., Nikolova, M., 2005.  Salt-and-pepper noise removal by median-type noise detectors and detail-preserving regularization.  IEEE Trans. Image Process. 14, 1479–85.  doi:10.1109/TIP.2005.852196.
  * Chan et al. [2002] Chan, T.F., Kang, S.H., Shen, J., 2002.  Euler’s elastica and curvature-based inpainting.  SIAM J. Appl. Math. 63, 564–92.  doi:10.1137/S0036139901390088.
  * Chan et al. [2006] Chan, T.F., Shen, J., Zhou, H.M., 2006.  Total variation wavelet inpainting.  J. Math. Imaging Vision 25, 107–25.  doi:10.1007/s10851-006-5257-3.
  * Choi et al. [2016] Choi, J., Dong, B., Zhang, X., 2016.  Limited tomography reconstruction via tight frame and simultaneous sinogram extrapolation.  J. Comput. Math. 34, 575–89.  doi:10.4208/jcm.1605-m2016-0535.
  * Cucker and Smale [2002] Cucker, F., Smale, S., 2002\.  On the mathematical foundations of learning.  Bull. Amer. Math. Soc. (N.S.) 39, 1–49.  doi:10.1090/S0273-0979-01-00923-5.
  * Daubechies [1992] Daubechies, I., 1992.  Ten Lectures on Wavelets. volume 61 of CBMS-NSF Regional Conference Series in Applied Mathematics.  Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA.  doi:10.1137/1.9781611970104.
  * Daubechies et al. [2003] Daubechies, I., Han, B., Ron, A., Shen, Z., 2003.  Framelets: MRA-based constructions of wavelet frames.  Appl. Comput. Harmon. Anal. 14, 1–46.  doi:10.1016/S1063-5203(02)00511-0.
  * Diestel [2018] Diestel, R., 2018.  Graph Theory. volume 173 of Graduate Texts in Mathematics.  Fifth ed., Springer, Berlin.  Paperback edition of [ MR3644391].
  * Dong [2017] Dong, B., 2017.  Sparse representation on graphs by tight wavelet frames and applications.  Appl. Comput. Harmon. Anal. 42, 452–79.  doi:10.1016/j.acha.2015.09.005.
  * Dong et al. [2012] Dong, B., Ji, H., Li, J., Shen, Z., Xu, Y., 2012.  Wavelet frame based blind image inpainting.  Appl. Comput. Harmon. Anal. 32, 268–79.  doi:10.1016/j.acha.2011.06.001.
  * Dong et al. [2016] Dong, B., Jiang, Q., Liu, C., Shen, Z., 2016.  Multiscale representation of surfaces by tight wavelet frames with applications to denoising.  Appl. Comput. Harmon. Anal. 41, 561–89.  doi:10.1016/j.acha.2015.03.005.
  * Dong et al. [2013] Dong, B., Li, J., Shen, Z., 2013.  X-ray CT image reconstruction via wavelet frame based regularization and Radon domain inpainting.  J. Sci. Comput. 54, 333–49.  doi:10.1007/s10915-012-9579-6.
  * Dong and Shen [2013] Dong, B., Shen, Z., 2013.  MRA-based wavelet frames and applications, in: Mathematics in Image Processing. Amer. Math. Soc., Providence, RI. volume 19 of IAS/Park City Math. Ser., pp. 9–158.
  * Dong and Shen [2015] Dong, B., Shen, Z., 2015.  Image restoration: a data-driven perspective, in: Proceedings of the 8th International Congress on Industrial and Applied Mathematics, Higher Ed. Press, Beijing. pp. 65–108.
  * Dong et al. [2017] Dong, B., Shen, Z., Xie, P., 2017.  Image restoration: a general wavelet frame based model and its asymptotic analysis.  SIAM J. Math. Anal. 49, 421–45.  doi:10.1137/16M1064969.
  * Dong et al. [2021] Dong, B., Shen, Z., Yang, J., 2021.  Approximation from noisy data.  SIAM J. Numer. Anal. 59, 2722–45.  doi:10.1137/20M1389091.
  * Donoho [2006] Donoho, D.L., 2006.  Compressed sensing.  IEEE Trans. Inform. Theory. 52, 1289–306.  doi:10.1109/TIT.2006.871582.
  * Elad et al. [2005] Elad, M., Starck, J.L., Querre, P., Donoho, D.L., 2005\.  Simultaneous cartoon and texture image inpainting using morphological component analysis (MCA).  Appl. Comput. Harmon. Anal. 19, 340–58.  doi:10.1016/j.acha.2005.03.005.
  * Folland [1999] Folland, G.B., 1999.  Real Analysis: Modern Techniques and Their Applications.  Pure and Appl. Math.. 2nd ed., John Wiley & Sons Inc., New York.
  * Goldstein and Osher [2009] Goldstein, T., Osher, S.J., 2009\.  The split Bregman method for $L1$-regularized problems.  SIAM J. Imaging Sci. 2, 323–43.  doi:10.1137/080725891.
  * Guo et al. [2014] Guo, W., Qin, J., Yin, W., 2014.  A new detail-preserving regularization scheme.  SIAM J. Imaging Sci. 7, 1309–34.  doi:10.1137/120904263.
  * Han and Shen [2009] Han, B., Shen, Z., 2009.  Dual wavelet frames and Riesz bases in Sobolev spaces.  Constr. Approx. 29, 369–406.  doi:10.1007/s00365-008-9027-x.
  * Ji et al. [2011] Ji, H., Shen, Z., Xu, Y., 2011\.  Wavelet based restoration of images with missing or damaged pixels.  East Asian J. Appl. Math. 1, 108–31.  doi:10.4208/eajam.020310.240610a.
  * Jia [1995] Jia, R.Q., 1995.  Subdivision schemes in $L_{p}$ spaces.  Adv. Comput. Math. 3, 309–41.  doi:10.1007/BF03028366.
  * Johnson et al. [2009] Johnson, M.J., Shen, Z., Xu, Y., 2009.  Scattered data reconstruction by regularization in B-spline and associated wavelet spaces.  J. Approx. Theory 159, 197–223.  doi:10.1016/j.jat.2009.02.005.
  * Koltchinskii [2001] Koltchinskii, V., 2001.  Rademacher penalties and structural risk minimization.  IEEE Trans. Inform. Theory 47, 1902–14.  doi:10.1109/18.930926.
  * Li et al. [2011] Li, Y.R., Shen, L., Dai, D.Q., Suter, B.W., 2011.  Framelet algorithms for de-blurring images corrupted by impulse plus Gaussian noise.  IEEE Trans. Image Process. 20, 1822–37.  doi:10.1109/TIP.2010.2103950.
  * Lustig et al. [2007] Lustig, M., Donoho, D., Pauly, J.M., 2007.  Sparse MRI: the application of compressed sensing for rapid MR imaging.  Magn. Reson. Med. 58, 1182–95.  doi:10.1002/mrm.21391.
  * Mallat [2008] Mallat, S., 2008.  A Wavelet Tour of Signal Processing, Third Edition: The Sparse Way.  3rd ed., Academic Press.
  * Rauhut et al. [2008] Rauhut, H., Schnass, K., Vandergheynst, P., 2008.  Compressed sensing and redundant dictionaries.  IEEE Trans. Inform. Theory 54, 2210–9.  doi:10.1109/TIT.2008.920190.
  * Ron and Shen [1997] Ron, A., Shen, Z., 1997.  Affine systems in $L_{2}(\mathbb{R}^{d})$: the analysis of the analysis operator.  J. Funct. Anal. 148, 408–47.  doi:10.1006/jfan.1996.3079.
  * Ross [1984] Ross, S., 1984.  A First Course in Probability.  Second ed., Macmillan Co., New York; Collier Macmillan Ltd., London.
  * Shen [2010] Shen, Z., 2010.  Wavelet frames and image restorations, in: Proceedings of the International Congress of Mathematicians. Volume IV, Hindustan Book Agency, New Delhi. pp. 2834–63.
  * Starck et al. [2005] Starck, J.L., Elad, M., Donoho, D.L., 2005.  Image decomposition via the combination of sparse representations and a variational approach.  IEEE Trans. Image Process. 14, 1570–82.  doi:10.1109/TIP.2005.852206.
  * van der Vaart and Wellner [1996] van der Vaart, A.W., Wellner, J.A., 1996\.  Weak Convergence and Empirical Processes.  Springer Series in Statistics, Springer-Verlag, New York.  doi:10.1007/978-1-4757-2545-2. with applications to statistics.
  * Vapnik [1998] Vapnik, V.N., 1998.  Statistical Learning Theory.  Adaptive and Learning Systems for Signal Processing, Communications, and Control, John Wiley & Sons, Inc., New York.  A Wiley-Interscience Publication.
  * W. Lawton et al. [1998] W. Lawton, W., Lee, S.L., Shen, Z., 1998.  Convergence of multidimensional cascade algorithm.  Numer. Math. 78, 427–38.  doi:10.1007/s002110050319.
  * Wen et al. [2012] Wen, Y.W., Chan, R.H., Yip, A.M., 2012.  A primal-dual method for total-variation-based wavelet domain inpainting.  IEEE Trans. Image Process. 21, 106–14.  doi:10.1109/TIP.2011.2159983.
  * Yang et al. [2017] Yang, J., Stahl, D., Shen, Z., 2017.  An analysis of wavelet frame based scattered data reconstruction.  Appl. Comput. Harmon. Anal. 42, 480–507.  doi:10.1016/j.acha.2015.09.008.
  * Ye and Zhou [2013] Ye, X., Zhou, H., 2013.  Fast total variation wavelet inpainting via approximated primal-dual hybrid gradient algorithm.  Inverse Probl. Imaging 7, 1031–50.  doi:10.3934/ipi.2013.7.1031.
  * Zhang and Chan [2010] Zhang, X., Chan, T.F., 2010\.  Wavelet inpainting by nonlocal toral variation.  Inverse Probl. Imaging 4, 191–210.  doi:10.3934/ipi.2010.4.191.