# Multivariate $\alpha$-Molecules

Axel Flinth  Martin Schäfer  Both authors are affiliated to the Institut für
Mathematik, Technische Universität Berlin.
_E-mail addresses:_<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

The suboptimal performance of wavelets with regard to the approximation of
multivariate data gave rise to new representation systems, specifically
designed for data with anisotropic features. Some prominent examples of these
are given by ridgelets, curvelets, and shearlets, to name a few.

The great variety of such so-called directional systems motivated the search
for a common framework, which unites many under one roof and enables a
simultaneous analysis, for example with respect to approximation properties.
Building on the concept of parabolic molecules, the recently introduced
framework of $\alpha$-molecules does in fact include the previous mentioned
systems. Until now however it is confined to the bivariate setting, whereas
nowadays one often deals with higher dimensional data. This motivates the
extension of this unifying theory to dimensions larger than 2, put forward in
this work. In particular, we generalize the central result that the cross-
Gramian of any two systems of $\alpha$-molecules will to some extent be
localized.

As an exemplary application, we investigate the sparse approximation of video
signals, which are instances of 3D data. The multivariate theory allows us to
derive almost optimal approximation rates for a large class of representation
systems.

_Keywords:_ Wavelets, Shearlets, Anisotropic Scaling, $\alpha$-Molecules,
Multiscale Analysis, Nonlinear Approximation.

_2010 MSC:_ 41A30, 41A63, 42C40

##  1 Introduction

111The final publication has been published in Journal of Approximation
Theory. It can be found via its DOI 10.1016/j.jat.2015.10.004.

One of the most influential modern developments in applied harmonic analysis
has undeniably been the introduction of _wavelets_ [13]. Their construction is
based on dilations and translations of a (finite) set of generating functions
$(g_{\lambda})_{\lambda}\subseteq L^{2}(\mathbb{R}^{d})$. By carefully
choosing the generators, the resulting systems can become frames or even
orthonormal bases of the space $L^{2}(\mathbb{R}^{d})$. Furthermore,
additional properties can be obtained, such as e.g. smoothness or compact
support. Some real-world applications of wavelets today are e.g. data
compression (e.g. JPEG2000) or restoration tasks in imaging sciences [1]. In
the field of PDE’s wavelets nowadays play a central role in solving elliptic
equations [7].

The great success of wavelet systems – besides their elegant construction
principle and available fast numerical implementations – rests upon the fact
that they provide efficient multiscale representations for various types of
data. In particular, they optimally sparsely approximate functions
$f:\mathbb{R}^{d}\rightarrow\mathbb{C}$, which are smooth apart from (a finite
number of) point singularities, in the sense of fast decay of the $N$-term
approximation error. Since such singularities are the only ones that occur in
‘reasonable’ 1D data, we can safely say that wavelets are optimal for
approximating one-dimensional functions.

Moving up a dimension however, the situation changes completely. Two-
dimensional data may well have singularities along curves and is often
governed by such anisotropic features – think of edges in images for instance.
A widely used model for such data is the class of cartoon-like functions [15],
i.e. functions which are smooth except for a curve-like singularity (see
Section 4 for details). For this class, wavelets do not perform optimally any
more [15], and hence other approaches have to be considered.

###  1.1 Directional Representation Systems

The reason for the non-optimal performance of wavelets in a multivariate
setting is due to their isotropic scaling law, which is not optimally suited
for resolving anisotropic, i.e. directional, features. Therefore, many systems
employing some form of anisotropic scaling and thus better suited for this
task have been considered in recent years. Subsequently, we briefly recall a
few of these constructions for motivation purposes, but by no means this shall
be a complete overview.

####  1.1.1 Ridgelets

Aiming to approximate functions with line singularities, Candès defined so-
called _ridgelets_ [2] as translated, rotated and dilated versions of a ridge
function, which is constant orthogonal to some specified direction
$\eta\in\mathbb{S}^{d-1}$. Since such functions are not square-integrable, the
concept was adjusted by Donoho [3] allowing ridgelets a slow decay orthogonal
to the $\eta$-direction, leading to a modified notion adopted for instance in
[23, 26, 25]. In the new sense, a system of ridgelets is constructed
performing rotations, translations and directional scaling on a generator
$g\in L^{2}(\mathbb{R}^{d})$ with corresponding scaling matrix

$\displaystyle A_{0,s}=\begin{pmatrix}s&0\\\ 0&1\end{pmatrix},\qquad s>0.$

Tight ridgelet frames of this type were constructed e.g. in [23, 25].

####  1.1.2 Curvelets and Shearlets

A true breakthrough was achieved by Candès and Donoho in 2002 with the
introduction of _curvelets_ [5], the first system to provide a provably
(almost) optimal approximation rate for a certain class of cartoon-like
functions. Again, the idea is to apply certain rotation, translation and
scaling operations to a generating function. The major novelty was the use of
_parabolic scaling_ , a compromise between directional scaling used for
ridgelets and isotropic scaling used for wavelets, described by a matrix of
the form

$\displaystyle A_{\frac{1}{2},s}=\begin{pmatrix}s&0\\\
0&s^{1/2}\end{pmatrix},\qquad s>0.$ (1)

This type of scaling is specifically adapted to data with
$C^{2}$-discontinuity curves, since it leaves the parabola invariant and
produces functions with essential support in a rectangle of size ‘width
$\approx$ length2’. We mention that in the actual construction of the
classical tight frame of curvelets [5], the translations and rotations are
applied to a set of generators, related to each other by a parabolic scaling
law realised not by (1) but by dilations with respect to polar coordinates.

A few years after curvelets in 2005, _shearlets_ were developed mainly by
Kutyniok, Labate, Lim, and Weiss [40]. They also scale parabolically and
feature the same celebrated approximation properties as curvelets for cartoon-
like functions [30, 38]. The main difference is that shearings and not
rotations are used for the change of direction. The choice of shears makes
shearlets more adapted to a digital grid, since shearings given by the
matrices

$\displaystyle S_{h}=\begin{pmatrix}1&0\\\
h&1\end{pmatrix}\quad\text{and}\quad S^{T}_{h}=\begin{pmatrix}1&h\\\
0&1\end{pmatrix},\quad h\in\mathbb{R},$ (2)

leave the digital grid invariant. This is favorable in a discrete setting and
bears the advantage of a unified treatment of the continuum and digital realm.
It should be noted that some actual constructions of shearlet systems are not
entirely faithful to the original idea of applying shears, translations, and
parabolic scalings to a single generator: The probably most notable and widely
used adjustment is the idea of _cone-adaption_ , where several generators with
different orientations are used in order to avoid large shear parameters. We
will discuss this strategy in greater detail later in the article.

Nowadays, shearlets are a widely used directional representation system with
applications ranging from imaging science [16], simulations of inverse
scattering problems [43] to solvers for transport equations [12]. For more
information we refer to the book [39].

####  1.1.3 $\alpha$-Curvelets (and -Shearlets)

The systems we have presented so far all utilize different versions of the
scaling matrix

$\displaystyle A_{\alpha,s}=\begin{pmatrix}s&0\\\
0&s^{\alpha}\end{pmatrix},\qquad s>0,$ (3)

where the parameter $\alpha\in[0,1]$ specifies the degree of anisotropy in the
scaling: $\alpha=1$ corresponds to wavelets, $\alpha=\frac{1}{2}$ to curvelets
and shearlets, and $\alpha=0$ to ridgelets. This observation was used in [25]
to define _$\alpha$ -curvelets_, and associated bandlimited tight frames were
constructed for every $\alpha\in[0,1]$. Similar to $\alpha$-curvelets, the
notion of a shearlet can be generalized to comprise $\alpha$-scaling. The
resulting _$\alpha$ -shearlets_ have been defined and examined in [35, 41]
(for the range $\alpha\in[\frac{1}{2},1)$).

###  1.2 A common Framework

The directional systems described above are all constructed using the same
idea: start with a set of generators, and then perform scalings (with some
degree of anisotropicity), changes of direction (e.g. rotations or shears) and
translations. Further, in order to obtain systems with desirable properties,
some regularity condition on the generators has to be posed. Having this in
mind, it seems possible to regard all such systems as certain instances of a
more general concept.

####  1.2.1 Parabolic Molecules

In 2011, Grohs and Kutyniok introduced the concept of _parabolic molecules_
[27], which allows to derive classical curvelets and shearlets as special
instances of the same general construction process. Starting from a set of
generators, a system of parabolic molecules is obtained via parabolic
dilations, rotations, and translations. The essential novelty is that the
generators can, apart from a certain time-frequency localization, be chosen
freely and each function may have its own generator. Together with the
utilization of so-called parametrizations to allow generic indexing, the
‘variability’ of the generators provides the flexibility to cast rotation- and
shear-based systems as instances of one unifying construction principle.
Moreover, it becomes possible to relax the vanishing moment conditions –
important for high approximation rates – imposed on the generators. Rather to
demand rigid conditions as in most classical constructions, it suffices to
require the moments of the variable generators to vanish asymptotically at
high scales, without changing the asymptotic approximation behavior.

####  1.2.2 $\alpha$-Molecules

The scope of parabolic molecules is limited to parabolically scaled systems,
wherefore a major generalization was pursued in [28], namely the extension to
_$\alpha$ -molecules_. These incorporate more general $\alpha$-scaling (3) and
can thus bridge the gap between wavelets and ridgelets, as well as curvelets
and shearlets in between.

However, like the framework of parabolic molecules, they are confined to a
2-dimensional setting. Since nowadays higher dimensional data plays an ever
increasing role, an extension of the theory to higher dimensions is
appreciable. A first step in this direction was taken by one of the authors
[20] with an extension of the parabolic molecules framework to 3D. In this
paper, we aim to generalize the framework to arbitrary dimensions
$d\in\mathbb{N}$, $d\geq 2$ and general scaling parameters $\alpha\in[0,1]$.

####  1.2.3 Why $\alpha$-Molecules?

The concept of (multivariate) $\alpha$-molecules covers a great variety of
directional multiscale systems and unifies their treatment and analysis, e.g.
with respect to approximation properties. The foundational result behind this
is Theorem 2.5, i.e. the fact that the localization of the cross-Gramian of
two systems of $\alpha$-molecules – in the sense of a strong off-diagonal
decay – merely depends on their respective parametrizations and orders. Hence,
the parametrization and the order of a system of $\alpha$-molecules alone is
sufficient information to determine the corresponding approximation behavior.
This is illustrated by Theorem 4.4, where a large class of directional
representation systems is specified with almost optimal approximation
performance with respect to cartoon video data. Finally, we remark that apart
from the analysis aspects the framework also promises new design approaches
for novel constructions.

###  1.3 Our Contributions

As mentioned before, the goal of this paper is to generalize the concept of
$\alpha$-molecules to arbitrary dimensions. The multivariate formulation
extends the earlier results from [27, 28, 20] and gives valuable insights,
e.g. on how they scale with the dimension. One should emphasize that the
extension beyond dimension 2 comes with several delicacies such as to
determine a suitable definition of the so-called $\alpha$-scale index
distance. The technical effort to prove the mentioned results is considerably
higher when dealing with more than 2 dimensions, mainly because many arguments
take place on the unit sphere instead of the unit circle. It also gets
significantly harder to prove that shearlets, i.e. the main example of
multidimensional directional systems in dimensions higher than 2, can be
included in the framework. Hence already the core results of the theoretical
framework themselves do not generalize straightforwardly.

###  1.4 Outline

The paper is organized as follows. The core part of the theory, in particular
Theorem 2.5, is presented in Section 2. Since the corresponding proof is quite
involved it is outsourced to Section 6. The abstract theory is further
developed in Section 3 with a focus on approximation theory. Here Theorem 3.7
derives sufficient conditions for two systems of $\alpha$-molecules to be
sparsity equivalent. In Section 4 we then exemplarily apply the theory to
video data and identify a large class of representation systems providing
almost optimal sparse approximation in Theorem 4.4. Finally, Section 5 is
devoted to a large class of concrete systems of $\alpha$-molecules, namely
multivariate $\alpha$-shearlet molecules. As specific examples we present
pyramid-adapted shearlet systems, in particular those generated by compactly
supported functions and the smooth Parseval frame of band-limited shearlets by
Guo and Labate. This frame is presented in greater detail in Subsection 5.3.1,
thereby fixing some inaccuracies of the original definition.

###  1.5 Notation

The (strictly) positive real numbers are denoted by $\mathbb{R}_{+}$. The
vector space $\mathbb{R}^{d}$, where $d\in\mathbb{N}$, is equipped with the
usual Euclidean scalar product denoted by $\langle\cdot,\cdot\rangle$.
$\mathbb{N}$ hereby denotes the set of positive integers, while
$\mathbb{N}_{0}=\mathbb{N}\cup\left\\{0\right\\}$. For the unit sphere in
$\mathbb{R}^{d}$ the symbol $\mathbb{S}^{d-1}$ is used. The standard unit
vectors are given by $e_{1},\ldots,e_{d}$ and for a vector
$x\in\mathbb{R}^{d}$ we use the notation $[x]_{i}:=\langle x,e_{i}\rangle$,
$i\in\\{1,\ldots,d\\}$, for the $i$:th component. Its $p$-(quasi-)norm in the
range $0<p\leq\infty$ is denoted by $|x|_{p}$. In case of the Euclidean norm
$|x|_{2}=\sqrt{\langle x,x\rangle}$, we will usually omit the subindex. We
further define
$\left|x\right|_{[d-1]}:=|([x]_{1},\ldots,[x]_{d-1},0)^{T}|_{2}$. For a matrix
$M\in\mathbb{R}^{m,n}$, we denote its operator norm as a mapping from the
Euclidean $\mathbb{R}^{n}$ to the Euclidean $\mathbb{R}^{m}$ by
$\left\|M\right\|_{2\to 2}$, and its entries by $[M]_{i}^{j}$, $i=1,\dots,m$,
$j=1,\dots n$.

The usual Lebesgue spaces on $\mathbb{R}^{d}$ are denoted by
$L^{p}(\mathbb{R}^{d})$, where $0<p\leq\infty$. The corresponding sequence
spaces are given by $\ell^{p}(\Lambda)$, where $\Lambda$ is a countable index
set. In both cases we use the symbol $\|\cdot\|_{p}$ for the associated
(quasi-)norms. Further, the symbol $\langle\cdot,\cdot\rangle$ will also be
used for the inner products on the Hilbert spaces $L^{2}(\mathbb{R}^{d})$ and
$\ell^{2}(\Lambda)$. For the weak versions of the sequence spaces we use the
notation $\omega\ell^{p}(\Lambda)$ with associated (quasi-)norms
$\|\cdot\|_{\omega\ell^{p}}$. For their definition we refer to Subsection 3.1.

In addition, we need the following function spaces on $\mathbb{R}^{d}$: the
space of continuous functions $C(\mathbb{R}^{d})$, the space of $n$-times
continuously differentiable functions $C^{n}(\mathbb{R}^{d})$ for
$n\in\mathbb{N}\cup\\{\infty\\}$, as well as their respective restrictions
$C_{c}(\mathbb{R}^{d})$ and $C^{n}_{c}(\mathbb{R}^{d})$ to functions with
compact support.

The Fourier transform $\hat{f}$ of a function $f$ in the space of Schwarz
functions $\mathscr{S}(\mathbb{R}^{d})$ is given by

$\displaystyle\hat{f}(\xi)=\int_{\mathbb{R}^{d}}f(x)\exp(-2\pi
i\langle\xi,x\rangle)dx.$

As usual, it extends to the space of tempered distributions
$\mathscr{S}^{\prime}(\mathbb{R}^{d})$.

For two entities $x,y$, usually dependent on a certain set of parameters, the
notation ‘$x\lesssim y$’ shall mean that $x\leq Cy$ for some fixed constant
$C>0$, which is independent of the involved parameters. If both $x\lesssim y$
and $y\lesssim x$ we write ‘$x\asymp y$’. We further need the ceiling function
on $\mathbb{R}$ given by $\lceil x\rceil:=\min\\{\ell\in\mathbb{Z}:\ell\geq
x\\}$. A useful abbreviation is also the ubiquitous ‘analyst’s bracket’
defined by $\langle x\rangle:=\sqrt{1+x^{2}}$ for $x\in\mathbb{R}$.

##  2 $\alpha$-Molecules in $d$ Dimensions

Recalling the definition in [28], a system of bivariate $\alpha$-molecules
consists of functions in $L^{2}(\mathbb{R}^{2})$ obtained by applying
$\alpha$-scaling, rotations, and translations to a set of generating
functions, which need to be sufficiently localized in time and frequency. Due
to this construction, every $\alpha$-molecule is naturally associated with a
certain scale, orientation and spatial position, which – in the
$2$-dimensional case – is conveniently represented by a point in the
corresponding parameter space
$\mathbb{P}_{2}=\mathbb{R}_{+}\times\mathbb{S}^{1}\times\mathbb{R}^{2}$.

Aiming for a multivariate generalization, we thus first need a $d$-dimensional
version of this parameter space. We let $\mathbb{S}^{d-1}$ denote the unit
sphere in $\mathbb{R}^{d}$ and put

$\displaystyle\mathbb{P}_{d}=\mathbb{R}_{+}\times\mathbb{S}^{d-1}\times\mathbb{R}^{d}.$

Each function $m_{\lambda}\in L^{2}(\mathbb{R}^{d})$ of a system of
$d$-dimensional $\alpha$-molecules $(m_{\lambda})_{\lambda\in\Lambda}$ shall
by definition then be associated with a unique point
$(s_{\lambda},e_{\lambda},x_{\lambda})\in\mathbb{P}_{d}$, where the variable
$s_{\lambda}\in\mathbb{R}_{+}$ shall represent its scale, the vector
$e_{\lambda}\in\mathbb{S}^{d-1}$ its orientation in $\mathbb{R}^{d}$, and
$x_{\lambda}\in\mathbb{R}^{d}$ the spatial location. The relation between the
index $\lambda$ of a molecule $m_{\lambda}$ and its position
$(s_{\lambda},e_{\lambda},x_{\lambda})$ in $\mathbb{P}_{d}$ is described by a
so-called parametrization, analogue to [28].

######  Definition 2.1.

A _parametrization_ consists of a pair $(\Lambda,\Phi_{\Lambda})$, where
$\Lambda$ is a discrete index set and $\Phi_{\Lambda}$ is a mapping

$\Phi_{\Lambda}:\left\\{\begin{array}[]{ccc}\Lambda&\to&\mathbb{P}_{d},\\\
\lambda\in\Lambda&\mapsto&\left(s_{\lambda},e_{\lambda},x_{\lambda}\right).\end{array}\right.$

which associates with each $\lambda\in\Lambda$ a _scale_
$s_{\lambda}\in\mathbb{R}_{+}$, a _direction_
$e_{\lambda}\in\mathbb{S}^{d-1}$, and a _location_
$x_{\lambda}\in\mathbb{R}^{d}$.

For practical purposes it is more convenient to represent an orientation
$\eta\in\mathbb{S}^{d-1}$ by a set of angles. Therefore we define the rotation
matrix $R_{\theta}$ for
$\theta=(\theta_{1},\ldots,\theta_{d-2})\in\mathbb{R}^{d-2}$ by

$\displaystyle
R_{\theta}=\begin{pmatrix}\cos(\theta_{1})&&-\sin(\theta_{1})\\\ &I_{d-2}&\\\
\sin(\theta_{1})&&\cos(\theta_{1})\end{pmatrix}\cdot{\ldots}\cdot\begin{pmatrix}\cos(\theta_{d-2})&&-\sin(\theta_{d-2})&\\\
&1&&\\\ \sin(\theta_{d-2})&&\cos(\theta_{d-2})&\\\ &&&I_{d-3}\end{pmatrix},$

where $I_{d}$ for $d\in\mathbb{N}$ denotes the $d$-dimensional identity
matrix. Furthermore, we introduce for $\varphi\in\mathbb{R}$ the matrix

$\displaystyle R_{\varphi}=\begin{pmatrix}\cos(\varphi)&\sin(\varphi)&\\\
-\sin(\varphi)&\cos(\varphi)&\\\ &&I_{d-2}\end{pmatrix}.$

Note that these definitions pose an inconsistency in the notation, since they
depend on the particular naming of the index. However, since we always use
these particular indices, this will not lead to any problems while improving
the readability significantly.

Each orientation $\eta\in\mathbb{S}^{d-1}$ can now be uniquely represented by
a set of angles
$(\theta_{1},\ldots,\theta_{d-2},\varphi)\in[0,\pi]\times[-\frac{\pi}{2},\frac{\pi}{2}]^{d-3}\times[0,2\pi]$
via the relation

$\displaystyle\eta=R^{T}_{\varphi}R^{T}_{\theta}e_{d},$ (4)

where $e_{d}$ is the $d$th unit vector of $\mathbb{R}^{d}$. Explicitly, it is
given by

$\displaystyle\eta(\theta,\varphi)=\begin{pmatrix}\eta_{1}(\theta,\varphi)\\\
\vdots\\\
\eta_{d}(\theta,\varphi)\end{pmatrix}=\begin{pmatrix}\phantom{+}\cos(\varphi)\cos(\theta_{d-2})\cdots\cdots\cos(\theta_{2})\sin(\theta_{1})\\\
\phantom{+}\sin(\varphi)\cos(\theta_{d-2})\cdots\cdots\cos(\theta_{2})\sin(\theta_{1})\\\
-\sin(\theta_{d-2})\cos(\theta_{d-3})\cdots\cos(\theta_{2})\sin(\theta_{1})\\\
\vdots\\\ -\sin(\theta_{3})\cos(\theta_{2})\sin(\theta_{1})\\\
-\sin(\theta_{2})\sin(\theta_{1})\\\ \cos(\theta_{1})\end{pmatrix}.$

Next, we adapt the $\alpha$-scaling matrix (3) to the multivariate setting.
For $\alpha\in[0,1]$, we set

$\displaystyle A_{\alpha,s}=\begin{pmatrix}s^{\alpha}I_{d-1}&\\\
&s\end{pmatrix}.$ (5)

In case $\alpha=1$ this matrix scales $\mathbb{R}^{d}$ isotropically, in the
range $\alpha\in[0,1)$ it scales uniformly in all directions except for the
$e_{d}$-direction. Note that here we choose $e_{d}$ as the distinguished
direction in which the scaling is stronger – in contrast to the 2-dimensional
case [28], where $e_{1}$ was chosen.

After this preparation we are ready to give the definition of $d$-variate
$\alpha$-molecules, $d\in\mathbb{N},d\geq 2$, which essentially reduces to the
original definition from [28] for $d=2$, except for the interchanged roles of
the directions $e_{1}$ and $e_{d}$.

######  Definition 2.2.

Let $\alpha\in[0,1]$, $d\in\mathbb{N}$, $d\geq 2$ and
$L,M,N_{1},N_{2}\in\mathbb{N}_{0}\cup\\{\infty\\}$. Further let
$(\Lambda,\Phi_{\Lambda})$ be a parametrization with
$\Phi_{\Lambda}(\lambda)=(s_{\lambda},e_{\lambda},x_{\lambda})\in\mathbb{P}_{d}$
for $\lambda\in\Lambda$. The corresponding angles (4) for $e_{\lambda}$ shall
be denoted by $(\theta_{\lambda},\varphi_{\lambda})$. A family of functions
$(m_{\lambda})_{\lambda\in\Lambda}\subseteq L^{2}(\mathbb{R}^{d})$ is called a
_system of $d$-dimensional $\alpha$-molecules_ of order $(L,M,N_{1},N_{2})$
with respect to the parametrization $(\Lambda,\Phi_{\Lambda})$, if each
$m_{\lambda}$ is of the form

$\displaystyle
m_{\lambda}=s_{\lambda}^{\frac{1+\alpha(d-1)}{2}}g_{\lambda}\big{(}A_{\alpha,s_{\lambda}}R_{\theta_{\lambda}}R_{\varphi_{\lambda}}(x-x_{\lambda})\big{)}$
(6)

with generators $g_{\lambda}\in L^{2}(\mathbb{R}^{d})$ satisfying for every
multi-index $\rho\in\mathbb{N}_{0}^{d}$ with $|\rho|_{1}\leq L$ the condition

$\displaystyle\left|\partial^{\rho}\hat{g}_{\lambda}(\xi)\right|\lesssim\min\left(1,s_{\lambda}^{-1}+\left|[\xi]_{d}\right|+s_{\lambda}^{-(1-\alpha)}\left|\xi\right|_{[d-1]}\right)^{M}\langle\left|\xi\right|\rangle^{-N_{1}}\langle\left|\xi\right|_{[d-1]}\rangle^{-N_{2}}.$
(7)

The implicit constant in (7) is required to be uniform in $\Lambda$. In case
that a control parameter takes the value $\infty$, this shall mean that the
condition (7) is fulfilled with the respective quantity arbitrarily large.

A system of $\alpha$-molecules is thus obtained by applying rotations,
translations, and $\alpha$-scaling to a set of generating functions
$(g_{\lambda})_{\lambda}$, which are required to obey a prescribed time-
frequency localization. Every molecule $m_{\lambda}$ is thereby allowed to
have its own individual generator $g_{\lambda}$.

The definition only poses conditions on the Fourier transform of the
generators $g_{\lambda}$. The number $L$ describes the spatial localization,
$M$ the number of directional (almost) vanishing moments, and $N_{1},N_{2}$
the smoothness of an element $m_{\lambda}$. Also note that the weighting
function on the right hand side of (7) is symmetric with respect to rotations
around the $e_{d}$-axis, as well as reflections along this axis.

Applying $A_{\alpha,s}$ with $\alpha<1$ and $s>1$ to the unit ball
$B=\\{x\in\mathbb{R}^{d}:|x|\leq 1\\}$ stretches $B$ in the $e_{d}$-direction.
This results in plate-like support of the characteristic function
$\chi_{B}(A_{\alpha,s}\cdot)$ for large $s\in\mathbb{R}_{+}$, with the ‘plate’
lying in the plane spanned by the vectors $\\{e_{1},\ldots,e_{d-1}\\}$. Thus,
at high scales $\alpha$-molecules can be thought of as plate-like objects in
the spatial domain. The approximate frequency support on the other hand is
concentrated in a pair of opposite cones in the direction of the respective
orientation.

######  Remark 2.3.

It may seem more natural to choose a rotation $R_{\eta}$ from $e_{d}$ to
$\eta\in\mathbb{S}^{d-1}$ in the $(e_{d},\eta)$-plane to adjust the
orientation in (6). Due to the symmetries of the weighting function of the
generators, this choice is however not necessary. Since it is easier to use
fixed rotation planes, we stick to this more pragmatic choice of rotation
parameters.

Let us conclude this paragraph with some comments on the use of the term
‘molecule’. In the theory of function spaces, ‘atoms’ originally refer to the
basic building blocks of a function space. In the widest sense, an atomic
decomposition of a function space is a countable subset containing functions
called ‘atoms’, which allow to represent every function of the space as a
countable linear combination.

In the theory of atomic decomposition of so called _Hardy spaces_ $H^{p}$, an
atom is defined as a function $a$ supported in some cube $Q$ possessing
vanishing moments and satisfying some norm bound, e.g.
$\left\|a\right\|_{2}\leq\left|Q\right|^{\frac{1}{2}-\frac{1}{p}}$[48]. This
definition has also been adapted in a slightly less rigid form in other parts
of mathematics. Here, the term ”atom” often simply refers to a function having
compact support and possessing many vanishing moments. Typically, these atoms
also possess additional properties, e.g. they may be bounded or fulfill
smoothness conditions.

Furthermore, in many instances, the atoms are also related to each other.
Classical coorbit spaces e.g. possess atomic decompositions with atoms
obtained from the action of a group on a single generator [18]. A primary
example are the (homogeneous) Besov-Triebel-Lizorkin spaces with (compactly
supported) wavelets as atoms.

A system of $\alpha$-molecules somewhat resembles this structure, whereas in a
relaxed form. The compact support condition is replaced with a less
restrictive decay condition, and the moments are only asymptotically
vanishing. In addition, the molecules are related to each other via certain
group transformations, namely translations, rotations, and dilations. However,
this relation shall not be understood in a strict sense, since the generators
are allowed to vary to some extent. They just need to fulfill a uniform
localization condition. For the functions of a system featuring these kind of
soft conditions the term ‘molecules’ was coined and used e.g. in [4, 32, 27,
28].

###  2.1 Index Distance in $d$ Dimensions

A central ingredient of the theory of bivariate $\alpha$-molecules [28] is the
fact that the parameter space $\mathbb{P}_{2}$ can be equipped with a natural
(pseudo-)metric with the property, that the distance between two points in
$\mathbb{P}_{2}$ ‘anti-correlates’ with the size of the scalar products of
$\alpha$-molecules associated with those points: The greater the distance
between two indices$\lambda,\lambda^{\prime}\in\mathbb{P}_{2}$, the smaller
the scalar product of the corresponding $\alpha$-molecules
$m_{\lambda},m_{\lambda^{\prime}}\in L^{2}(\mathbb{R}^{d})$.

Our next aim is to find a suitable analogon of this (pseudo-)metric for the
parameter space $\mathbb{P}_{d}$. As for $\mathbb{P}_{2}$, the distance
between two points
$(s_{\lambda},e_{\lambda},x_{\lambda}),\,(s_{\mu},e_{\mu},x_{\mu})\in\mathbb{P}_{d}$
must certainly take into account their spatial, scale, and orientational
relation. The spatial distance is measured by a rightly balanced combination
of an isotropic term $|x_{\lambda}-x_{\mu}|^{2}$ and a non-isotropic component
$|\langle e_{\lambda},x_{\lambda}-x_{\mu}\rangle|$, which depends on the
orientation of the molecules. For the distance between the orientations
$e_{\lambda}$ and $e_{\mu}$, it seems natural to consider the angle
$d_{\mathbb{S}}(e_{\lambda},e_{\mu})=\arccos(\langle
e_{\lambda},e_{\mu}\rangle)$ with
$d_{\mathbb{S}}(e_{\lambda},e_{\mu})\in[0,\pi]$. Due to the symmetries of the
weighting function in (7) however, the angle
$d_{\mathbb{S}}(e_{\lambda},e_{\mu})$ is projected onto the interval
$[-\pi/2,\pi/2)$, with the projected angle
$\\{d_{\mathbb{S}}(e_{\lambda},e_{\mu})\\}$ being the unique element of the
set $\left\\{d_{\mathbb{S}}(e_{\lambda},e_{\mu})+n\pi\ |\
n\in\mathbb{Z}\right\\}$ in the interval $[-\pi/2,\pi/2)$. A suitable measure
for the orientational distance is then
$|\\{d_{\mathbb{S}}(e_{\lambda},e_{\mu})\\}|^{2}$. This definition is in fact
consistent with the one in [28], since in two dimensions we have
$|\\{d_{\mathbb{S}}(e_{\lambda},e_{\mu})\\}|=|\\{\varphi_{\lambda}-\varphi_{\mu}\\}|$.
Finally, the distance between different scales $s_{\lambda},\,s_{\mu}>0$ is
measured by the ratio
$\max\left\\{s_{\lambda}/s_{\mu},s_{\mu}/s_{\lambda}\right\\}$.

Altogether, this leads to the following definition. It directly generalizes
the metric introduced in [29], which is a simplified version of the original
metric from [28].

######  Definition 2.4.

Let $\alpha\in[0,1]$. For given parametrizations $(\Lambda,\Phi_{\Lambda})$
and $(\Delta,\Phi_{\Delta})$ with
$(s_{\lambda},e_{\lambda},x_{\lambda})=\Phi_{\Lambda}(\lambda)$ and
$(s_{\mu},e_{\mu},x_{\mu})=\Phi_{\Delta}(\mu)$, the _$\alpha$ -scaled index
distance_ $\omega_{\alpha}:\Lambda\times\Delta\rightarrow[1,\infty)$ is
defined by

$\displaystyle\omega_{\alpha}(\lambda,\mu)=\max\left\\{\frac{s_{\lambda}}{s_{\mu}},\frac{s_{\mu}}{s_{\lambda}}\right\\}\left(1+d_{\alpha}(\lambda,\mu)\right),\qquad\lambda\in\Lambda,\,\mu\in\Delta,$

where with $s_{0}=\min\\{s_{\lambda},s_{\mu}\\}$

$\displaystyle
d_{\alpha}(\lambda,\mu)=s_{0}^{2\alpha}\left|x_{\lambda}-x_{\mu}\right|^{2}+s_{0}^{2(1-\alpha)}\left|\left\\{d_{\mathbb{S}}(e_{\lambda},e_{\mu})\right\\}\right|^{2}+s_{0}\left|\langle
e_{\lambda},x_{\lambda}-x_{\mu}\rangle\right|.$

Let $(\Lambda,\Phi_{\Lambda})$ be a parametrization. Then the induced index
distance on $\Lambda$ is pseudosymmetric and satisfies a pseudo triangle
inequality. More precisely, it has the following properties:

  * (i)

$\omega_{\alpha}(\lambda,\lambda)=1$ for all $\lambda\in\Lambda$,

  * (ii)

$\omega_{\alpha}(\lambda,\lambda^{\prime})\asymp\omega_{\alpha}(\lambda^{\prime},\lambda)$
for all $\lambda,\lambda^{\prime}\in\Lambda$,

  * (iii)

$\omega_{\alpha}(\lambda,\lambda^{\prime})\lesssim\omega_{\alpha}(\lambda,\lambda^{\prime\prime})\omega_{\alpha}(\lambda^{\prime\prime},\lambda^{\prime})$
for all $\lambda,\lambda^{\prime},\lambda^{\prime\prime}\in\Lambda$.

Hence the function $\omega_{\alpha}$ can be viewed as a kind of multiplicative
pseudo-metric. A proof of these properties for the 2-dimensional case can be
found in [29], which translates very well to higher dimensions.

Now we are in a position to formulate the main theorem of this paper. It
states that the index distance – in a certain sense – measures the size of the
scalar products of $\alpha$-molecules.

######  Theorem 2.5.

Let $\alpha\in[0,1]$, $d\in\mathbb{N}$, $d\geq 2$, and let
$(m_{\lambda})_{\lambda\in\Lambda}$ and $(p_{\mu})_{\mu\in\Delta}$ be two
systems of $d$-dimensional $\alpha$-molecules of order $(L,M,N_{1},N_{2})$
with respect to parametrizations $(\Lambda,\Phi_{\Lambda})$ and
$(\Delta,\Phi_{\Delta})$, respectively. Further assume that there exists some
constant $c>0$ such that

$s_{\lambda}\geq c\quad\text{and}\quad s_{\mu}\geq c\quad\text{for all
}\lambda\in\Lambda,\mu\in\Delta\text{ with
}(s_{\lambda},e_{\lambda},x_{\lambda})=\Phi_{\Lambda}(\lambda),(s_{\mu},e_{\mu},x_{\mu})=\Phi_{\Delta}(\mu).$

If $N_{1}>\frac{d}{2}$ and if there exists some positive integer
$N\in\mathbb{N}$ such that

$\displaystyle L\geq 2N,\quad M>3N-d+\frac{1+\alpha(d-1)}{2},\quad N_{1}\geq
N+\frac{1+\alpha(d-1)}{2},\quad N_{2}\geq 2N+d-2,$

then we have

$\displaystyle\left|\langle
m_{\lambda},p_{\mu}\rangle\right|\lesssim\omega_{\alpha}(\lambda,\mu)^{-N}.$

The proof of Theorem 2.5 is very long and technical and for this reason not
presented here but in Section 6. Let us instead discuss the significance of
this result. It states that – with appropriate assumptions on the
parametrizations – the cross-Gramian of two systems of $\alpha$-molecules is
well-localized, in the sense of a fast off-diagonal decay with respect to the
index distance $\omega_{\alpha}$. Put differently, the matrix is close to a
diagonal matrix and the corresponding systems are almost orthogonal to each
other. This property has many implications, see for instance [29, 24]. Its
significance with respect to sparsity equivalence is elaborated in the next
section.

##  3 Sparse Approximation with $\alpha$-Molecules

Based on Theorem 2.5 it is possible to develop a general methodology to
categorize frames of $\alpha$-molecules according to their sparse
approximation behavior. A central concept in this context is the notion of
sparsity equivalence.

Another question that naturally arises in this context is if it is possible
develop a theory of smoothness spaces associated with frames of
$\alpha$-molecules. For such an investigation, coorbit space theory provides
an appropriate abstract framework. Usually however, due to the lack of group
structure, this question can not be handled within the classical theory
developed in [18, 17, 19]. In subsequent contributions, among others [10, 11,
8], the classical theory has seen significant extensions beyond the group
setting. In fact, it is possible to base the theory solely on the notion of an
abstract continuous frame, see [21, 47, 46, 36]. In this general setup
coorbits associated to frames of $\alpha$-molecules can be defined and
investigated.

Up to now, this has only been carried out to some extent and not yet
systematically, i.e., for certain special instances of $\alpha$-molecules. A
particular example are cone-adapted bivariate shearlet systems [44]. The
authors believe that the development of a theory of $\alpha$-molecule
smoothness spaces is beyond the scope of this paper, but certainly a very
interesting possibility for future research. In this paper, we concentrate on
sparse approximations.

###  3.1 Sparse Approximation and Sparsity Equivalence

Let us briefly recall some aspects of approximation theory in a general
(separable) Hilbert space $(\mathcal{H},\langle\cdot,\cdot\rangle)$. Utilizing
a system $(m_{\lambda})_{\lambda\in\Lambda}\subseteq\mathcal{H}$, a signal
$f\in\mathcal{H}$ can be represented by the coefficients
$c_{\lambda}\in\mathbb{C}$ of the expansion

$\displaystyle f=\sum_{\lambda\in\Lambda}c_{\lambda}m_{\lambda}.$ (8)

Suitable representation systems are provided e.g. by so-called frame systems
[6], which ensure stable measurement of the coefficients and also stable
reconstruction. A system $(m_{\lambda})_{\lambda\in\Lambda}$ in $\mathcal{H}$
forms a _frame_ if there exist constants $A,B>0$, called the _frame bounds_ ,
such that

$A\|f\|^{2}\leq\sum_{\lambda\in\Lambda}|\langle f,m_{\lambda}\rangle|^{2}\leq
B\|f\|^{2}\text{ for all }f\in\mathcal{H}.$

If $A$ and $B$ can be chosen equal, the frame is called _tight_. In case
$A=B=1$, one speaks of a _Parseval frame_. The associated frame operator
$S:\mathcal{H}\rightarrow\mathcal{H}$ is given by
$Sf=\sum_{\lambda\in\Lambda}\langle f,m_{\lambda}\rangle m_{\lambda}$.

Since $S$ is always invertible, the system $(S^{-1}m_{\lambda})_{\lambda}$ is
also a frame, referred to as the _canonical dual frame_. It can be used to
compute a particular sequence of coefficients in the expansion (8) via

$c_{\lambda}=\langle f,S^{-1}m_{\lambda}\rangle,\quad\lambda\in\Lambda.$

This sequence however is usually not the only one possible. Unlike the
expansion in a basis, a representation with respect to a frame need not be
unique. The canonical dual frame can also be used to express $f$ in terms of
the frame coefficients $(\langle f,m_{\lambda}\rangle)_{\lambda}$ by

$f=\sum_{\lambda\in\Lambda}\langle f,m_{\lambda}\rangle S^{-1}m_{\lambda}.$

In general, any system $(\tilde{m}_{\lambda})_{\lambda\in\Lambda}$ satisfying
this reconstruction formula is called an associated dual frame.

Let us turn to the question of efficient encoding. In practice we have to
restrict to finite expansions (8), which usually leads to an approximation
error. Given a positive integer $N$, the best $N$-term approximation $f_{N}$
of some element $f\in\mathcal{H}$ with respect to the system
$(m_{\lambda})_{\lambda}$ is defined by

$f_{N}=\mbox{argmin}\Big{\|}f-\sum_{\lambda\in\Lambda_{N}}c_{\lambda}m_{\lambda}\Big{\|}^{2}\quad\mbox{s.t.}\quad\\#\Lambda_{N}\leq
N.$

For efficient approximation, it is desirable to find representation systems
which provide good sparse approximation for the considered data, in the sense
that the approximation error $\|f-f_{N}\|$ decays quickly for
$N\rightarrow\infty$. Typically one wants to approximate signals in some
subclass $\mathcal{C}\subseteq\mathcal{H}$. The approximation performance of a
system with respect to such a class is then usually judged by the worst-case
scenario, i.e. the worst possible decay rate of the error $\|f-f_{N}\|$ for
$f\in\mathcal{C}$. In this sense a system $(m_{\lambda})_{\lambda}$ provides
optimally sparse approximations with respect to $\mathcal{C}$, if its worst-
case approximation rates are the best among all systems.

It is common to consider not the best $N$-term approximation but the $N$-term
approximation, obtained by keeping the $N$ largest coefficients. This
approximation is better understood and provides a bound for the best $N$-term
approximation error. We will also denote it by $f_{N}$, since the context will
always make the meaning clear.

The $N$-term approximation rate achieved by a frame is closely related to the
decay of the corresponding frame coefficients, often measured by a strong or
weak $\ell^{p}$-(quasi-)norm with $p>0$. The weak $\ell^{p}$-(quasi-)norm is
defined by

$\|(c_{\lambda})_{\lambda}\|_{\omega\ell^{p}}:=\Big{(}\sup_{\varepsilon>0}\varepsilon^{p}\cdot\\#\\{\lambda:|c_{\lambda}|>\varepsilon\\}\Big{)}^{1/p},$

and by definition a sequence $(c_{\lambda})_{\lambda}\in\omega\ell^{p}$ if
$\left\|(c_{\lambda})_{\lambda}\right\|_{\omega\ell^{p}}<\infty$. Since
$\left\|(c_{\lambda})_{\lambda}\right\|_{\omega\ell^{p}}\leq\left\|(c_{\lambda})_{\lambda}\right\|_{p}$
for every sequence $(c_{\lambda})_{\lambda}$, we have the embedding
$\ell^{p}\hookrightarrow\omega\ell^{p}$. Note also that every non-increasing
rearrangement $(c^{*}_{n})_{n\in\mathbb{N}}$ of a sequence
$(c_{\lambda})_{\lambda}\in\omega\ell^{p}$ satisfies

$\displaystyle\sup_{n>0}n^{1/p}|c^{\ast}_{n}|=\|(c_{\lambda})_{\lambda}\|_{\omega\ell^{p}}.$

The well-known result below (see [14]), whose proof can be found e.g. in [28],
shows that membership of the expansion coefficients in an $\ell^{p}$ space for
small $p>0$ implies good $N$-term approximation rates.

######  Lemma 3.1 ([28, Lemma 5.1]).

Let $(m_{\lambda})_{\lambda\in\Lambda}$ be a frame in $\mathcal{H}$ and
$f=\sum c_{\lambda}m_{\lambda}$ an expansion of $f\in\mathcal{H}$ with respect
to this frame. If $(c_{\lambda})_{\lambda}\in\omega\ell^{2/(p+1)}(\Lambda)$
for some $p>0$, then the $N$-term approximation rate for $f$ achieved by
keeping the $N$ largest coefficients is at least of order $N^{-p/2}$, i.e.

$\|f-f_{N}\|_{2}^{2}\lesssim N^{-p}.$

In particular, the error of best $N$-term approximation decays at least with
order $N^{-p/2}$.

As illustrated by Lemma 3.1 the decay rate of the frame coefficients
determines the $N$-term approximation rate. In particular, if the sequence
$\left(\left\langle f,m_{\lambda}\right\rangle\right)_{\lambda\in\Lambda}$ of
frame coefficients lies in $\ell^{p}$ for $p<2$, the best approximation rate
of the dual frame $\left(\tilde{m}_{\lambda}\right)_{\lambda\in\Lambda}$ is at
least of order $N^{-(1/p-1/2)}$.

Let us now assume that we have two frames $(m_{\lambda})_{\lambda\in\Lambda}$
and $(p_{\mu})_{\mu\in\Delta}$ in the Hilbert space $\mathcal{H}$ and
expansion coefficients for $f\in\mathcal{H}$ with respect to these two
systems. Then these frames provide the same $N$-term approximation rate for
$f$, if the corresponding expansion coefficients have similar decay, e.g. if
they belong to the same $\ell^{p}$-space. We recall [28, Proposition 5.2] and
formulate this result in an abstract Hilbert space setting.

######  Proposition 3.2 ([28, Proposition 5.2]).

Let $p\in(0,2)$, and let $(m_{\lambda})_{\lambda\in\Lambda}$ and
$(p_{\mu})_{\mu\in\Delta}$ be frames in a Hilbert space $\mathcal{H}$ and
$(\tilde{m}_{\lambda})_{\lambda\in\Lambda}$ a dual frame for
$(m_{\lambda})_{\lambda\in\Lambda}$ such that

$\left\|\left(\langle
m_{\lambda},p_{\mu}\rangle\right)_{\lambda\in\Lambda,\mu\in\Delta}\right\|_{\ell^{p}\to\ell^{p}}<\infty.$

Then $(\langle f,\tilde{m}_{\lambda}\rangle)_{\lambda}\in\ell^{p}(\Lambda)$
implies $(\langle f,p_{\mu}\rangle)_{\mu}\in\ell^{p}(\Delta)$. In particular,
$f\in\mathcal{H}$ can be encoded by the $N$ largest frame coefficients from
$(\langle f,p_{\mu}\rangle)_{\mu}$ up to accuracy $\lesssim N^{-(1/p-1/2)}$.

This proposition motivates the following notion of sparsity equivalence
initially introduced in [27] for parabolic molecules.

######  Definition 3.3 ([27, Definition 4.2]).

Let $p\in(0,\infty]$, and let $(m_{\lambda})_{\lambda\in\Lambda}$ and
$(p_{\mu})_{\mu\in\Delta}$ be frames in a Hilbert space $\mathcal{H}$. Then
$(m_{\lambda})_{\lambda\in\Lambda}$ and $(p_{\mu})_{\mu\in\Delta}$ are
sparsity equivalent in $\ell^{p}$, if

$\left\|\left(\langle{m}_{\lambda},p_{\mu}\rangle\right)_{\lambda\in\Lambda,\mu\in\Delta}\right\|_{\ell^{p}\to\ell^{p}}<\infty.$

Sparsity equivalence, as pointed out in [28], is not an equivalence relation.
Nevertheless, it allows to transfer approximation properties from one anchor
system to other systems.

###  3.2 Consistency of Parametrizations

Our aim in this section is to categorize frames of $\alpha$-molecules in
$L^{2}(\mathbb{R}^{d})$ with respect to their approximation behavior, building
upon the notion of sparsity equivalence. We emphasize that a system of
$\alpha$-molecules does not per se constitute a frame. In fact, the question
if a system of functions in $L^{2}(\mathbb{R}^{d})$ is a frame is decoupled
from the question if it forms a system of $\alpha$-molecules.

Theorem 3.7 will provide sufficient conditions for two frames of
$\alpha$-molecules to be sparsity equivalent, based upon the notion of
($\alpha,k$)-consistency originally introduced in [28]. To motivate this
concept, we recall a simple estimate from [27] for the operator norm of a
matrix on discrete $\ell^{p}$ spaces.

######  Lemma 3.4 ([27, Lemma 4.4]).

Let $\Lambda,\Delta$ be two discrete index sets, and let ${\bf
A}:\ell^{p}(\Lambda)\to\ell^{p}(\Delta)$, $p>0$ be a linear mapping defined by
its matrix representation ${\bf
A}=\left(A_{\lambda,\mu}\right)_{\lambda\in\Lambda,\,\mu\in\Delta}$. Then we
have the bound

$\|{\bf
A}\|_{\ell^{p}(\Lambda)\to\ell^{p}(\Delta)}\leq\max\left\\{\sup_{\lambda}\sum_{\mu}|A_{\lambda,\mu}|^{\min\\{1,p\\}},\sup_{\mu}\sum_{\lambda}|A_{\lambda,\mu}|^{\min\\{1,p\\}}\right\\}^{1/\min\\{1,p\\}}.$

We apply this lemma to the cross-Gramian ${\bf A}$ of two systems of
$\alpha$-molecules, and aim for sufficient conditions for the right hand side
to be finite. The following notion was introduced in [28].

######  Definition 3.5 ([28, Definition 5.5]).

Let $\alpha\in[0,1]$ and $k>0$. Two parametrizations
$(\Lambda,\Phi_{\Lambda})$ and $(\Delta,\Phi_{\Delta})$ are called _(
$\alpha,k$)-consistent_, if

$\displaystyle\sup_{\lambda\in\Lambda}\sum_{\mu\in\Delta}\omega_{\alpha}\left(\lambda,\mu\right)^{-k}<\infty\quad\text{and}\quad\sup_{\mu\in\Delta}\sum_{\lambda\in\Lambda}\omega_{\alpha}\left(\lambda,\mu\right)^{-k}<\infty.$
(9)

######  Remark 3.6.

Note that due to symmetry of the distance function $\omega_{\alpha}$ it
suffices to check only one of the two conditions in equation (9) to prove
$(\alpha,k)$-consistency.

In view of Theorem 2.5, the consistency of the parametrizations of two systems
of $\alpha$-molecules provides a convenient sufficient condition for their
sparsity equivalence.

######  Theorem 3.7.

Let $\alpha\in[0,1]$, $d\in\mathbb{N}$, $d\geq 2$, $k>0$, and
$p\in(0,\infty]$. Let $(m_{\lambda})_{\lambda\in\Lambda}$ and
$(p_{\mu})_{\mu\in\Delta}$ be two frames of $d$-dimensional $\alpha$-molecules
of order $(L,M,N_{1},N_{2})$ with ($\alpha,k$)-consistent parametrizations
$(\Lambda,\Phi_{\Lambda})$ and $(\Delta,\Phi_{\Delta})$ satisfying

$s_{\lambda}\geq c,s_{\mu}\geq c\text{ for all
}\lambda\in\Lambda,\mu\in\Delta$

and with $q:=\min\\{1,p\\}$

$L\geq 2\frac{k}{q},\quad M>3\frac{k}{q}-d+\frac{1+\alpha(d-1)}{2},\quad
N_{1}>\frac{d}{2},\>N_{1}\geq\frac{k}{q}+\frac{1+\alpha(d-1)}{2},\quad
N_{2}\geq 2\frac{k}{q}+d-2.$

Then $(m_{\lambda})_{\lambda\in\Lambda}$ and $(p_{\mu})_{\mu\in\Delta}$ are
sparsity equivalent in $\ell^{p}$.

###### Proof.

Let $q:=\min\\{1,p\\}$. By Lemma 3.4, it suffices to prove that

$\max\left\\{\sup_{\lambda\in\Lambda}\sum_{\mu\in\Delta}|\langle
m_{\lambda},p_{\mu}\rangle|^{q},\sup_{\mu\in\Delta}\sum_{\lambda\in\Lambda}|\langle
m_{\lambda},p_{\mu}\rangle|^{q}\right\\}^{1/q}<\infty.$

Since, by Theorem 2.5, we have $|\langle
m_{\lambda},p_{\mu}\rangle|\lesssim\omega_{\alpha}(\lambda,\mu)^{-k/q},$ we
can conclude that

$\max\left\\{\sup_{\lambda\in\Lambda}\sum_{\mu\in\Delta}|\langle
m_{\lambda},p_{\mu}\rangle|^{q},\sup_{\mu\in\Delta}\sum_{\lambda\in\Lambda}|\langle
m_{\lambda},p_{\mu}\rangle|^{q}\right\\}\lesssim\max\left\\{\sup_{\lambda\in\Lambda}\sum_{\mu\in\Delta}\omega_{\alpha}(\lambda,\mu)^{-k},\sup_{\mu\in\Delta}\sum_{\lambda\in\Lambda}\omega_{\alpha}(\lambda,\mu)^{-k}\right\\}$

with the expression on the right hand side being finite due to the
$(\alpha,k)$-consistency of the parametrizations $(\Lambda,\Phi_{\Lambda})$
and $(\Delta,\Phi_{\Delta})$. The proof is completed. ∎

This theorem allows to categorize frames of $\alpha$-molecules according to
their sparse approximation behavior. The general strategy is as follows. If an
approximation result for a specific system of $\alpha$-molecules is known and
a class of $\alpha$-molecules satisfies the hypotheses of Theorem 3.7, i.e.
they are all sparsity equivalent to this specific system, they automatically
inherit its known approximation behavior. In this way, one in the end obtains
a stand-alone result for frames of $\alpha$-molecules to exhibit sparse
approximation, depending solely on the parametrization and the order.

##  4 Sparse Approximation of Video Data

In this section we demonstrate with a specific example how the machinery of
$\alpha$-molecules can be applied in practice. In our exemplary application,
we are interested in the sparse representation of video signals, modelled by
the class of cartoon-like functions $\mathcal{E}^{2}(\mathbb{R}^{3})$
introduced below.

Following the general methodology, we first need a suitable anchor system, for
which a sparse approximation result with respect to
$\mathcal{E}^{2}(\mathbb{R}^{3})$ is known. Utilizing Theorem 3.7 the
framework can then transfer the approximation rate from this reference system
to other systems. In this way we will be able to identify a large class of
representation systems, which provide almost optimal sparse approximation for
$\mathcal{E}^{2}(\mathbb{R}^{3})$.

###  4.1 Cartoon-like Functions

A suitable model for image and video data is provided by the class of cartoon-
like functions, first introduced by Donoho [15] and later extended e.g. in
[41]. We shall use the following simplified model in dimensions $d=2$ and
$d=3$.

######  Definition 4.1 ([15],[41, Definition 2.1]).

For fixed $\nu>0$ and $d\in\\{2,3\\}$ the _class
$\mathcal{E}^{2}(\mathbb{R}^{d})$ of cartoon-like functions_ consists of
functions $f:\mathbb{R}^{d}\rightarrow\mathbb{C}$ of the form

$f=f_{0}+f_{1}\chi_{B},$

where $B\subset[0,1]^{d}$ and $f_{i}\in C^{2}(\mathbb{R}^{d})$ with
$\text{supp }f_{i}\subset[0,1]^{d}$ and $\|f_{i}\|_{C^{2}}\leq 1$ for each
$i=0,1$. For dimension $d=2$, we assume that the boundary $\partial B$ is a
closed $C^{2}$-curve with curvature bounded by $\nu$, and, for $d=3$, the
discontinuity $\partial B$ shall be a closed $C^{2}$-surface with principal
curvatures bounded by $\nu$.

This model is justified by the observation that real-life images and video
data typically consist of smooth regions, separated by piecewise smooth
boundaries. Without loss of generality we restrict in Definition 4.1 to
cartoon-like functions with smooth boundaries.

###  4.2 Optimal Approximation for Cartoon-like Functions

In [15, 41] the optimal approximation rates for
$\mathcal{E}^{2}(\mathbb{R}^{2})$ and $\mathcal{E}^{2}(\mathbb{R}^{3})$,
achievable with algorithms satisfying a _polynomial depth search_ constraint,
were derived. An algorithm for sparse approximation is thereby restricted to
polynomial depth search in a given (countable) dictionary, if there exists a
polynomial $\pi$ such that the algorithm only chooses from the first $\pi(N)$
vectors of the dictionary when forming the $N$:th sparse approximation [15].
Such a constraint is very natural from a practical standpoint and has the nice
side-effect that it ensures the existence of the best $N$-term approximation.
In general, this may not be the case, as the instance of a countable dense
subset of $L^{2}(\mathbb{R}^{d})$ as a dictionary shows. Here the best
$1$-term approximation does not always exist.

We now cite the result of [15, 41]. In [41] it is conjectured that the result
also generalizes to higher dimensions.

######  Theorem 4.2 ([15, Theorem 7.2],[41, Theorem 3.2]).

Let $d\in\\{2,3\\}$. The best $N$-term approximation rate for
$\mathcal{E}^{2}(\mathbb{R}^{d})$, achieved by an arbitrary dictionary under
the restriction of polynomial depth search, cannot exceed

$\|f-f_{N}\|_{2}^{2}\lesssim N^{-\frac{2}{d-1}},$

where $f_{N}$ is the best $N$-term approximation of
$f\in\mathcal{E}^{2}(\mathbb{R}^{d})$.

For $d=2$ it has been shown that this rate can indeed be achieved [15] using
so-called wedgelets, which are adaptive to the data. Moreover, there are
several examples of non-adaptive frames in two and three dimensions which
almost provide these optimal rates [5, 31, 38, 33, 41], typically up to log-
terms. In particular, it was proven by Guo and Labate in [33] that the smooth
Parseval frame of band-limited 3D-shearlets $SH$ constructed by them in [34]
sparsely approximates the class $\mathcal{E}^{2}(\mathbb{R}^{3})$ with an
almost optimal approximation rate. We recall the definition of this particular
system in Subsection 5.3.1 and state the approximation result below.

######  Theorem 4.3 ([33, Theorem 3.1]).

Let $SH=\\{\psi_{\lambda}\\}_{\lambda\in\Lambda_{SH}}$ be the smooth Parseval
frame of 3D-shearlets defined in Subsection 5.3.1. Then the sequence of
shearlet coefficients $\theta_{\lambda}(f):=\langle f,\psi_{\lambda}\rangle$,
$\lambda\in\Lambda_{SH}$, associated with
$f\in\mathcal{E}^{2}(\mathbb{R}^{3})$ satisfies

$\sup_{f\in\mathcal{E}^{2}(\mathbb{R}^{3})}|\theta_{\lambda}(f)|_{N}\lesssim
N^{-1}\cdot\log(N),$

where $|\theta_{\lambda}(f)|_{N}$ denotes the $N$:th largest shearlet
coefficient.

Theorem 4.3 shows that the shearlet coefficients belong to
$\omega\ell^{p}(\Lambda_{SH})$ for every $p>1$. In view of Lemma 3.1, for
every $f\in\mathcal{E}^{2}(\mathbb{R}^{3})$, the frame $SH$ therefore provides
at least the approximation rate

$\displaystyle\|f-f_{N}\|_{2}^{2}\lesssim
N^{-1+\varepsilon}\quad,\text{$\varepsilon>0$ arbitrary},$ (10)

where $f_{N}$ denotes the $N$-term approximation obtained from the $N$ largest
coefficients. According to Theorem 4.2, this is almost the optimal
approximation rate achievable for cartoon-like functions
$\mathcal{E}^{2}(\mathbb{R}^{3})$. For small $\varepsilon>0$, we get
arbitrarily close to the optimal rate.

The idea to use 3D-shearlets for processing video data has been tested in
practice in [45]. The authors of said article develop a clever discretisation
procedure, allowing a fast computation of the shearlet coefficients. They then
test how their discrete shearlet transform can be used to denoise and enhance
video sequences, with promising results.

###  4.3 Transfer of the Approximation Rate

Our final goal is to find a large class of representation systems which
achieve the almost optimal rate (10). For this, we put the machinery of
$\alpha$-molecules to work. Via Theorem 3.7 it is possible to transfer the
approximation rate (10) established for the smooth Parseval frame of
$3$D-shearlets $SH$ to other systems of 3-dimensional $\frac{1}{2}$-molecules.
In fact, the frame $SH$ is a suitable choice for the reference system, since
by Proposition 5.9 it constitutes a system of 3-dimensional
$\frac{1}{2}$-molecules of order $(\infty,\infty,\infty,\infty)$ with respect
to the parametrization $(\Lambda_{SH},\Phi_{SH})$ The following result is then
a direct application of the general theory.

######  Theorem 4.4.

Assume that a frame $(m_{\lambda})_{\lambda\in\Lambda}$ of $3$-dimensional
$\frac{1}{2}$-molecules satisfies, for some $k>0$, the following two
conditions:

  * (i)

its parametrization $(\Lambda,\Phi_{\Lambda})$ is ($\frac{1}{2},k$)-consistent
with $(\Lambda_{SH},\Phi_{SH})$,

  * (ii)

its order $(L,M,N_{1},N_{2})$ satisfies

$L\geq 2k,\quad M\geq 3k-2,\quad N_{1}\geq k+1,\quad N_{1}>3/2,\quad N_{2}\geq
2k+1.$

Then each dual frame $(\tilde{m}_{\lambda})_{\lambda\in\Lambda}$ possesses an
almost optimal $N$-term approximation rate for the class of cartoon-like
functions ${\cal E}^{2}(\mathbb{R}^{3})$, i.e. for all
$f\in\mathcal{E}^{2}(\mathbb{R}^{3})$

$\|f-f_{N}\|_{2}^{2}\lesssim N^{-1+\varepsilon},\quad\varepsilon>0\text{
arbitrary},$

where $f_{N}$ denotes the $N$-term approximation obtained from the $N$ largest
frame coefficients.

###### Proof.

Let $SH=\\{\psi_{\lambda}\\}_{\lambda\in\Lambda_{SH}}$ be the Parseval frame
of $3$D-shearlets from Subsection 5.3.1, and take
$f\in\mathcal{E}^{2}(\mathbb{R}^{3})$. By Theorem 4.3 the sequence of shearlet
coefficients $(\theta_{\lambda})_{\lambda}$ given by $\theta_{\lambda}=\langle
f,\psi_{\lambda}\rangle$ belongs to $\omega\ell^{p}(\Lambda_{SH})$ for every
$p>1$. Since $\omega\ell^{p}\hookrightarrow\ell^{p+\epsilon}$ for arbitrary
$\varepsilon>0$, this further implies
$(\theta_{\lambda})_{\lambda}\in\ell^{p}(\Lambda_{SH})$ for every $p>1$. Let
now

$f=\sum_{\mu\in\Lambda}c_{\mu}\tilde{m}_{\mu}$

be the canonical expansion of $f$ with respect to the dual frame
$(\tilde{m}_{\mu})_{\mu}$, with frame coefficients $(c_{\mu})_{\mu}$. Note
that since $SH$ is a Parseval frame, the canonical dual frame of $SH$ is equal
to $SH$ itself. Therefore the coefficents are given by

$c_{\mu}=\langle
f,m_{\mu}\rangle=\Big{\langle}\sum_{\lambda}\theta_{\lambda}\psi_{\lambda},m_{\mu}\Big{\rangle}=\sum_{\lambda}\langle\psi_{\lambda},m_{\mu}\rangle\theta_{\lambda}.$

Thus, they are related to the shearlet coefficients
$(\theta_{\lambda})_{\lambda}$ by the cross-Gramian
$(\langle\psi_{\lambda},m_{\mu}\rangle)_{\lambda,\mu}$. By Theorem 3.7,
conditions (i) and (ii) guarantee that the frame $(m_{\mu})_{\mu\in\Lambda}$
is sparsity equivalent to $(\psi_{\lambda})_{\lambda\in\Lambda_{SH}}$ in
$\ell^{p}$ for every $p>1$. This implies that the cross-Gramian is a bounded
operator $\ell^{p}(\Lambda_{SH})\rightarrow\ell^{p}(\Lambda)$, which maps
$(\theta_{\lambda})_{\lambda}$ to $(c_{\mu})_{\mu}$. Hence,
$(c_{\mu})_{\mu}\in\ell^{p}(\Lambda)$ for every $p>1$. The embedding
$\ell^{p}\hookrightarrow\omega\ell^{p}$ then proves
$(c_{\mu})_{\mu}\in\omega\ell^{p}(\Lambda)$ for every $p>1$. Finally, for
arbitrary $\varepsilon>0$, the application of Lemma 3.1 yields

$\|f-f_{N}\|_{2}^{2}\lesssim N^{-1+\varepsilon},$

where $f_{N}$ denotes the $N$-term approximation with respect to the system
$(\tilde{m}_{\mu})_{\mu}$ obtained by choosing the $N$ largest coefficients. ∎

Theorem 4.4 specifies a large class of multiscale systems with almost optimal
approximation performance for video data $\mathcal{E}^{2}(\mathbb{R}^{3})$.
According to Remark 5.11 condition (i) is in particular fulfilled by every
$\frac{1}{2}$-shearlet parametrization (see Theorem 5.3) for $k>3$. Hence, due
to condition (ii) all systems of 3-dimensional $\frac{1}{2}$-shearlet
molecules of order

$L\geq 7,\quad M\geq 8,\quad N_{1}\geq 5,\quad N_{2}\geq 8,$

provide almost optimal approximation for $\mathcal{E}^{2}(\mathbb{R}^{3})$.

Taking into account Proposition 5.12, the statement of Theorem 4.4 in
particular includes the following result for compactly supported shearlet
frames.

######  Corollary 4.5.

Any dual frame of a shearlet frame of the form (27) generated by compactly
supported functions $\phi,\psi^{1},\psi^{2},\psi^{3}\in
L^{2}(\mathbb{R}^{3})$, so that $\phi\in C^{13}(\mathbb{R}^{3})$ and so that
for each $\varepsilon\in\\{1,2,3\\}$

  1. (i)

$\partial^{\gamma}\psi^{\varepsilon}$ exists and is continuous for every
$\gamma=(\gamma_{1},\gamma_{2},\gamma_{3})^{T}\in\mathbb{N}_{0}^{3}$ with
$|\gamma|_{\infty}\leq 13$ and $\gamma_{\varepsilon}\leq 5$,

  2. (ii)

$\psi^{\varepsilon}$ has at least 15 vanishing directional moments in
direction $e_{\varepsilon}$,

provides the almost optimal approximation rate (10) for the cartoon video
class $\mathcal{E}^{2}(\mathbb{R}^{3})$.

This corollary is a new result for compactly supported shearlets on its own. A
similar result was proved in [41]. In comparison the most intriguing fact is
the simplicity of its deduction: The framework of $\alpha$-molecules enables a
simple transport of the decay rates.

######  Remark 4.6.

The 2-dimensional counterpart of Theorem 4.4 is contained in [28, Theorem
5.12] for the choice $\alpha=\frac{1}{2}$. In [28] it is further shown that
not only any system of bivariate $\frac{1}{2}$-shearlet molecules satisfies
the conditions of this theorem, provided that the order is sufficiently high,
but also every system of sufficiently high order $\frac{1}{2}$-curvelet
molecules. This implies that also curvelet-like constructions yield almost
optimal approximation for the class $\mathcal{E}^{2}(\mathbb{R}^{2})$,
including the classical curvelet frame.

In contrast, a ‘true’ curvelet construction in 3D is not known to the authors.
Note that, despite the misleading name, the construction of the ‘$3D$ discrete
curvelet transform’ in [49] is actually shear-based. Still, it can be expected
that any curvelet-like system would fall into our framework, and thus Theorem
4.4 would immediately establish the almost optimal approximation rate.

##  5 Shearlet Systems in $d$ Dimensions

We introduce a very general class of shear-based systems, namely _systems of
$\alpha$-shearlet molecules_. The definition in $d$ dimensions is analogue to
the 2-dimensional case [28]. Roughly speaking, they are shear-based systems
obtained from variable generators, where similar to $\alpha$-molecules the
conditions on the generators have been relaxed to a mere time-frequency
localization requirement. The notion of $\alpha$-shearlet molecules comprises
many specific shear-based constructions and simplifies the treatment of such
systems within the general framework of $\alpha$-molecules.

###  5.1 Multidimensional $\alpha$-Shearlet Molecules

As explained in Section 1, shearlet-like constructions are based on
anisotropic scaling, shearings, and translations. For the change of scale, we
utilize $\alpha$-scaling as defined by (5). The change of orientation is
provided by shearings, in $d$ dimensions given by the shearing matrices

$\displaystyle S_{h}=\begin{pmatrix}I_{d-1}&0\\\
h^{T}&1\end{pmatrix}\quad\text{and}\quad S^{T}_{h}=\begin{pmatrix}I_{d-1}&h\\\
0&1\end{pmatrix},\quad h\in\mathbb{R}^{d-1},$

which are the natural generalizations of (2). The matrix $S^{T}_{h}$ shears
parallel to the $(e_{1},\ldots,e_{d-1})$-plane and the shear vector
$h\in\mathbb{R}^{d-1}$ determines the direction of the shearing in this plane.
The transformations associated with shearings and $\alpha$-scalings naturally
form a group [9].

To avoid directional bias, the frequency domain is divided into cone-like
regions along the coordinate axes and a coarse-scale box for the low
frequencies. Note that this comes at the cost of losing the group properties
mentioned above. This division procedure is however crucial for applications,
and also, as the subsequent arguments will show, for including
$\alpha$-shearlets in the concept of $\alpha$-molecules. The cone-like regions
along the $e_{\varepsilon}$-axes shall be called _pyramids_ and are explicitly
given by

$\displaystyle\mathcal{P}_{\varepsilon}=\left\\{(\xi_{1},\dots,\xi_{d})^{T}\in\mathbb{R}^{d}\leavevmode\nobreak\
|\leavevmode\nobreak\ \forall
i\in\\{1,\ldots,d\\}:\left|\xi_{i}\right|\leq\left|\xi_{\varepsilon}\right|\right\\},$

where $\varepsilon\in\left\\{1,\ldots,d\right\\}$. $\varepsilon=0$ shall refer
to a coarse-scale box of the form
$\mathcal{R}=\\{\xi\in\mathbb{R}^{d}:|\xi|_{\infty}\leq C\\}$, where $C>0$ is
a suitably chosen constant. In the sequel we will always stay in this so-
called cone-adapted setting. For an illustration of this specific setting in
3D, we refer to Subsection 5.3.

In each cone we require different versions of the scaling and shearing
operators. The cyclic permutation matrix

$\displaystyle Z=\begin{pmatrix}0&1\\\ I_{d-1}&0\end{pmatrix}$ (11)

allows to elegantly define these operators associated with the respective
cones by $Z^{\varepsilon}S_{h}Z^{-\varepsilon}$ and
$Z^{\varepsilon}A_{\alpha,s}Z^{-\varepsilon}$.

Before we come to the definition of $\alpha$-shearlet molecules, we need to
introduce a set of characteristic parameters, associated with these systems.
The resolution of the underlying sampling grid is determined by the parameters
$\sigma>1$, $\tau_{1},\ldots,\tau_{d}>0$, and a sequence
$\Theta=(\eta_{j})_{j\in\mathbb{N}_{0}}\subset\mathbb{R}_{+}$. The parameter
$\sigma$ specifies the fineness of the scale sampling. The parameters
$\tau_{\varepsilon}$, $\varepsilon\in\\{1,\ldots,d\\}$, determine the spatial
resolution in the $e_{\varepsilon}$-direction. For convenience they are
summarized in the diagonal matrix $\mathcal{T}:={\text{\rm
diag}}(\tau_{1},\ldots,\tau_{d})\in\leavevmode\nobreak\ \mathbb{R}^{d\times
d}$. The angular resolution at each scale $j\in\mathbb{N}_{0}$ is given by the
value $\eta_{j}$ of the sequence $\Theta$. Last but not least, in each cone
$\varepsilon\in\\{1,\ldots,d\\}$ and at each scale $j\in\mathbb{N}_{0}$ the
shearing parameter $\ell$ is restricted to a set
$\mathscr{L}_{\varepsilon,j}\subseteq\mathbb{Z}^{d-1}$. These sets are
collected in
$\mathscr{L}:=\\{\mathscr{L}_{\varepsilon,j}:\varepsilon\in\\{1,\ldots,d\\},\,j\in\mathbb{N}_{0}\\}$.

After the introduction of this sampling data
$\mathbb{D}:=\\{\sigma,\Theta,\mathscr{L},\mathcal{T}\\}$ we can now give the
definition of a system of $\alpha$-shearlet molecules in $d$ dimensions,
depending on $\mathbb{D}$. The scale-dependent step size $\eta_{j}$ of the
directional sampling is assumed to satisfy
$\eta_{j}\asymp\sigma^{-j(1-\alpha)}$ for $j\in\mathbb{N}_{0}$. Further, we
require the upper bounds
$\mathbb{L}_{j}:=\max\big{\\{}|\ell|_{\infty}:\ell\in\mathscr{L}_{\varepsilon,j},\varepsilon\in\\{1,\ldots,d\\}\big{\\}}$,
$j\in\mathbb{N}_{0}$, to fulfill the complementary condition
$\mathbb{L}_{j}\lesssim\sigma^{j(1-\alpha)}$. We remark that the translation
parameters $\tau_{\varepsilon}$ may also vary with the indices
$(\varepsilon,j,\ell)$, as long as their values are restricted to some fixed
interval ${[}\tau_{min},\tau_{max}{]}$ with
$0<\tau_{min}\leq\tau_{max}<\infty$. However, this is not indicated in the
notation.

######  Definition 5.1.

Let $\alpha\in[0,1]$, $d\in\mathbb{N}$, $d\geq 2$, and
$L,M,N_{1},N_{2}\in\mathbb{N}_{0}\cup\\{\infty\\}$. Further the sampling data
$\mathbb{D}$ shall be given as above. For
$\varepsilon\in\left\\{1,\ldots,d\right\\}$, a system of functions

$\Sigma_{\varepsilon}:=\Big{\\{}m^{\varepsilon}_{j,\ell,k}\in
L^{2}(\mathbb{R}^{d})\leavevmode\nobreak\ :\leavevmode\nobreak\
(j,\ell,k)\in\Lambda^{s}_{\varepsilon}\Big{\\}},$

indexed by the set
$\Lambda^{s}_{\varepsilon}:=\big{\\{}(j,\ell,k)\leavevmode\nobreak\
:\leavevmode\nobreak\
j\in\mathbb{N}_{0},\,\ell\in\mathscr{L}_{\varepsilon,j}\subseteq\mathbb{Z}^{d-1},\,k\in\mathbb{Z}^{d}\big{\\}},$
is called a _system of $d$-dimensional $\alpha$-shearlet molecules of order
$(L,M,N_{1},N_{2})$ associated with the orientation $\varepsilon$_, if it is
of the form

$\displaystyle
m_{j,\ell,k}^{\varepsilon}(x)=\sigma^{\frac{(1+\alpha(d-1))j}{2}}\gamma^{\varepsilon}_{j,\ell,k}\big{(}Z^{\varepsilon}A^{j}_{\alpha,\sigma}S_{\ell\eta_{j}}Z^{-\varepsilon}x-\mathcal{T}k\big{)}$
(12)

with generating functions $\gamma^{\varepsilon}_{j,\ell,k}\in
L^{2}(\mathbb{R}^{d})$ satisfying for every $\rho\in\mathbb{N}_{0}^{d}$ with
$|\rho|_{1}\leq L$

$\displaystyle\left|\partial^{\rho}\hat{\gamma}^{\varepsilon}_{j,\ell,k}(\xi)\right|\lesssim\frac{\min\\{1,\sigma^{-j}+\sigma^{-(1-\alpha)j}|Z^{-\varepsilon}\xi|_{[d-1]}+\left|[Z^{-\varepsilon}\xi]_{d}\right|\\}^{M}}{\langle\left|\xi\right|\rangle^{N_{1}}\langle\left|Z^{-\varepsilon}\xi\right|_{[d-1]}\rangle^{N_{2}}}.$
(13)

The implicit constant is required to be uniform over
$\Lambda^{s}_{\varepsilon}$. If one of the parameters $L,M,N_{1},N_{2}$ takes
the value $\infty$, this shall mean that condition (13) is fulfilled with the
respective quantity arbitrarily large.

Combining systems of $\alpha$-shearlet molecules of order $(L,M,N_{1},N_{2})$
for each orientation $\varepsilon\in\left\\{1,\ldots,d\right\\}$ with a system
of coarse-scale elements

$\displaystyle\Sigma_{0}:=\Big{\\{}m^{0}_{0,{\bf 0},k}:=\gamma^{0}_{0,{\bf
0},k}(\cdot-\mathcal{T}k)\leavevmode\nobreak\ :\leavevmode\nobreak\
k\in\mathbb{Z}^{d}\Big{\\}},$ (14)

where the generators $\gamma^{0}_{0,{\bf 0},k}\in L^{2}(\mathbb{R}^{d})$
fulfill $|\partial^{\rho}\hat{\gamma}^{0}_{0,{\bf
0},k}(\xi)|\lesssim\langle\left|\xi\right|\rangle^{-N_{1}}\langle\left|\xi\right|_{[d-1]}\rangle^{-N_{2}}$
for every $\rho\in\mathbb{N}_{0}^{d}$ with $|\rho|_{1}\leq L$, yields a
_system of $\alpha$-shearlet molecules_ of order $(L,M,N_{1},N_{2})$. The
associated index set is

$\displaystyle\Lambda^{s}_{0}:=\Big{\\{}(0,{\bf
0},k):k\in\mathbb{Z}^{d}\Big{\\}}\subseteq\mathbb{N}_{0}\times\mathbb{Z}^{d-1}\times\mathbb{Z}^{d}.$

######  Definition 5.2.

For each $\varepsilon\in\\{1,\ldots,d\\}$, let $\Sigma_{\varepsilon}$ be a
system of $\alpha$-shearlet molecules of order $(L,M,N_{1},N_{2})$ associated
with the respective orientation. Further, let $\Sigma_{0}$ be a system of
coarse-scale scale elements defined as in (14). Then the union

$\Sigma:=\bigcup_{\varepsilon=0}^{d}\Sigma_{\varepsilon}$

is called a _system of $\alpha$-shearlet molecules of order
$(L,M,N_{1},N_{2})$_. The associated _shearlet index set_ is given by

$\Lambda^{s}=\\{(\varepsilon,j,\ell,k):\varepsilon\in\\{0,\ldots,d\\},\,(j,\ell,k)\in\Lambda^{s}_{\varepsilon}\\}.$

Next, we prove that the system $\Sigma$ is a system of $\alpha$-molecules.

######  Theorem 5.3.

Let $\alpha\in[0,1]$ and $\Sigma$ be a system of $\alpha$-shearlet molecules
of order $(L,M,N_{1},N_{2})$. Then $\Sigma$ constitutes a system of
$\alpha$-molecules of the same order. The associated _$\alpha$ -shearlet
parametrization_ $(\Lambda^{s},\Phi^{s})$ is given by the map
$\Phi^{s}(\lambda)=(s_{\lambda},e_{\lambda},x_{\lambda})\in\mathbb{P}_{d}$ for
$\lambda=(\varepsilon,j,\ell,k)\in\Lambda^{s}$, where

$\displaystyle s_{\lambda}=\sigma^{j},\quad e_{\lambda}=n_{\lambda}\cdot
Z^{\varepsilon}\begin{pmatrix}\eta_{j}\ell\\\ 1\end{pmatrix},\quad
x_{\lambda}=Z^{\varepsilon}S^{-1}_{\ell\eta_{j}}A^{-j}_{\alpha,\sigma}Z^{-\varepsilon}\mathcal{T}k,$
(15)

and $n_{\lambda}=(1+\eta_{j}^{2}\left|\ell\right|_{2}^{2})^{-1/2}$ is a
normalization constant.

In particular for $\varepsilon=0$ we have $s_{\lambda}=1$, $e_{\lambda}=e_{d}$
and $x_{\lambda}=\mathcal{T}k$ for every $\lambda=(0,0,{\bf
0},k)\in\Lambda^{s}$.

###### Proof.

Since a finite union of systems of $\alpha$-molecules is itself a system of
$\alpha$-molecules, we can prove this theorem separately for each system
$\Sigma_{\varepsilon}$, $\varepsilon\in\\{0,\ldots,d\\}$. For $\Sigma_{0}$ the
statement is obvious. For the other systems it suffices to give the proof for
$\varepsilon=d$, since they are all related by a mere permutation of indices.
We subsequently drop the index $\varepsilon$ to simplify the notation and note
$Z^{\varepsilon}=I$ for $\varepsilon=d$.

For the proof we introduce the index set
$\Lambda^{s,d}:=\\{(d,j,\ell,k)\leavevmode\nobreak\ :\leavevmode\nobreak\
(j,\ell,k)\in\Lambda^{s}_{d}\\}$. Let $\lambda=(d,j,\ell,k)\in\Lambda^{s,d}$
and $m_{\lambda}:=m^{d}_{j,\ell,k}$ the associated $\alpha$-shearlet molecule
with corresponding generating function
$\gamma_{\lambda}:=\gamma^{d}_{j,\ell,k}$. As usual we denote the angles
representing the orientation $e_{\lambda}$ by
$(\theta_{\lambda},\varphi_{\lambda})$, i.e.
$e_{\lambda}=R^{T}_{\varphi_{\lambda}}R^{T}_{\theta_{\lambda}}e_{d}$. The
molecule $m_{\lambda}$ can clearly be written in the form (6) with respect to
the generator

$\displaystyle
g_{\lambda}(x):=\gamma_{\lambda}(A^{j}_{\alpha,\sigma}S_{\ell\eta_{j}}R_{\varphi_{\lambda}}^{T}R_{\theta_{\lambda}}^{T}A^{-j}_{\alpha,\sigma}x),\quad
x\in\mathbb{R}^{d}.$

It remains to check condition (7) for these functions. On the Fourier side we
have

$\displaystyle\hat{g}_{\lambda}(\xi)=\hat{\gamma}_{\lambda}(A^{-j}_{\alpha,\sigma}S_{\ell\eta_{j}}^{-T}R_{\varphi_{\lambda}}^{T}R_{\theta_{\lambda}}^{T}A^{j}_{\alpha,\sigma}\xi),\quad\xi\in\mathbb{R}^{d}.$

For $\lambda=(d,j,\ell,k)\in\Lambda^{s,d}$ let us first examine the matrix

$\displaystyle
M_{\lambda}:=S_{\ell\eta_{j}}^{-T}R_{\varphi_{\lambda}}^{T}R_{\theta_{\lambda}}^{T}.$
(16)

A simple calculation shows
$M_{\lambda}e_{d}=S_{\ell\eta_{j}}^{-T}R_{\varphi_{\lambda}}^{T}R_{\theta_{\lambda}}^{T}e_{d}=S_{\ell\eta_{j}}^{-T}e_{\lambda}=S_{\ell\eta_{j}}^{-T}n_{\lambda}(\eta_{j}\ell,1)^{T}=n_{\lambda}e_{d}.$
Hence, the entries of the last column of $M_{\lambda}$ vanish except for the
last one. Next, we prove the uniform boundedness of the set of operators
$\\{M_{\lambda}\\}_{\lambda\in\Lambda^{s,d}}$. It holds uniformly for
$\lambda\in\Lambda^{s,d}$

$\|M_{\lambda}\|_{2\rightarrow 2}=\|S_{\ell\eta_{j}}^{-T}\|_{2\rightarrow
2}=\sqrt{1+\eta_{j}^{2}|\ell|^{2}_{2}}\lesssim\sqrt{1+\eta_{j}^{2}\mathbb{L}_{j}^{2}}\lesssim
1.$

Note that this implies that each entry in $M_{\lambda}$ is bounded in modulus.
Since similar considerations hold for the inverse
$M^{-1}_{\lambda}=R_{\theta_{\lambda}}R_{\varphi_{\lambda}}S_{\ell\eta_{j}}^{T},$
we can conclude that both
$\widetilde{M}_{\lambda}:=A^{-j}_{\alpha,\sigma}M_{\lambda}A^{j}_{\alpha,\sigma}$
and its inverse $\widetilde{M}^{-1}_{\lambda}$ have the form

$\displaystyle\begin{pmatrix}*&\dots&*&0\\\ \vdots&\ddots&\vdots&\vdots\\\
*&\dots&*&0\\\ \square&\dots&\square&*\end{pmatrix},$

where the entries $*$ are the same as in $M_{\lambda}$ (or $M^{-1}_{\lambda}$)
and the entries $\square$ are of the form
$\sigma^{-j(1-\alpha)}[M_{\lambda}e_{i}]_{d}$ (or
$\sigma^{-j(1-\alpha)}[M^{-1}_{\lambda}e_{i}]_{d}$) for
$i\in\\{1,\ldots,d-1\\}$. In particular, the entries of
$\widetilde{M}_{\lambda}$ and $\widetilde{M}^{-1}_{\lambda}$ are uniformly
bounded in modulus. This implies $\|\widetilde{M}_{\lambda}\|_{2\rightarrow
2}\lesssim 1$ and $\|\widetilde{M}^{-1}_{\lambda}\|_{2\rightarrow 2}\lesssim
1$. Altogether, we obtain

$\displaystyle|\widetilde{M}_{\lambda}\xi|\asymp|\xi|\text{ uniformly for
$\xi\in\mathbb{R}^{d}$ and }\lambda\in\Lambda^{s,d}.$ (17)

Due to the structure of the last column of $\widetilde{M}_{\lambda}$ we
further have for $\xi=(\xi_{1},\ldots,\xi_{d})^{T}\in\mathbb{R}^{d}$

$\displaystyle|\widetilde{M}_{\lambda}\xi|_{[d-1]}=|\widetilde{M}_{\lambda}(\xi_{1},\ldots,\xi_{d-1},0)^{T}|_{[d-1]}\leq\|\widetilde{M}_{\lambda}\|_{2\rightarrow
2}|(\xi_{1},\ldots,\xi_{d-1},0)^{T}|=\|\widetilde{M}_{\lambda}\|_{2\rightarrow
2}|\xi|_{[d-1]}.$

For the inverse $\widetilde{M}^{-1}$ it holds analogously
$|\widetilde{M}^{-1}_{\lambda}\xi|_{[d-1]}\leq\|\widetilde{M}^{-1}_{\lambda}\|_{2\rightarrow
2}\left|\xi\right|_{[d-1]}$. We conclude

$\displaystyle|\widetilde{M}_{\lambda}\xi|_{[d-1]}\asymp\left|\xi\right|_{[d-1]}\text{
uniformly for $\xi\in\mathbb{R}^{d}$ and }\lambda\in\Lambda^{s,d}.$ (18)

Finally, the following estimate holds uniformly for
$\xi=(\xi_{1},\ldots,\xi_{d})^{T}\in\mathbb{R}^{d}$ and
$\lambda\in\Lambda^{s,d}$,

$\displaystyle|[\widetilde{M}_{\lambda}\xi]_{d}|\leq|[M_{\lambda}]^{d}_{d}||\xi_{d}|+\sum_{i=1}^{d-1}\sigma^{-j(1-\alpha)}|[M_{\lambda}]^{i}_{d}||\xi_{i}|\lesssim\sigma^{-(1-\alpha)j}\left|\xi\right|_{[d-1]}+\left|\xi_{d}\right|.$
(19)

Finally, we can prove (7) for every $\rho\in\mathbb{N}_{0}^{d}$ with
$|\rho|_{1}\leq L$,

$\displaystyle\left|\partial^{\rho}\hat{g}_{\lambda}(\xi)\right|\lesssim\sup_{|\beta|_{1}\leq
L}\left|\big{(}\partial^{\beta}\hat{\gamma}_{\lambda}\big{)}(\widetilde{M}_{\lambda}\xi)\right|$
$\displaystyle\lesssim\frac{\min\\{1,\sigma^{-j}+\sigma^{-(1-\alpha)j}|\widetilde{M}_{\lambda}\xi|_{[d-1]}+|[\widetilde{M}_{\lambda}\xi]_{d}|\\}^{M}}{\langle|\widetilde{M}_{\lambda}\xi|\rangle^{N_{1}}\langle|\widetilde{M}_{\lambda}\xi|_{[d-1]}\rangle^{N_{2}}}$
$\displaystyle\lesssim\frac{\min\\{1,\sigma^{-j}+\sigma^{-(1-\alpha)j}\left|\xi\right|_{[d-1]}+\left|[\xi]_{d}\right|\\}^{M}}{\langle\left|\xi\right|\rangle^{N_{1}}\langle\left|\xi\right|_{[d-1]}\rangle^{N_{2}}}.$

The first estimate holds true, since
$\hat{g}_{\lambda}(\xi)=\hat{\gamma}_{\lambda}(\widetilde{M}_{\lambda}\xi)$
and the entries of $\widetilde{M}_{\lambda}$ are uniformly bounded in
$\lambda$. The second estimate is due to (13). For the last estimate we used
(17), (18), and (19). The observation $s_{\lambda}=\sigma^{j}$ finishes the
proof. ∎

###  5.2 Consistency of the Shearlet Parametrizations

The properties of $\alpha$-molecules depend essentially on their
parametrizations. In view of Theorem 3.7 the consistency is of particular
interest when investigating approximation properties. In this paragraph we
shall prove, in Proposition 5.6, that shearlet parametrizations are consistent
with each other. This allows to establish approximation rates for various
shearlet-like constructions simultaneously, as long as they fall under the
umbrella of the shearlet-molecule concept.

######  Lemma 5.4.

Consider the _gnomonic projection_
$\phi:\mathbb{R}^{d}\backslash\left\\{x\in\mathbb{R}^{d}\ |\
[x]_{d}=0\right\\}\to\mathbb{R}^{d},x\mapsto\frac{1}{[x]_{d}}x$, and let
$1\geq c>0$ be fixed. For
$v,w\in\mathbb{S}^{d-1}\cap\left\\{x\in\mathbb{R}^{d}:[x]_{d}\geq c\right\\}$
we then have $|\phi(v)-\phi(w)|\asymp|v-w|$ and
$\left|v-w\right|_{[d-1]}\asymp|v-w|$.

###### Proof.

First note that $\left|v-w\right|_{[d-1]}=|\pi(v)-\pi(w)|$, where $\pi$ is the
orthogonal projection of $\mathbb{R}^{d}$ onto the
$(e_{1},\ldots,e_{d-1})$-plane. On the set
$\mathbb{S}^{d-1}\cap\left\\{x\in\mathbb{R}^{d}:[x]_{d}\geq c\right\\}$, the
mappings $\phi$ and $\pi$ are diffeomorphisms with bounded derivatives in both
directions. This implies the statement. ∎

In order to apply the previous lemma it is useful to record the following
observation.

######  Lemma 5.5.

Let $1\geq c>0$ be fixed and let
$w=(w_{1},\ldots,w_{d})^{T}\in\mathbb{S}^{d-1}$ be a vector such that
$w_{d}<c$. Then there exists a point
$\tilde{w}=(\tilde{w}_{1},\ldots,\tilde{w}_{d})^{T}\in\mathbb{S}^{d-1}$ with
$\tilde{w}_{d}\geq c$ such that

$\displaystyle|\tilde{w}-v|\leq|w-v|\qquad\text{ for every }\quad
v\in\mathbb{S}^{d-1}\cap\left\\{x\in\mathbb{R}^{d}:[x]_{d}\geq c\right\\}.$

###### Proof.

If $w_{d}\leq-c$ simply take $\tilde{w}$ to be the reflection of $w$ at the
$(e_{1},\ldots,e_{d-1})$-plane. Then we have $\tilde{w}_{d}\geq c>0$ and we
can conclude for every $v=(v_{1},\ldots,v_{d})^{T}\in\mathbb{S}^{d-1}$ with
$v_{d}\geq c>0$

$|v-w|^{2}=\left|v-w\right|_{[d-1]}^{2}+|v_{d}-w_{d}|^{2}=\left|v-\tilde{w}\right|_{[d-1]}^{2}+|v_{d}+\tilde{w}_{d}|^{2}\geq\left|v-\tilde{w}\right|_{[d-1]}^{2}+|v_{d}-\tilde{w}_{d}|^{2}=|v-\tilde{w}|^{2}.$

In the other case $|w_{d}|<c$ we argue as follows. Applying a rotation about
the $e_{d}$-axis, we may assume that $w$ is of the form
$[\sqrt{1-w_{d}^{2}},0,\ldots 0,w_{d}]^{T}$. The vector
$\tilde{w}=[\sqrt{1-c^{2}},0,\ldots,0,c]^{T}$ then has the desired properties.
To verify this it suffices to show $\langle\tilde{w},v\rangle\geq\langle
w,v\rangle$, because then

$\displaystyle|\tilde{w}-v|^{2}=|\tilde{w}|^{2}+|v|^{2}-2\langle\tilde{w},v\rangle=2-2\langle\tilde{w},v\rangle\leq|w|^{2}+|v|^{2}-2\langle
w,v\rangle=|w-v|^{2}.$

In order to show
$0\leq\langle\tilde{w}-w,v\rangle=v_{1}(\sqrt{1-c^{2}}-\sqrt{1-w_{d}^{2}})+v_{d}(c-w_{d})$,
we first observe that $\sqrt{1-c^{2}}<\sqrt{1-w_{d}^{2}}$ since $|w_{d}|<c$.
Moreover, every
$v\in\mathbb{S}^{d-1}\cap\left\\{x\in\mathbb{R}^{d}:[x]_{d}\geq c\right\\}$
satisfies $|v_{1}|\leq\sqrt{1-v_{d}^{2}}$. It follows

$\displaystyle
v_{1}\Big{(}\sqrt{1-c^{2}}-\sqrt{1-w_{d}^{2}}\Big{)}+v_{d}(c-w_{d})\geq\sqrt{1-v_{d}^{2}}\Big{(}\sqrt{1-c^{2}}-\sqrt{1-w_{d}^{2}}\Big{)}+v_{d}(c-w_{d}).$

Hence, it just remains to prove the inequality
$\sqrt{1-v_{d}^{2}}\big{(}\sqrt{1-c^{2}}-\sqrt{1-w_{d}^{2}}\big{)}+v_{d}(c-w_{d})\geq
0$ under the condition $0\leq|w_{d}|<c\leq v_{d}\leq 1$. The associated angles
$\theta_{w},\theta_{c},\theta_{v}\in[0,\pi]$ defined by
$\cos\theta_{w}=w_{d}$, $\cos\theta_{c}=c$, and $\cos\theta_{v}=v_{d}$,
satisfy $\pi\geq\theta_{w}\geq\theta_{c}\geq\theta_{v}\geq 0$, and the
inequality reads as

$\cos(\theta_{c}-\theta_{v})=\langle(\sin\theta_{v},\cos\theta_{v}),(\sin\theta_{c},\cos\theta_{c})\rangle\geq\langle(\sin\theta_{v},\cos\theta_{v}),(\sin\theta_{w},\cos\theta_{w})\rangle=\cos(\theta_{w}-\theta_{v}).$

This however is obviously true since
$0\leq\theta_{c}-\theta_{v}\leq\theta_{w}-\theta_{v}\leq\pi$. ∎

After this preparation we are in the position to prove the consistency.

######  Proposition 5.6.

Let $\alpha\in[0,1]$ and assume that $(\Lambda,\Phi_{\Lambda})$ and
$(\Delta,\Phi_{\Delta})$ are $\alpha$-shearlet parametrizations (possibly with
different parameters). Then $(\Lambda,\Phi_{\Lambda})$ and
$(\Delta,\Phi_{\Delta})$ are $(\alpha,k)$-consistent for every $k>d$.

###### Proof.

As already was noted in Remark 3.6, it suffices to prove that for $N>d$ it
holds

$\displaystyle\sup_{\mu\in\Delta}\sum_{\lambda\in\Lambda}\omega_{\alpha}(\lambda,\mu)^{-N}<\infty.$

For this task it is convenient to decompose the shearlet index set
$\Lambda=\Lambda_{0}\cup\cdots\cup\Lambda_{d}$ into the sets
$\Lambda_{\varepsilon}$ associated with the respective pyramidal regions
$\mathcal{P}_{\varepsilon}$ for $\varepsilon\in\\{1,\ldots,d\\}$ and the low-
frequency box $\mathcal{R}$ for $\varepsilon=0$. The sum then splits
accordingly into $d+1$ parts, which we handle separately below.

##### $\Lambda_{0}$:

Let $\mu\in\Delta$ and $\lambda=(0,0,{\bf 0},k)\in\Lambda_{0}$ with
$k\in\mathbb{Z}^{d}$. The shearlet parametrization (15) yields
$s_{\lambda}=1$, $e_{\lambda}=e_{d}$, and $x_{\lambda}=\mathcal{T}k$.
Furthermore, $s_{\mu}\geq 1$ for all $\mu\in\Lambda$. Hence we have

$\omega_{\alpha}(\lambda,\mu)=s_{\mu}(1+\left|\mathcal{T}k-x_{\mu}\right|^{2}+\left|\left\\{d_{\mathbb{S}}(e_{d},e_{\mu})\right\\}\right|^{2}+|\langle
e_{d},\mathcal{T}k-x_{\mu}\rangle|)\geq
s_{\mu}(1+\left|\mathcal{T}k-x_{\mu}\right|^{2}).$

We conclude

$\displaystyle\sum_{\lambda\in\Lambda_{0}}\omega_{\alpha}(\lambda,\mu)^{-N}\leq\sum_{k\in\mathbb{Z}^{d}}s_{\mu}^{-N}(1+\left|\mathcal{T}k-x_{\mu}\right|^{2})^{-N}\lesssim\sum_{k\in\mathbb{Z}^{d}}(1+\left|k\right|^{2})^{-N},$

where for $N>d/2$ the sum on the right converges.

##### $\Lambda_{\varepsilon}$, $\varepsilon\in\\{1,\ldots,d\\}$:

We only deal with the special case $\varepsilon=d$, since the other cases can
be transformed to this case via rotations. Let $\mu\in\Delta$ and write
$s_{\mu}=\sigma^{j^{\prime}}$ with $j^{\prime}\in\mathbb{R}$. In view of
$s_{\lambda}=\sigma^{j}$ for $\lambda=(d,j,\ell,k)\in\Lambda_{d}$ we then have

$\displaystyle\sum_{\lambda\in\Lambda_{d}}\omega_{\alpha}(\lambda,\mu)^{-N}=\sum_{j\in\mathbb{N}_{0}}\sigma^{-N\left|j-j^{\prime}\right|}\sum_{\stackrel{{\scriptstyle\lambda\in\Lambda_{d}}}{{s_{\lambda}=\sigma^{j}}}}\left(1+d_{\alpha}(\lambda,\mu)\right)^{-N}.$

If we can prove that

$\displaystyle\mathcal{S}:=\sum_{\stackrel{{\scriptstyle\lambda\in\Lambda_{d}}}{{s_{\lambda}=\sigma^{j}}}}\left(1+d_{\alpha}({\lambda},\mu)\right)^{-N}\lesssim\sigma^{d|j-j^{\prime}|},$
(20)

independently of $j\in\mathbb{N}_{0}$ and $\mu\in\Delta$, we are done, since
$\sigma>1$, $s_{\mu}=\sigma^{j^{\prime}}$,
$\max\\{s_{\lambda}/s_{\mu},s_{\mu}/s_{\lambda}\\}=\sigma^{|j-j^{\prime}|}$
and thus if $N>d$

$\sum_{\lambda\in\Lambda_{d}}\omega_{\alpha}(\lambda,\mu)^{-N}\lesssim\sum_{j\in\mathbb{N}_{0}}\sigma^{(d-N)\left|j-j^{\prime}\right|}\leq
2\sum_{j\in\mathbb{N}_{0}}\sigma^{(d-N)j}=\frac{2}{1-\sigma^{d-N}}<\infty.$

Putting in the definition of $d_{\alpha}(\lambda,\mu)$ and abbreviating
$j_{0}:=\min\\{j,j^{\prime}\\}$, the sum $\mathcal{S}$ becomes

$\displaystyle\mathcal{S}=\sum_{\stackrel{{\scriptstyle\lambda\in\Lambda_{d}}}{{s_{\lambda}=\sigma^{j}}}}\left(1+\sigma^{2\alpha
j_{0}}\left|x_{\lambda}-x_{\mu}\right|^{2}+\sigma^{2(1-\alpha)j_{0}}\left|\left\\{d_{\mathbb{S}}(e_{\lambda},e_{\mu})\right\\}\right|^{2}+\sigma^{j_{0}}\left|\langle
e_{\lambda},x_{\lambda}-x_{\mu}\rangle\right|\right)^{-N}.$ (21)

In order to prove the estimate (20) for $\mathcal{S}$, we first study the
different terms of the summand independently. Let
$\lambda=(d,j,\ell,k)\in\Lambda_{d}$ and recall the matrix $M_{\lambda}$ from
(16). It holds

$M^{T}_{\lambda}=R_{\theta_{\lambda}}R_{\varphi_{\lambda}}S^{-1}_{\ell\eta_{j}},$

and – according to the discussion of $M_{\lambda}$ in the proof of Theorem 5.3
– its last row is given by $(0,\ldots,0,n_{\lambda})$ with
$n_{\lambda}=(1+\eta_{j}^{2}\left|\ell\right|_{2}^{2})^{-\frac{1}{2}}$. Since
$\eta_{j}\asymp\sigma^{-j(1-\alpha)}$ and
$|\ell|_{2}\lesssim\mathbb{L}_{j}\lesssim\sigma^{j(1-\alpha)}$ this implies
$n_{\lambda}\asymp 1$ uniformly for all $\lambda\in\Lambda_{d}$.

As a direct consequence
$[M^{T}_{\lambda}x]_{d}=n_{\lambda}[x]_{d}\asymp[x]_{d}$ uniformly for
$\lambda\in\Lambda_{d}$ and $x\in\mathbb{R}^{d}$. In addition, we have
$|M^{T}_{\lambda}x|\asymp|x|$ uniformly for $\lambda\in\Lambda_{d}$ and
$x\in\mathbb{R}^{d}$ since $\|M^{T}_{\lambda}\|_{2\rightarrow
2}=\|M_{\lambda}\|_{2\rightarrow 2}\lesssim 1$ and also
$\|M^{-T}_{\lambda}\|_{2\rightarrow 2}=\|M^{-1}_{\lambda}\|_{2\rightarrow
2}\lesssim 1$.

These observations allow the following estimate,

$\displaystyle\left|x_{\lambda}-x_{\mu}\right|$
$\displaystyle=\left|S^{-1}_{\ell\eta_{j}}A^{-j}_{\alpha,\sigma}\mathcal{T}k-x_{\mu}\right|=\left|R_{\theta_{\lambda}}R_{\varphi_{\lambda}}S^{-1}_{\ell\eta_{j}}A^{-j}_{\alpha,\sigma}\mathcal{T}k-R_{\theta_{\lambda}}R_{\varphi_{\lambda}}x_{\mu}\right|$
$\displaystyle=\left|M^{T}_{\lambda}\big{(}\mathcal{T}A^{-j}_{\alpha,\sigma}k-M^{-T}_{\lambda}R_{\theta_{\lambda}}R_{\varphi_{\lambda}}x_{\mu}\big{)}\right|\asymp\left|A^{-j}_{\alpha,\sigma}k-\mathcal{T}^{-1}M^{-T}_{\lambda}R_{\theta_{\lambda}}R_{\varphi_{\lambda}}x_{\mu}\right|$
$\displaystyle\gtrsim\left|A^{-j}_{\alpha,\sigma}k-\mathcal{T}^{-1}S_{\ell\eta_{j}}x_{\mu}\right|_{[d-1]}=\left|\sigma^{-j\alpha}k-\mathcal{T}^{-1}S_{\ell\eta_{j}}x_{\mu}\right|_{[d-1]}.$
(22)

In view of
$e_{\lambda}=R^{T}_{\varphi_{\lambda}}R^{T}_{\theta_{\lambda}}e_{d}$ we also
have the estimate

$\displaystyle\left|\langle e_{\lambda},x_{\lambda}-x_{\mu}\rangle\right|$
$\displaystyle=\left|\langle
e_{\lambda},S^{-1}_{\ell\eta_{j}}A^{-j}_{\alpha,\sigma}\mathcal{T}k-x_{\mu}\rangle\right|=\left|\langle
e_{d},R_{\theta_{\lambda}}R_{\varphi_{\lambda}}S^{-1}_{\ell\eta_{j}}A^{-j}_{\alpha,\sigma}\mathcal{T}k-R_{\theta_{\lambda}}R_{\varphi_{\lambda}}x_{\mu}\rangle\right|$
$\displaystyle=\left|\langle
e_{d},M^{T}_{\lambda}\big{(}\mathcal{T}A^{-j}_{\alpha,\sigma}k-M^{-T}_{\lambda}R_{\theta_{\lambda}}R_{\varphi_{\lambda}}x_{\mu}\big{)}\rangle\right|\asymp\left|\langle
e_{d},A^{-j}_{\alpha,\sigma}k-\mathcal{T}^{-1}S_{\ell\eta_{j}}x_{\mu}\rangle\right|$
$\displaystyle=\left|\langle
e_{d},\sigma^{-j}k-\mathcal{T}^{-1}S_{\ell\eta_{j}}x_{\mu}\rangle\right|.$
(23)

According to the shearlet parametrization (15) we have
$e_{\lambda}=n_{\lambda}(\ell\eta_{j},1)^{T}$, where $n_{\lambda}\asymp 1$ as
shown above. Hence, there is a constant $c>0$ such that $n_{\lambda}\geq c$
for all $\lambda\in\Lambda_{d}$. It follows $[e_{\lambda}]_{d}\geq c>0$ for
all $\lambda\in\Lambda_{d}$. Without loss of generality we can further assume
that $[e_{\mu}]_{d}\geq 0$ since
$|\\{d_{\mathbb{S}}(e_{\lambda},-e_{\mu})\\}|=|\\{d_{\mathbb{S}}(e_{\lambda},e_{\mu})\\}|$.

In this situation Lemma 6.3 applies and tells us that
$\left|\left\\{d_{\mathbb{S}}(e_{\lambda},e_{\mu})\right\\}\right|\asymp|e_{\lambda}-e_{\mu}|$.
Moreover, possibly after changing $e_{\mu}$ to $\tilde{e}_{\mu}$ as in Lemma
5.5 to enforce $[\tilde{e}_{\mu}]_{d}\geq c$, we have
$|e_{\lambda}-e_{\mu}|\geq|e_{\lambda}-\tilde{e}_{\mu}|$ for all
$\lambda\in\Lambda_{d}$.

Let $\phi$ be the gnomonic projection from Lemma 5.4. Then
$\phi(e_{\lambda})=(\ell\eta_{j},1)^{T}\in\mathbb{R}^{d}$ and Lemma 5.4
together with the observation
$\left|\phi(v)-\phi(w)\right|_{[d-1]}=\left|\phi(v)-\phi(w)\right|$ implies
the estimate,

$|e_{\lambda}-\tilde{e}_{\mu}|\asymp|(\ell\eta_{j},1)^{T}-\phi(\tilde{e}_{\mu})|=|(\ell\eta_{j},1)^{T}-\phi(\tilde{e}_{\mu})|_{[d-1]}.$

Subsequently, let $\nu_{\mu}\in\mathbb{R}^{d-1}$ be defined by
$\phi(\tilde{e}_{\mu})=(\nu_{\mu},1)^{T}$. Altogether we arrive at

$\displaystyle\left|\left\\{d_{\mathbb{S}}(e_{\lambda},e_{\mu})\right\\}\right|\gtrsim|(\ell\eta_{j},1)^{T}-\phi(\tilde{e}_{\mu})|_{[d-1]}=|\ell\eta_{j}-\nu_{\mu}|.$
(24)

We now use (5.2), (5.2) and (24) to estimate the sum $\mathcal{S}$ in (21).
Introducing the quantities
$q_{1}(\ell):=\sigma^{j\alpha}\mathcal{T}^{-1}S_{\ell\eta_{j}}x_{\mu}$,
$q_{2}(\ell):=\sigma^{j}\mathcal{T}^{-1}S_{\ell\eta_{j}}x_{\mu}$, and
$q_{3}:=\eta^{-1}_{j}\nu_{\mu}$, and taking into account
$\eta_{j}\asymp\sigma^{-(1-\alpha)j}$ we obtain

$\displaystyle\mathcal{S}\lesssim\sum_{k\in\mathbb{Z}^{d}}\sum_{\ell\in\mathscr{L}_{d,j}}\left(1+\sigma^{2\alpha(j_{0}-j)}\left|k-q_{1}(\ell)\right|_{[d-1]}^{2}+\sigma^{(j_{0}-j)}\left|\langle
e_{d},k-q_{2}(\ell)\rangle\right|+\sigma^{2(1-\alpha)(j_{0}-j)}|\ell-
q_{3}|^{2}\right)^{-N}.$

Next, we distinguish the cases $j>j^{\prime}$ and $j\leq j^{\prime}$. For
$j\leq j^{\prime}$ we have $j_{0}=j$ and we obtain

$\displaystyle\mathcal{S}$
$\displaystyle\lesssim\sum_{k\in\mathbb{Z}^{d}}\sum_{\ell\in\mathbb{Z}^{d-1}}\left(1+\left|k-q_{1}(\ell)\right|_{[d-1]}^{2}+\left|\langle
e_{d},k-q_{2}(\ell)\rangle\right|+|\ell-q_{3}|^{2}\right)^{-N}$
$\displaystyle\lesssim\sum_{k\in\mathbb{Z}^{d}}\sum_{\ell\in\mathbb{Z}^{d-1}}\left(1+\left|k\right|_{[d-1]}^{2}+\left|\langle
e_{d},k\rangle\right|+|\ell|_{[d-1]}^{2}\right)^{-N}<\infty.$

In case $j>j^{\prime}$ it holds $j_{0}=j^{\prime}$ and $p:=j^{\prime}-j\leq
0$. The term $\sigma^{pd}\mathcal{S}$ is – up to a multiplicative constant –
bounded by

$\displaystyle\sum_{\ell\in\mathbb{Z}^{d-1}}\sigma^{p(1-\alpha)(d-1)}\sum_{k\in\mathbb{Z}^{d}}\sigma^{p\alpha(d-1)}\sigma^{p}\big{(}1+\sigma^{2\alpha
p}\left|k-q_{1}(\ell)\right|_{[d-1]}^{2}+\sigma^{p}\left|\langle
e_{d},k-q_{2}(\ell)\rangle\right|+\sigma^{2(1-\alpha)p}|\ell-
q_{3}|^{2}\big{)}^{-N}.$

The last sum can be interpreted as a Riemann sum, which is bounded – up to a
multiplicative constant independent of $j$ and $j^{\prime}$ as long as
$j>j^{\prime}$ – by the corresponding integral

$\displaystyle\int_{y\in\mathbb{R}^{d-1}}\int_{x\in\mathbb{R}^{d}}\Big{(}1+\left|x-\sigma^{\alpha
p}q_{1}(y)\right|_{[d-1]}^{2}+\left|\langle
e_{d},x-\sigma^{p}q_{2}(y)\rangle\right|+|y-\sigma^{(1-\alpha)p}q_{3}|^{2}\Big{)}^{-N}\,dx\,dy.$

All in all we end up with
$\mathcal{S}\lesssim\sigma^{d(j-j^{\prime})}\int_{y\in\mathbb{R}^{d-1}}\int_{x\in\mathbb{R}^{d}}\Big{(}1+\left|x\right|_{[d-1]}^{2}+\left|\langle
e_{d},x\rangle\right|+|y|^{2}\Big{)}^{-N}\,dx\,dy.$ To see that the integral
converges for $N>d$, we carry out the integration over $x_{d}$, which yields
up to a fixed constant

$\int_{y\in\mathbb{R}^{d-1}}\int_{\tilde{x}\in\mathbb{R}^{d-1}}(1+\left|\tilde{x}\right|_{[d-1]}^{2}+|y|^{2})^{-(N-1)}\,d\tilde{x}\,dy=\int_{z\in\mathbb{R}^{2(d-1)}}(1+|z|^{2})^{-(N-1)}.$

The integral on the right converges precisely for $N>d$. This observation
concludes the proof. ∎

###  5.3 Pyramid-adapted Shearlet Systems in $3$D

In the sequel we focus on some concrete shearlet systems in $3$ dimensions,
which are already on the market and for which we verify that they are
instances of $\alpha$-shearlet molecules for $\alpha=\frac{1}{2}$ and thus by
Theorem 5.3 also systems of 3-dimensional parabolic molecules.

Let us first recall the classic definition [39] of a shearlet system in
$L^{2}(\mathbb{R}^{3})$. A system of 3D-shearlets is defined as a collection
of functions in $L^{2}(\mathbb{R}^{3})$ of the form

$\displaystyle\Big{\\{}\psi_{j,\ell,k}=2^{j}\psi(S_{\ell}A_{\frac{1}{2},2}^{j}\cdot-k)\leavevmode\nobreak\
:\leavevmode\nobreak\
j\in\mathbb{Z},\ell\in\mathbb{Z}^{2},k\in\mathbb{Z}^{3}\Big{\\}},$ (25)

where $\psi\in L^{2}(\mathbb{R}^{3})$ is a suitable generating function. The
classical choice for the generator is a function $\psi$ defined on the
frequency domain by

$\displaystyle\hat{\psi}(\xi)=w(\xi_{3})\textstyle{v(\frac{\xi_{1}}{\xi_{3}})v(\frac{\xi_{2}}{\xi_{3}})},\quad\xi=(\xi_{1},\xi_{2},\xi_{3})^{T}\in\mathbb{R}^{3},$
(26)

where $v\in C^{\infty}_{c}(\mathbb{R})$ is a bump function and $w\in
C^{\infty}_{c}(\mathbb{R})$ the Fourier transform of a suitable univariate
discrete wavelet. It is possible to choose $v$ and $w$ so that (25) becomes a
Parseval frame for $L^{2}(\mathbb{R}^{3})$.

Unfortunately, the shearlet system (25) has a directional bias due to the
fact, that for large shearings the frequency support of the elements becomes
more and more elongated along the $(e_{1},e_{2})$-plane. This directional bias
affects negatively the approximation properties of (25) and makes this system
impractical in most applications.

To avoid this problem, the Fourier domain is usually partitioned into three
pyramidal regions

$\displaystyle\mathcal{P}_{1}$
$\displaystyle=\Big{\\{}(\xi_{1},\xi_{2},\xi_{3})\in\mathbb{R}^{3}\leavevmode\nobreak\
:\leavevmode\nobreak\ \textstyle{|\frac{\xi_{2}}{\xi_{1}}|\leq
1,|\frac{\xi_{3}}{\xi_{1}}|\leq 1}\Big{\\}},$ $\displaystyle\mathcal{P}_{2}$
$\displaystyle=\Big{\\{}(\xi_{1},\xi_{2},\xi_{3})\in\mathbb{R}^{3}\leavevmode\nobreak\
:\leavevmode\nobreak\ \textstyle{|\frac{\xi_{1}}{\xi_{2}}|\leq
1,|\frac{\xi_{3}}{\xi_{2}}|\leq 1}\Big{\\}},$ $\displaystyle\mathcal{P}_{3}$
$\displaystyle=\Big{\\{}(\xi_{1},\xi_{2},\xi_{3})\in\mathbb{R}^{3}\leavevmode\nobreak\
:\leavevmode\nobreak\ \textstyle{|\frac{\xi_{1}}{\xi_{3}}|\leq
1,|\frac{\xi_{2}}{\xi_{3}}|\leq 1}\Big{\\}},$

and for each pyramid a separate shearlet system is used. Then, since each
system only has to cover one pyramid, the shear parameters can be restricted
avoiding large shears. To take care of low frequencies, it is common to use
distinguished coarse-scale elements with frequencies in a centered box. Here
this will be the cube

$\mathcal{R}=\Big{\\{}\xi\in\mathbb{R}^{3}\leavevmode\nobreak\
:\leavevmode\nobreak\ |\xi|_{\infty}\leq\textstyle{\frac{1}{8}}\Big{\\}}.$

This cube together with the truncated pyramids
$\tilde{\mathcal{P}}_{1}:=\mathcal{P}_{1}\backslash\mathcal{R}$,
$\tilde{\mathcal{P}}_{2}:=\mathcal{P}_{2}\backslash\mathcal{R}$, and
$\tilde{\mathcal{P}}_{3}:=\mathcal{P}_{3}\backslash\mathcal{R}$ partitions the
Fourier domain into 4 regions.

With each of these regions, different operators are associated. The coarse-
scale functions are only translated, in the other regions we also scale and
shear. The scaling and shearing operators associated with the respective
regions $\varepsilon\in\\{1,2,3\\}$ are given by
$A^{(\varepsilon)}_{\frac{1}{2},s}=Z^{\varepsilon}A_{\frac{1}{2},s}Z^{-\varepsilon}$
and $S^{(\varepsilon)}_{h}=Z^{\varepsilon}S_{h}Z^{-\varepsilon}$, and take the
concrete form

$\displaystyle A^{(1)}_{\frac{1}{2},s}=\begin{pmatrix}s&0&0\\\
0&s^{\frac{1}{2}}&0\\\ 0&0&s^{\frac{1}{2}}\end{pmatrix},\quad
A^{(2)}_{\frac{1}{2},s}=\begin{pmatrix}s^{\frac{1}{2}}&0&0\\\ 0&s&0\\\
0&0&s^{\frac{1}{2}}\end{pmatrix},\quad
A^{(3)}_{\frac{1}{2},s}=A_{\frac{1}{2},s}=\begin{pmatrix}s^{\frac{1}{2}}&0&0\\\
0&s^{\frac{1}{2}}&0\\\ 0&0&s\end{pmatrix},$

for $s>0$, and for $h\in\mathbb{R}^{2}$

$\displaystyle S^{(1)}_{h}=\begin{pmatrix}1&h_{1}&h_{2}\\\ 0&1&0\\\
0&0&1\end{pmatrix},\quad S^{(2)}_{h}=\begin{pmatrix}1&0&0\\\ h_{2}&1&h_{1}\\\
0&0&1\end{pmatrix},\quad S^{(3)}_{h}=S_{h}=\begin{pmatrix}1&0&0\\\ 0&1&0\\\
h_{1}&h_{2}&1\end{pmatrix}.$

Now we are ready to define a modified shearlet system, which is adapted to our
partition of the Fourier domain and therefore called _cone-adapted_. These
systems do not exhibit the directional bias as (25). In the 3D cone-adapted
setting they are called _pyramid-adapted 3D shearlet systems_.

######  Definition 5.7 ([41, 42]).

For fixed $\tau_{1},\tau_{2}>0$ let $\mathcal{T}={\text{\rm
diag}}(\tau_{1},\tau_{2},\tau_{2})\in\mathbb{R}^{3\times 3}$. The (affine)
_pyramid-adapted 3D shearlet system_ generated by the functions $\phi\in
L^{2}(\mathbb{R}^{3})$ and $\psi^{\varepsilon}\in L^{2}(\mathbb{R}^{3})$,
$\varepsilon\in\\{1,2,3\\}$, is defined as the union

$\displaystyle
SH(\phi,\psi^{1},\psi^{2},\psi^{3};\tau_{1},\tau_{2}):=\Phi(\phi;\tau_{1})\cup\Psi_{1}(\psi^{1};\tau_{1},\tau_{2})\cup\Psi_{2}(\psi^{2};\tau_{1},\tau_{2})\cup\Psi_{3}(\psi^{3};\tau_{1},\tau_{2})$
(27)

of the coarse-scale functions
$\Phi(\phi;\tau_{1}):=\\{\phi_{k}=\phi(\cdot-\tau_{1}k):k\in\mathbb{Z}^{3}\\}$
and the functions

$\displaystyle\Psi_{\varepsilon}(\psi^{\varepsilon};\tau_{1},\tau_{2}):=\Big{\\{}\psi^{\varepsilon}_{j,\ell,k}=2^{j}\psi^{\varepsilon}(Z^{\varepsilon}S_{\ell}A_{\frac{1}{2},2}^{j}Z^{-\varepsilon}\cdot-Z^{\varepsilon}\mathcal{T}Z^{-\varepsilon}k):\leavevmode\nobreak\
j\in\mathbb{N}_{0},\ell\in\mathbb{Z}^{2},|\ell|_{\infty}\leq\lceil
2^{j/2}\rceil,k\in\mathbb{Z}^{3}\Big{\\}}$

associated with the pyramids $\tilde{\mathcal{P}}_{\varepsilon}$ for
$\varepsilon\in\\{1,2,3\\}$.

These pyramid-adapted affine systems are the prime examples of
$\frac{1}{2}$-shearlet-molecules. In practice, one wants them to be frames,
especially tight frames. However, the construction of tight frames of pyramid-
adapted shearlets is not trivial.

The simplest way to obtain a Parseval frame of pyramid-adapted shearlets
starts with a Parseval shearlet frame of the type (25), which is easier to
construct. It yields a shearlet system associated with the pyramid
$\tilde{\mathcal{P}}_{3}$ by removing all elements, whose frequency support
does not intersect $\tilde{\mathcal{P}}_{3}$. Truncating the remaining
functions in the frequency domain outside of $\tilde{\mathcal{P}}_{3}$, one
obtains a Parseval frame for the space

$L^{2}(\tilde{\mathcal{P}}_{3})^{\vee}:=\\{f\in
L^{2}(\mathbb{R}^{3})\leavevmode\nobreak\ :\leavevmode\nobreak\ \text{supp
}\hat{f}\subset\tilde{\mathcal{P}}_{3}\\}.$

A similar procedure yields Parseval frames associated with the the other parts
of the Fourier domain, namely for
$L^{2}(\tilde{\mathcal{P}}_{\varepsilon})^{\vee}$, $\varepsilon\in\\{1,2\\}$,
and $L^{2}(\mathcal{R})^{\vee}$. The union of these frames then is a Parseval
frame for the whole space $L^{2}(\mathbb{R}^{3})$.

This approach has the drawback that it leads to bad spatial localization of
the shearlets due to their lack of smoothness in the frequency domain, which
is a consequence of the truncation. A different approach was taken by Candès,
Demanet, and Ying in [49]. They gave up on the affine structure of the system
and found a shearlet-like construction of a Parseval frame. Guo and Labate
modified this approach [33, 34] and found another shearlet-type construction,
which is even close to affine.

####  5.3.1 Bandlimited Tight Frames of Pyramid-adapted Shearlets

The construction we present here is the one due to Guo and Labate [33, 34]. It
starts with a Meyer scaling function $\phi\in\mathscr{S}(\mathbb{R})$
satisfying $0\leq\hat{\phi}\leq 1$, $\text{supp
}\hat{\phi}\subseteq[-\frac{1}{8},\frac{1}{8}]$, and $\hat{\phi}=1$ on
$[-\frac{1}{16},\frac{1}{16}]$, which is used to define
$\Phi\in\mathscr{S}(\mathbb{R}^{3})$ on the Fourier side by

$\displaystyle\hat{\Phi}(\xi):=\hat{\phi}(\xi_{1})\hat{\phi}(\xi_{2})\hat{\phi}(\xi_{3}),\quad\xi=(\xi_{1},\xi_{2},\xi_{3})^{T}\in\mathbb{R}^{3}.$
(28)

Then the function

$\displaystyle
W(\xi):=\sqrt{\hat{\Phi}^{2}(2^{-2}\xi)-\hat{\Phi}^{2}(\xi)},\quad\xi\in\mathbb{R}^{3},$

is defined, with $\text{supp
}W\subseteq{\textstyle[-{\frac{1}{2}},\frac{1}{2}]^{3}\backslash(-\frac{1}{16},\frac{1}{16})^{3}}$
and $W=1$ on
$[-{\scriptsize{\frac{1}{4}}},\scriptsize{\frac{1}{4}}]^{3}\backslash(-\frac{1}{8},\frac{1}{8})^{3}$,
such that $\hat{\Phi}^{2}(\xi)+\sum_{j\geq 0}W^{2}(2^{-2j}\xi)=1.$for every
$\xi\in\mathbb{R}^{3}$. These functions thus produce a smooth tiling of the
frequency domain into cartesian coronae. To take care of the directional
scaling, a bump-like function $v\in C_{c}^{\infty}(\mathbb{R})$ is used, which
satisfies $\text{supp }v\subseteq[-1,1]$ and

$\displaystyle\left|v(t-1)\right|^{2}+\left|v(t)\right|^{2}+\left|v(t+1)\right|^{2}=1\quad\text{
for }t\in[-1,1],$ $\displaystyle v(0)=1\text{ and }v^{(n)}(0)=0\text{ for
}n\geq 1.$

For an explicit construction of such a function we refer to [31]. Then $V\in
C^{\infty}(\mathbb{R}^{3})$ is defined by

$V(\xi)=\textstyle{v(\frac{\xi_{1}}{\xi_{3}})v(\frac{\xi_{2}}{\xi_{3}})},\quad\xi=(\xi_{1},\xi_{2},\xi_{3})^{T}\in\mathbb{R}^{3},$

with support fully contained in the pyramid $\mathcal{P}_{3}$. After this
preparation the smooth Parseval frame of band-limited 3D-shearlets introduced
by Guo and Labate in [34] can be defined.

The _coarse-scale functions_ , which take care of the low frequencies in
$\mathcal{R}$, are translates of the function $\Phi$ from (28),

$\displaystyle SH_{0}:=\big{\\{}\psi^{0}_{0,{\bf
0},k}(x)=\Phi(\cdot-k)\leavevmode\nobreak\ :\leavevmode\nobreak\
k\in\mathbb{Z}^{3}\big{\\}}.$ (29)

The shearlets, whose frequency support is fully contained in the respective
pyramids, are called _interior shearlets_. They are defined as the collection
of functions

$\displaystyle
SH_{int}:=\big{\\{}\psi^{\varepsilon}_{j,\ell,k}\leavevmode\nobreak\
:\leavevmode\nobreak\ (\varepsilon,j,\ell,k)\in\Lambda_{int}\big{\\}}$

indexed by
$\Lambda_{int}:=\\{(\varepsilon,j,\ell,k)\in\\{1,2,3\\}\times\mathbb{N}_{0}\times\mathbb{Z}^{2}\times\mathbb{Z}^{3}:|\ell|_{\infty}<2^{j}\\}$
and with Fourier transforms

$\displaystyle\hat{\psi}_{j,\ell,k}^{\varepsilon}(\xi)=2^{-2j}W(2^{-2j}\xi)V(S^{-T}_{\ell}A^{-j}_{\frac{1}{2},4}Z^{-\varepsilon}\xi)\exp(-2\pi
i\langle
Z^{\varepsilon}S^{-T}_{\ell}A^{-j}_{\frac{1}{2},4}Z^{-\varepsilon}\xi,k\rangle),\quad\xi\in\mathbb{R}^{3},$
(30)

where $W$ and $V$ are the auxiliary functions from above. Observe that

$V(S^{-T}_{\ell}A^{-j}_{\frac{1}{2},4}\xi)=v(2^{j}\textstyle{\frac{\xi_{1}}{\xi_{3}}}-\ell_{1})v(2^{j}\textstyle{\frac{\xi_{2}}{\xi_{3}}}-\ell_{2}),$

and compare this to (26). Finally, the so-called _boundary shearlets_ ,
obtained by carefully glueing together shearlets from adjacent pyramidal
regions, are added to obtain a smooth well-localized frame. The glueing
process is rather delicate, since it is important to select the right
shearlets matching together. In fact, even in the original construction [34]
there are some inaccuracies. We correct them here, which leads to a slight
modification of the original definition.

We make a distinction between boundary shearlets defined between two pyramidal
regions and those at the corners, where three pyramidal regions meet.
Following [34] we also distinguish between the scales $j\geq 1$ and $j=0$.

Let us begin with the scales $j\geq 1$ and the functions at the boundary where
only two pyramidal regions meet. We define, for $j\geq 1$,
$\varepsilon_{1}\in\\{-1,1\\}$, $\ell_{1}=\varepsilon_{1}2^{j}$,
$|\ell_{2}|<2^{j}$, and $k\in\mathbb{Z}^{3}$,

$\displaystyle\hat{\psi}_{j,\ell,k}^{1}(\xi)$
$\displaystyle=\begin{cases}2^{-2j-3}W(2^{-2j}\xi)v(2^{j}\frac{\xi_{2}}{\xi_{1}}-\ell_{1})v(2^{j}\frac{\xi_{3}}{\xi_{1}}-\ell_{2})\exp(-2\pi
i\langle
2^{-2}ZS^{-T}_{\ell}A_{\frac{1}{2},2^{-2j}}Z^{-1}\xi,k\rangle)&,\xi\in\mathcal{P}_{1};\\\
2^{-2j-3}W(2^{-2j}\xi)v(2^{j}\frac{\xi_{1}}{\xi_{2}}-\ell_{1})v(2^{j}\frac{\xi_{3}}{\xi_{2}}-\varepsilon_{1}\ell_{2})\exp(-2\pi
i\langle
2^{-2}ZS^{-T}_{\ell}A^{-j}_{\frac{1}{2},4}Z^{-1}\xi,k\rangle)&,\xi\in\mathcal{P}_{2};\end{cases}$
$\displaystyle\hat{\psi}_{j,\ell,k}^{2}(\xi)$
$\displaystyle=\begin{cases}2^{-2j-3}W(2^{-2j}\xi)v(2^{j}\frac{\xi_{3}}{\xi_{2}}-\ell_{1})v(2^{j}\frac{\xi_{1}}{\xi_{2}}-\ell_{2})\exp(-2\pi
i\langle
2^{-2}Z^{2}S^{-T}_{\ell}A^{-j}_{\frac{1}{2},4}Z^{-2}\xi,k\rangle)&,\xi\in\mathcal{P}_{2};\\\
2^{-2j-3}W(2^{-2j}\xi)v(2^{j}\frac{\xi_{2}}{\xi_{3}}-\ell_{1})v(2^{j}\frac{\xi_{1}}{\xi_{3}}-\varepsilon_{1}\ell_{2})\exp(-2\pi
i\langle
2^{-2}Z^{2}S^{-T}_{\ell}A^{-j}_{\frac{1}{2},4}Z^{-2}\xi,k\rangle)&,\xi\in\mathcal{P}_{3};\end{cases}$
$\displaystyle\hat{\psi}_{j,\ell,k}^{3}(\xi)$
$\displaystyle=\begin{cases}2^{-2j-3}W(2^{-2j}\xi)v(2^{j}\frac{\xi_{1}}{\xi_{3}}-\ell_{1})v(2^{j}\frac{\xi_{2}}{\xi_{3}}-\ell_{2})\exp(-2\pi
i\langle
2^{-2}S^{-T}_{\ell}A^{-j}_{\frac{1}{2},4}\xi,k\rangle)&,\xi\in\mathcal{P}_{3};\\\
2^{-2j-3}W(2^{-2j}\xi)v(2^{j}\frac{\xi_{3}}{\xi_{1}}-\ell_{1})v(2^{j}\frac{\xi_{2}}{\xi_{1}}-\varepsilon_{1}\ell_{2})\exp(-2\pi
i\langle
2^{-2}S^{-T}_{\ell}A^{-j}_{\frac{1}{2},4}\xi,k\rangle)&,\xi\in\mathcal{P}_{1}.\end{cases}$
(31)

Note that we only give the definition in the regions where the functions have
non-trivial support. Outside they are supposed to be zero.

Next, we come to the corners where three pyramidal regions meet. Here we have
to glue together three shearlet parts, each coming from a different pyramid.
For convenience the corner elements will be associated to the first pyramid
$\mathcal{P}_{1}$. For $j\geq 1$, $\ell_{1}=\varepsilon_{1}2^{j}$,
$\ell_{2}=\varepsilon_{2}2^{j}$ with
$\varepsilon_{1},\varepsilon_{2}\in\\{-1,1\\}$, and $k\in\mathbb{Z}^{3}$, they
are defined as follows:

$\displaystyle\hat{\psi}_{j,\ell,k}^{1}(\xi)$
$\displaystyle=\begin{cases}2^{-2j-3}W(2^{-2j}\xi)v(2^{j}\frac{\xi_{2}}{\xi_{1}}-\ell_{1})v(2^{j}\frac{\xi_{3}}{\xi_{1}}-\ell_{2})\exp(-2\pi
i\langle
2^{-2}ZS^{-T}_{\ell}A^{-j}_{\frac{1}{2},4}Z^{-1}\xi,k\rangle)&,\xi\in\mathcal{P}_{1};\\\
2^{-2j-3}W(2^{-2j}\xi)v(2^{j}\frac{\xi_{1}}{\xi_{2}}-\ell_{1})v(2^{j}\frac{\xi_{3}}{\xi_{2}}-\varepsilon_{1}\ell_{2})\exp(-2\pi
i\langle
2^{-2}ZS^{-T}_{\ell}A^{-j}_{\frac{1}{2},4}Z^{-1}\xi,k\rangle)&,\xi\in\mathcal{P}_{2};\\\
2^{-2j-3}W(2^{-2j}\xi)v(2^{j}\frac{\xi_{2}}{\xi_{3}}-\varepsilon_{2}\ell_{1})v(2^{j}\frac{\xi_{1}}{\xi_{3}}-\ell_{2})\exp(-2\pi
i\langle
2^{-2}ZS^{-T}_{\ell}A^{-j}_{\frac{1}{2},4}Z^{-1}\xi,k\rangle)&,\xi\in\mathcal{P}_{3}.\end{cases}$
(32)

As in the original construction the definition of the boundary shearlets is
slightly different at the lowest scale $j=0$. For $j=0$, $\ell_{1}=\pm 1$,
$\ell_{2}=0$, and $k\in\mathbb{Z}^{3}$, we set

$\displaystyle\hat{\psi}_{j,\ell,k}^{1}(\xi)$
$\displaystyle=\begin{cases}W(\xi)v(\frac{\xi_{2}}{\xi_{1}}-\ell_{1})v(\frac{\xi_{3}}{\xi_{1}})\exp(-2\pi
i\langle\xi,k\rangle)&,\xi\in\mathcal{P}_{1};\\\
W(\xi)v(\frac{\xi_{1}}{\xi_{2}}-\ell_{1})v(\frac{\xi_{3}}{\xi_{2}})\exp(-2\pi
i\langle\xi,k\rangle)&,\xi\in\mathcal{P}_{2};\end{cases}$
$\displaystyle\hat{\psi}_{j,\ell,k}^{2}(\xi)$
$\displaystyle=\begin{cases}W(\xi)v(\frac{\xi_{3}}{\xi_{2}}-\ell_{1})v(\frac{\xi_{1}}{\xi_{2}})\exp(-2\pi
i\langle\xi,k\rangle)&,\xi\in\mathcal{P}_{2};\\\
W(\xi)v(\frac{\xi_{2}}{\xi_{3}}-\ell_{1})v(\frac{\xi_{1}}{\xi_{3}})\exp(-2\pi
i\langle\xi,k\rangle)&,\xi\in\mathcal{P}_{3};\end{cases}$ (33)
$\displaystyle\hat{\psi}_{j,\ell,k}^{3}(\xi)$
$\displaystyle=\begin{cases}W(\xi)v(\frac{\xi_{1}}{\xi_{3}}-\ell_{1})v(\frac{\xi_{2}}{\xi_{3}})\exp(-2\pi
i\langle\xi,k\rangle)&,\xi\in\mathcal{P}_{3};\\\
W(\xi)v(\frac{\xi_{3}}{\xi_{1}}-\ell_{1})v(\frac{\xi_{2}}{\xi_{1}})\exp(-2\pi
i\langle\xi,k\rangle)&,\xi\in\mathcal{P}_{1}.\end{cases}$

Finally, we come to the corner elements at the scale $j=0$. Again they are
associated with the first pyramid. Let
$\varepsilon_{1},\varepsilon_{2}\in\\{-1,1\\}$. Then we define them for $j=0$,
$\ell=(\varepsilon_{1},\varepsilon_{2})$, and $k\in\mathbb{Z}^{3}$ by

$\displaystyle\hat{\psi}_{j,\ell,k}^{1}(\xi)$
$\displaystyle=\begin{cases}W(\xi)v(\frac{\xi_{2}}{\xi_{1}}-\ell_{1})v(\frac{\xi_{3}}{\xi_{1}}-\ell_{2})\exp(-2\pi
i\langle\xi,k\rangle)&,\xi\in\mathcal{P}_{1};\\\
W(\xi)v(\frac{\xi_{1}}{\xi_{2}}-\ell_{1})v(\frac{\xi_{3}}{\xi_{2}}-\varepsilon_{1}\ell_{2})\exp(-2\pi
i\langle\xi,k\rangle)&,\xi\in\mathcal{P}_{2};\\\
W(\xi)v(\frac{\xi_{2}}{\xi_{3}}-\varepsilon_{2}\ell_{1})v(\frac{\xi_{1}}{\xi_{3}}-\ell_{2})\exp(-2\pi
i\langle\xi,k\rangle)&,\xi\in\mathcal{P}_{3}.\end{cases}$ (34)

All boundary shearlets are collected in the family $SH_{bound}$. Together with
the coarse-scale functions $SH_{0}$ and the interior shearlets $SH_{int}$ they
provide a Parseval frame for $L^{2}(\mathbb{R}^{3})$.

######  Theorem 5.8 ([34]).

The system of $3D$-shearlets

$\displaystyle SH:=SH_{0}\cup SH_{int}\cup SH_{bound}$

is a smooth (well-localized) Parseval frame for $L^{2}(\mathbb{R}^{3})$,
consisting of band-limited Schwarz functions.

The corresponding index set
$\Lambda_{SH}\subset\\{0,1,2,3\\}\times\mathbb{N}_{0}\times\mathbb{Z}^{2}\times\mathbb{Z}^{3}$
is given by

$\displaystyle\Lambda_{SH}:=\Big{\\{}(0,0,{\bf
0},k):k\in\mathbb{Z}^{3}\Big{\\}}\cup\Big{\\{}(\varepsilon,j,\ell,k)\leavevmode\nobreak\
:\leavevmode\nobreak\
\varepsilon\in\\{1,2,3\\},\,j\in\mathbb{N}_{0},\,\ell\in\mathscr{L}_{\varepsilon,j}\subseteq\mathbb{Z}^{2},\,k\in\mathbb{Z}^{3}\Big{\\}}$
(35)

with the shear parameters
$\mathscr{L}_{\varepsilon,j}=\\{(\ell_{1},\ell_{2})\in\mathbb{Z}^{2}:|\ell_{1}|\leq
2^{j},|\ell_{2}|<2^{j}\\}$ for $\varepsilon\in\\{2,3\\}$ and
$\mathscr{L}_{1,j}=\\{(\ell_{1},\ell_{2})\in\mathbb{Z}^{2}:|\ell_{1}|\leq
2^{j},|\ell_{2}|<2^{j}\\}\cup\\{(\pm 2^{j},\pm 2^{j})\\}$ at each scale
$j\in\mathbb{N}_{0}$.

The system $SH$ is another instance of a system of $\frac{1}{2}$-shearlet
molecules (at least after an appropriate re-indexing). In particular, it falls
within the framework of $\alpha$-molecules for $\alpha=\frac{1}{2}$.

######  Proposition 5.9.

Appropriately re-indexed, the smooth Parseval frame of band-limited shearlets
$SH$ constitutes a system of $3$-dimensional $\frac{1}{2}$-shearlet molecules
of order $(\infty,\infty,\infty,\infty)$.

###### Proof.

We first re-index the coarse-scale functions (29) as well as the boundary
elements (5.3.1) and (34) at scale $j=0$. For this we utilize the index set
$\Gamma\subset\\{0,1,2,3\\}\times\mathbb{N}_{0}\times\mathbb{Z}^{2}$ given by

$\Gamma:=\big{\\{}(0,0,{\bf
0})\big{\\}}\cup\big{\\{}(\varepsilon,0,\ell):\varepsilon\in\\{1,2,3\\},\ell=(\pm
1,0)\big{\\}}\cup\big{\\{}(1,0,\ell):\ell=(\pm 1,\pm 1)\big{\\}}.$

The functions we want to re-index are then precisely those functions
$\psi^{\varepsilon}_{j,\ell,k}\in SH$ with
$(\varepsilon,j,\ell,k)\in\Delta:=\Gamma\times\mathbb{Z}^{3}$. It holds
$\\#\Gamma=11$, and we enumerate the set $\Gamma$ in lexicographic order from
$0$ to $10$, described by a bijective function
$\mathcal{N}:\Gamma\rightarrow\\{0,\ldots,10\\}$. For
$(\varepsilon,j,\ell,k)\in\Delta$ we then re-index as follows. Writing
$\tilde{k}(\varepsilon,j,\ell,k):=(k_{1},k_{2},11\cdot
k_{3}+\mathcal{N}(\varepsilon,j,\ell))\in\mathbb{Z}^{3}$ the re-indexed
elements are given by

$\widetilde{\psi}^{0}_{0,{\bf
0},\tilde{k}(\varepsilon,j,\ell,k)}:=\psi^{\varepsilon}_{j,{\bf\ell},k}\quad\text{for
}(\varepsilon,j,\ell,k)\in\Delta.$

For $(\varepsilon,j,\ell,k)\in\Lambda_{SH}\backslash\Delta$ the functions
$\tilde{\psi}^{\varepsilon}_{j,{\bf\ell},k}:=\psi^{\varepsilon}_{j,{\bf\ell},k}$
remain the same. The relabelling is thus given by

$\displaystyle
F_{label}:\Lambda_{SH}\rightarrow\widetilde{\Lambda}_{SH},\>(\varepsilon,j,\ell,k)\mapsto\begin{cases}(0,0,{\bf
0},\tilde{k}(\varepsilon,j,\ell,k))\,&,(\varepsilon,j,\ell,k)\in\Delta;\\\
(\varepsilon,j,\ell,k)&,(\varepsilon,j,\ell,k)\notin\Delta.\end{cases}$ (36)

The newly obtained system

$\displaystyle\widetilde{SH}:=\big{\\{}\widetilde{\psi}^{\varepsilon}_{j,\ell,k}\big{\\}}_{(\varepsilon,j,\ell,k)\in\widetilde{\Lambda}_{SH}}$
(37)

is equipped with a shearlet index set
$\tilde{\Lambda}_{SH}\subset\\{0,1,2,3\\}\times\mathbb{N}_{0}\times\mathbb{Z}^{2}\times\mathbb{Z}^{3}$
similar to (35), however with the modified shear parameters
$\mathscr{L}_{1,0}=\mathscr{L}_{2,0}=\mathscr{L}_{3,0}=\\{(0,0)\\}$ at scale
$j=0$.

In the remainder we show that (37) is a system of $\frac{1}{2}$-shearlet
molecules of order $(\infty,\infty,\infty,\infty)$. As parameters we fix
$\sigma=4$ and $\eta_{j}=2^{-j}$ for $j\in\mathbb{N}_{0}$. The translation
parameters $\mathcal{T}={\text{\rm diag}}(\tau_{1},\tau_{2},\tau_{3})$ vary
with the indices and are chosen suitably later. Clearly, we have
$S_{\ell}A^{j}_{\frac{1}{2},4}=A^{j}_{\frac{1}{2},4}S_{\ell\eta_{j}}$. Thus,
defining

$\displaystyle\gamma^{\varepsilon}_{j,\ell,k}(x):=2^{-2j}\tilde{\psi}^{\varepsilon}_{j,\ell,k}\big{(}Z^{\varepsilon}A^{-j}_{\frac{1}{2},4}S^{-1}_{\ell}Z^{-\varepsilon}(x+\mathcal{T}k)\big{)},\quad
x\in\mathbb{R}^{3},$ (38)

for every $(\varepsilon,j,\ell,k)\in\widetilde{\Lambda}_{SH}$ we get the
desired representation (12), i.e.

$\displaystyle\tilde{\psi}_{j,\ell,k}^{\varepsilon}(x)=2^{2j}\gamma_{j,\ell,k}^{\varepsilon}(Z^{\varepsilon}S_{\ell}A^{j}_{\frac{1}{2},4}Z^{-\varepsilon}x-\mathcal{T}k)=2^{2j}\gamma_{j,\ell,k}^{\varepsilon}(Z^{\varepsilon}A^{j}_{\frac{1}{2},4}S_{\ell\eta_{j}}Z^{-\varepsilon}x-\mathcal{T}k),\quad
x\in\mathbb{R}^{3}.$

On the Fourier side the generators (38) take the form

$\displaystyle\hat{\gamma}_{j,\ell,k}^{\varepsilon}(\xi)=2^{2j}\hat{\tilde{\psi}}^{\varepsilon}_{j,\ell,k}\big{(}Z^{\varepsilon}A^{j}_{\frac{1}{2},4}S^{T}_{\ell}Z^{-\varepsilon}\xi\big{)}\exp(2\pi
i\langle\xi,\mathcal{T}k\rangle),\quad\xi\in\mathbb{R}^{3},$ (39)

and it remains to show that these functions satisfy (13). For this task we
distinguish between the coarse-scale elements, the interior shearlets and the
boundary shearlets of (37).

##### Coarse-Scale:

The coarse-scale elements $\\{\tilde{\psi}^{0}_{0,{\bf
0},k}\\}_{k\in\mathbb{Z}^{3}}$ of (37) are precisely those functions
$\psi^{\varepsilon}_{j,{\bf\ell},k}\in SH$ where
$(\varepsilon,j,\ell,k)\in\Delta$. For them (38) simplifies to
$\gamma^{0}_{0,{\bf 0},k}={\tilde{\psi}^{0}_{0,{\bf
0},k}}(\cdot+\mathcal{T}k)$, and we just need to show (13) for
$\hat{\gamma}^{0}_{0,{\bf 0},k}$ with $k\in\mathbb{Z}^{3}$. For this
$\mathcal{T}={\text{\rm diag}}(1,1,\frac{1}{11})$ is the right choice. A
calculation yields for every $(\varepsilon,j,\ell,k)\in\Delta$ and
$\tilde{k}=\tilde{k}(\varepsilon,j,\ell,k)\in\mathbb{Z}^{3}$

$\displaystyle\hat{\gamma}^{0}_{0,{\bf
0},\tilde{k}(\varepsilon,j,\ell,k)}(\xi)=\hat{\psi}^{\varepsilon}_{j,{\bf\ell},k}(\xi)\exp({\textstyle\frac{2\pi
i}{11}}\xi_{3}\cdot\mathcal{N}(\varepsilon,j,\ell)),\quad\xi=(\xi_{1},\xi_{2},\xi_{3})^{T}\in\mathbb{R}^{3}.$

Hence, looking at the definitions (29), (5.3.1), (34), it follows
$\hat{\gamma}^{0}_{0,{\bf 0},k}\in C^{\infty}_{c}(\mathbb{R}^{3})$ with
support in $[-\frac{1}{2},\frac{1}{2}]^{3}$.

##### Interior Shearlets:

Choosing $\mathcal{T}={\text{\rm diag}}(1,1,1)$, Equation (39) together with
(30) yields for $\xi\in\mathbb{R}^{3}$

$\displaystyle\hat{\gamma}^{\varepsilon}_{j,\ell,k}(\xi)=W(Z^{\varepsilon}M_{j,\ell}Z^{-\varepsilon}\xi)V(Z^{-\varepsilon}\xi),$

where the matrix $M_{j,\ell}:=2^{-2j}A^{j}_{\frac{1}{2},4}S^{T}_{\ell}$ has
the form

$\displaystyle M_{j,\ell}=\begin{pmatrix}2^{-j}&0&\ell_{1}2^{-j}\\\
0&2^{-j}&\ell_{2}2^{-j}\\\ 0&0&1\end{pmatrix}.$ (40)

We check (13) exemplarily for the case $\varepsilon=3$ where $Z^{3}=I$. A
calculation yields

$\displaystyle M_{j,\ell}\xi=\begin{pmatrix}2^{-j}(\xi_{1}+\ell_{1}\xi_{3})\\\
2^{-j}(\xi_{2}+\ell_{2}\xi_{3})\\\
\xi_{3}\end{pmatrix},\quad\xi=(\xi_{1},\xi_{2},\xi_{3})^{T}\in\mathbb{R}^{3}.$

Subsequently we prove that for $j\in\mathbb{N}_{0}$ and $|\ell|_{\infty}\leq
2^{j}$

$\displaystyle\text{supp
}(\hat{\gamma}^{3}_{j,\ell,k})\subseteq\mathcal{P}_{3}\cap\Big{\\{}\xi\in\mathbb{R}^{3}\leavevmode\nobreak\
:\leavevmode\nobreak\
\textstyle{\frac{1}{32}\leq|\xi_{3}|\leq\frac{1}{2}}\Big{\\}}.$ (41)

First observe that clearly $\text{supp
}(\hat{\gamma}^{3}_{j,\ell,k})\subseteq\mathcal{P}_{3}$. Now take
$\xi\in\mathcal{P}_{3}$ and
$\xi\notin\big{\\{}\xi\in\mathbb{R}^{3}:\frac{1}{32}\leq|\xi_{3}|\leq\frac{1}{2}\big{\\}}$.
With $|\xi_{3}|>\frac{1}{2}$ also $|[M_{j,\ell}\xi]_{3}|>\frac{1}{2}$ and thus
$M_{j,\ell}\xi\notin\text{supp }W$. If on the other hand
$|\xi_{3}|<\frac{1}{32}$ then $|[M_{j,\ell}\xi]_{3}|<\frac{1}{32}$ and, since
$j\geq 0$, $|\xi_{1}|\leq|\xi_{3}|$ and $|\ell|_{\infty}\leq 2^{j}$,

$\displaystyle|[M_{j,\ell}\xi]_{1}|=|2^{-j}(\xi_{1}+\ell_{1}\xi_{3})|\leq
2^{-j}(1+|\ell_{1}|)|\xi_{3}|\leq
2^{-j}(1+2^{j})|\xi_{3}|\leq(1+2^{-j})|\xi_{3}|\leq
2|\xi_{3}|<{\textstyle\frac{1}{16}}.$

Analogously, one obtains $|[M_{j,\ell}\xi]_{2}|<\frac{1}{16}$. Altogether,
this yields $|M_{j,\ell}\xi|_{\infty}<\frac{1}{16}$ if
$|\xi_{3}|<\frac{1}{32}$, which implies $M_{j,\ell}\xi\notin\text{supp }W$.
Consequently, $\hat{\gamma}^{3}_{j,\ell,k}(\xi)=0$ outside
$\mathcal{P}_{3}\cap\\{\xi\in\mathbb{R}^{3}:\textstyle{\frac{1}{32}\leq|\xi_{3}|\leq\frac{1}{2}}\\}$,
which proves (41).

Using analogous estimates for $\varepsilon\in\\{2,3\\}$ it follows that
$\text{supp
}\hat{\gamma}^{\varepsilon}_{j,\ell,k}\subseteq\textstyle{[-\frac{1}{2},\frac{1}{2}]^{3}\backslash(-\frac{1}{32},\frac{1}{32})^{3}}$
for every
$(\varepsilon,j,\ell,k)\in\Lambda_{int}=\\{(\varepsilon,j,\ell,k)\in\\{1,2,3\\}\times\mathbb{N}_{0}\times\mathbb{Z}^{2}\times\mathbb{Z}^{3}:|\ell|_{\infty}<2^{j}\\}$.

The derivatives of $\hat{\gamma}^{\varepsilon}_{j,\ell,k}$ are linear
combinations of functions
$\partial^{\beta}W(Z^{\varepsilon}M_{j,\ell}Z^{-\varepsilon}\xi)\partial^{\delta}V(Z^{-\varepsilon}\xi)$
with coefficients uniformly bounded, since the entries of $M_{j,\ell}$ are.
This fact together with the support condition implies that (13) is fulfilled
for arbitrary order.

##### Boundary Shearlets:

The boundary shearlets of (37) satisfy $j\geq 1$ and are precisely the
functions in (5.3.1) and (32). We exemplarily handle the functions (5.3.1),
the argumentation for the functions (32) is similar. Let us first look at the
boundary between $\mathcal{P}_{1}$ and $\mathcal{P}_{3}$, i.e. the functions
$\tilde{\psi}^{\varepsilon}_{j,\ell,k}$, where $\varepsilon=3$, $j\geq 1$,
$\ell_{1}=\pm 2^{j}$, $|\ell_{2}|<2^{j}$, and $k\in\mathbb{Z}^{3}$. Plugging
(5.3.1) into (39) and choosing $\mathcal{T}=\frac{1}{4}{\text{\rm
diag}}(1,1,1)$ we obtain

$\displaystyle\hat{\gamma}^{3}_{j,\ell,k}(\xi)=2^{-3}\begin{cases}W(M_{j,\ell}\xi)V(\xi)&,\xi\in
M^{-1}_{j,\ell}\mathcal{P}_{3};\\\ W(M_{j,\ell}\xi)V(N_{j,\ell}\xi)&,\xi\in
M_{j,\ell}^{-1}\mathcal{P}_{1};\end{cases}$

for the generators, where $M_{j,\ell}$ is the matrix (40) and where

$\displaystyle
N_{j,\ell}:=\begin{pmatrix}-\ell_{1}2^{-j}&0&2^{j}-\ell^{2}_{1}2^{-j}\\\
-\operatorname{\rm
sgn}(\ell_{1})\ell_{2}2^{-j}&1&\ell_{2}-2^{-j}|\ell_{1}|\ell_{2}\\\
2^{-j}&0&2^{-j}\ell_{1}\end{pmatrix}.$

Similar calculations as for the interior shearlets then prove

$\text{supp
}(\hat{\gamma}^{3}_{j,\ell,k})\subseteq\Big{\\{}\xi\in\mathbb{R}^{3}\leavevmode\nobreak\
:\leavevmode\nobreak\ \textstyle{|\frac{\xi_{1}}{\xi_{3}}|\leq
2,|\frac{\xi_{2}}{\xi_{3}}|\leq
4}\Big{\\}}\cap\Big{\\{}\xi\in\mathbb{R}^{3}\leavevmode\nobreak\
:\leavevmode\nobreak\
{\textstyle\frac{1}{64}\leq|\xi_{3}|\leq\frac{1}{2}}\Big{\\}}.$

For $\varepsilon\in\\{1,2\\}$ complementary results hold true. Altogether, it
follows $\text{supp
}\hat{\gamma}^{\varepsilon}_{j,\ell,k}\subseteq\textstyle{[-2,2]^{3}\backslash(-\frac{1}{64},\frac{1}{64})^{3}}$
for the generators of the functions (5.3.1). Hence, condition (13) is
fulfilled for arbitrary order. ∎

Proposition 5.9 in particular shows that the system $SH$ is a system of
$\frac{1}{2}$-molecules, however not with respect to a shearlet
parametrization because of the necessary relabelling $F_{label}$ in (36). The
actual parametrization is given by

$\Phi_{SH}:=\widetilde{\Phi}_{SH}\circ F_{label},$

where $\widetilde{\Phi}_{SH}$ denotes the $\frac{1}{2}$-shearlet
parametrization of the relabeled system.

######  Corollary 5.10.

The smooth shearlet frame $SH$ is a system of $3$-dimensional
$\frac{1}{2}$-molecules of order $(\infty,\infty,\infty,\infty)$ with respect
to the parametrization $(\Lambda_{SH},\Phi_{SH})$.

######  Remark 5.11.

Although $(\Lambda_{SH},\Phi_{SH})$ is not a shearlet parametrization, it
clearly is $(\frac{1}{2},k)$-consistent with every $\frac{1}{2}$-shearlet
parametrization for $k>3$. This follows from Proposition 5.6 and the
observation that relabelling of elements does not make any difference here.

####  5.3.2 Compactly Supported Pyramid-adapted Shearlets

There also exist shearlet frames for $L^{2}(\mathbb{R}^{2})$ and
$L^{2}(\mathbb{R}^{3})$ consisting of compactly supported functions. Compactly
supported frames of the form (27) have been constructed in [41, 37]. They are
also instances of $\frac{1}{2}$-shearlet molecules and their order can be
controlled by the regularity of the generators.

######  Proposition 5.12.

Let $\phi,\psi^{1},\psi^{2},\psi^{3}\in L^{2}(\mathbb{R}^{3})$ be compactly
supported and $L,M,N_{1},N_{2}\in\mathbb{N}_{0}\cup\\{\infty\\}$. If $\phi\in
C^{N_{1}+N_{2}}(\mathbb{R}^{3})$ and if, for every
$\varepsilon\in\\{1,2,3\\}$,

  1. (i)

the derivatives $\partial^{\gamma}\psi^{\varepsilon}$ exist and are continuous
for every $\gamma\in\mathbb{N}_{0}^{3}$ with
$[Z^{\varepsilon}\gamma]_{1},[Z^{\varepsilon}\gamma]_{2}\leq N_{1}+N_{2}$ and
$[Z^{\varepsilon}\gamma]_{3}\leq N_{1}$, where $Z$ is the cyclic permutation
matrix (11),

  2. (ii)

the generator $\psi^{\varepsilon}$ has $M+L$ directional vanishing moments in
$e_{\varepsilon}$-direction, i.e.

$\displaystyle\forall(x_{1},x_{2})\in\mathbb{R}^{2}:\int_{\mathbb{R}}\psi^{\varepsilon}(Z^{\varepsilon}x)x_{3}^{N}\,dx_{3}=0\quad\text{for
every $N\in\\{0,\ldots,M+L-1\\}$},$

then the system (27) obtained from these generators is a system of
$\frac{1}{2}$-shearlet molecules of order $(L,M,N_{1},N_{2})$.

###### Proof.

It is obvious that – rightly indexed – a system of the form (27) constitutes a
system of $\frac{1}{2}$-shearlet molecules. Hence we just need to verify the
order of the system. For this, little more is needed than utilizing the facts
that spatial decay implies smoothness in Fourier domain (and vice versa), and
that vanishing moments in spatial domain implies estimates of the form
$\left|\hat{g}(\xi)\right|\lesssim\min(1,\left|\xi\right|)^{M}$ in Fourier
domain. We refer to [27, Proposition 3.11] for details, where a similar two-
dimensional version of the theorem is proven. ∎

##  6 Proof of Theorem 2.5

This final section is devoted to the technical proof of Theorem 2.5. It is
split up into several pieces and has the same general structure as the proof
of the corresponding 2-dimensional result [28, Theorem 4.2]. In $d$ dimensions
however it takes more effort and the arguments are more involved.

###  6.1 Auxiliary Lemmas

Let us first collect some simple elementary facts, which turn out to be
useful. Subsequently $\mathcal{O}(d,\mathbb{R})$ shall denote the orthogonal
group of $\mathbb{R}^{d}$. Recall also the notation $\\{\theta\\}$ for the
‘projection’ of $\theta\in\mathbb{R}$ onto the interval
$[-\frac{\pi}{2},\frac{\pi}{2})$ in the sense of Subsection 2.1.

######  Lemma 6.1.

For $\theta\in\mathbb{R}$ let $\\{\theta\\}$ denote its ‘projection’ onto the
interval $[-\frac{\pi}{2},\frac{\pi}{2})$ as introduced in Subsection 2.1. It
then holds
$\left|\left\\{\theta\right\\}\right|\asymp\left|\sin(\theta)\right|$.

###### Proof.

Due to $\pi$-periodicity it suffices to verify the relation for
$\theta\in[-\frac{\pi}{2},\frac{\pi}{2})$. In this range we have
$\frac{2}{\pi}|\theta|\leq|\sin(\theta)|\leq|\theta|.$ ∎

An immediate corollary is the following result. Recall the notation
$d_{\mathbb{S}}(v,w)$ for the angle $\arccos(\langle v,w\rangle)\in[0,\pi]$
between two vectors $v,w\in\mathbb{S}^{d-1}$.

######  Lemma 6.2.

Let $e_{d}\in\mathbb{R}^{d}$ be the $d$:th unit vector. For
$\eta\in\mathbb{S}^{d-1}$ we have
$\left|\left\\{d_{\mathbb{S}}(\eta,e_{d})\right\\}\right|\asymp\left|\eta\right|_{[d-1]}$.

###### Proof.

Using a suitable rotation $R\in\mathcal{O}(d,\mathbb{R})$ of the form

$R=\begin{pmatrix}R_{d-1}&0\\\ 0&1\end{pmatrix},$

where $R_{d-1}\in\mathcal{O}(d-1,\mathbb{R})$, we can achieve
$R\eta=(\sin(\theta),0,\ldots,0,\cos(\theta))^{T}$ with
$\theta=d_{\mathbb{S}}(\eta,e_{d})$. Since $|\eta|_{[d-1]}=|\eta-
e_{d}|_{[d-1]}=|R(\eta-e_{d})|_{[d-1]}=|R\eta-e_{d}|_{[d-1]}=|\sin(\theta)|$,
it just remains to prove
$\left|\sin(\theta)\right|\asymp\left|\left\\{\theta\right\\}\right|$, which
is true by Lemma 6.1. ∎

######  Lemma 6.3.

Let $c>0$ be a constant. Then we have for all $v,w\in\mathbb{S}^{d-1}$ with
$[v]_{d}\geq c$ and $[w]_{d}\geq 0$

$\displaystyle|\\{d_{\mathbb{S}}(v,w)\\}|\asymp|v-w|.$

###### Proof.

Under the assumptions there exists $\varepsilon>0$ dependent on $c$, such that
$0\leq d_{\mathbb{S}}(v,w)\leq\pi-\varepsilon.$ It follows
$\frac{\varepsilon}{\pi-\varepsilon}|d_{\mathbb{S}}(v,w)|\leq|\\{d_{\mathbb{S}}(v,w)\\}|\leq|d_{\mathbb{S}}(v,w)|$.
The observation $d_{\mathbb{S}}(v,w)\asymp|v-w|$ finishes the proof. ∎

######  Lemma 6.4.

Let $R\in\mathcal{O}(d,\mathbb{R})$ be a rotation and
$\theta_{0}=d_{\mathbb{S}}(e_{d},Re_{d})\in[0,\pi]$ the angle between the d:th
unit vector $e_{d}\in\mathbb{R}^{d}$ and its image $Re_{d}$ under $R$. Then it
holds for all $\eta\in\mathbb{S}^{d-1}$

$\displaystyle|R\eta|_{[d-1]}=\sin(d_{\mathbb{S}}(R\eta,e_{d}))\geq\min\\{\left|\sin(d_{\mathbb{S}}(\eta,e_{d})+\theta_{0})\right|,\left|\sin(d_{\mathbb{S}}(\eta,e_{d})-\theta_{0})\right|\\}.$

Note $d_{\mathbb{S}}(\eta,e_{d})=d_{\mathbb{S}}(R\eta,Re_{d})$.

###### Proof.

Let $\eta=(\eta_{1},\ldots,\eta_{d})^{T}\in\mathbb{S}^{d-1}$ and put
$\theta_{1}:=d_{\mathbb{S}}(\eta,e_{d})=\arccos(\langle\eta,e_{d}\rangle)\in[0,\pi]$.
The rotation $R\in\mathcal{O}(d,\mathbb{R})$ can be decomposed in the form
$R=\tilde{R}R_{\theta_{0}}$ with
$\tilde{R},R_{\theta_{0}}\in\mathcal{O}(d,\mathbb{R})$ such that

$\tilde{R}=\begin{pmatrix}R_{d-1}&\\\ &1\end{pmatrix}\quad\text{and}\quad
R_{\theta_{0}}=\begin{pmatrix}\cos(\theta_{0})&&-\sin(\theta_{0})\\\
&I_{d-2}&\\\ \sin(\theta_{0})&&\cos(\theta_{0})\end{pmatrix},$

where $R_{d-1}\in\mathcal{O}(d-1,\mathbb{R})$ is some $(d-1)$-dimensional
rotation matrix and $I_{d-2}$ is the $(d-2)$-dimensional identity matrix. The
rotation $\tilde{R}$ leaves $|\cdot|_{[d-1]}$ invariant, whence

$|R\eta|_{[d-1]}=|\tilde{R}R_{\theta_{0}}\eta|_{[d-1]}=|R_{\theta_{0}}\eta|_{[d-1]}.$

Using $\eta_{d}=\cos(\theta_{1})$ and
$|\eta|^{2}_{[d-1]}=\eta_{1}^{2}+\eta_{2}^{2}+\ldots+\eta_{d-1}^{2}=1-\eta_{d}^{2}$,
it further follows

$\displaystyle\left|R_{\theta_{0}}\eta\right|_{[d-1]}^{2}$
$\displaystyle=(\cos(\theta_{0})\eta_{1}-\sin(\theta_{0})\eta_{d})^{2}+\eta_{2}^{2}+\dots+\eta_{d-1}^{2}$
$\displaystyle=\cos^{2}(\theta_{0})\eta_{1}^{2}+\sin^{2}(\theta_{0})\cos^{2}(\theta_{1})-2\cos(\theta_{0})\sin(\theta_{0})\eta_{1}\cos(\theta_{1})+(1-\eta_{1}^{2}-\cos^{2}(\theta_{1}))$
$\displaystyle=1-(\eta_{1}\sin(\theta_{0})+\cos(\theta_{1})\cos(\theta_{0}))^{2}.$

The last expression is a second-degree polynomial in the variable $\eta_{1}$
with a negative leading coefficient. Since $\eta_{1}^{2}\leq
1-\eta_{d}^{2}=1-\cos^{2}(\theta_{1})=\sin^{2}(\theta_{1})$, the variable
$\eta_{1}$ can take values only in $[-\sin(\theta_{1}),\sin(\theta_{1})]$. The
polynomial attains its minimum on this interval at the endpoints. Hence, we
can conclude

$\displaystyle\left|R_{\theta_{0}}\eta\right|_{[d-1]}^{2}$
$\displaystyle\geq\min_{\epsilon\in\\{-1,1\\}}\big{\\{}1-(\epsilon\sin(\theta_{1})\sin(\theta_{0})+\cos(\theta_{1})\cos(\theta_{0}))^{2}\big{\\}}$
$\displaystyle=\min_{\epsilon\in\\{-1,1\\}}\big{\\{}1-\cos^{2}(\theta_{1}-\epsilon\theta_{0})\big{\\}}=\min_{\epsilon\in\\{-1,1\\}}\big{\\{}\sin^{2}(\theta_{1}-\epsilon\theta_{0})\big{\\}},$

which proves the claim. ∎

###  6.2 Integral Estimates

We start with an estimate for the generators in (6), which will allow us to
work in polar coordinates.

######  Lemma 6.5.

Let the family of functions $\\{g_{\lambda}\\}_{\lambda\in\Lambda}$ satisfy
(7) uniformly for a multi-index $\rho\in\mathbb{N}^{d}_{0}$, and assume that
there is a constant $c>0$ such that $s_{\lambda}\geq c$ for all
$\lambda\in\Lambda$. Then the following estimate holds true uniformly for
$\lambda\in\Lambda$ and $\xi\in\mathbb{R}^{d}$

$\displaystyle\left|(\partial^{\rho}\hat{g}_{\lambda})(A^{-1}_{\alpha,s_{\lambda}}R_{\theta_{\lambda}}R_{\varphi_{\lambda}}\xi)\right|\lesssim\frac{\min\left\\{1,s_{\lambda}^{-1}(1+|\xi|)\right\\}^{M}}{\left(1+s_{\lambda}^{-1}|\xi|\right)^{N_{1}}(1+s_{\lambda}^{-\alpha}\left|R_{\theta_{\lambda}}R_{\varphi_{\lambda}}\xi\right|_{[d-1]})^{N_{2}}}.$
(42)

###### Proof.

We have
$|A^{-1}_{\alpha,s_{\lambda}}\xi|\geq\min\\{s_{\lambda}^{-1},s_{\lambda}^{-\alpha}\\}\left|\xi\right|\gtrsim
s_{\lambda}^{-1}\left|\xi\right|$ uniformly for $\xi\in\mathbb{R}^{d}$ and
$\lambda\in\Lambda$, since $s_{\lambda}\geq c>0$ for every
$\lambda\in\Lambda$. It follows
$|A^{-1}_{\alpha,s_{\lambda}}R_{\theta_{\lambda}}R_{\varphi_{\lambda}}\xi|\gtrsim
s_{\lambda}^{-1}\left|R_{\theta_{\lambda}}R_{\varphi_{\lambda}}\xi\right|=s_{\lambda}^{-1}|\xi|$.
Further, we observe
$|A^{-1}_{\alpha,s_{\lambda}}\xi|_{[d-1]}=s_{\lambda}^{-\alpha}\left|\xi\right|_{[d-1]}$
and
$|[A^{-1}_{\alpha,s_{\lambda}}\xi]_{d}|=s_{\lambda}^{-1}\left|[\xi]_{d}\right|$.
Finally, it holds $\langle|\xi|\rangle\asymp 1+|\xi|$ and
$\left|[\xi]_{d}\right|+\left|\xi\right|_{[d-1]}\asymp|\xi|$. Collecting all
of these estimates, one obtains

$\displaystyle\big{|}\big{(}\partial^{\rho}\hat{g}_{\lambda}\big{)}(A^{-1}_{\alpha,s_{\lambda}}R_{\theta_{\lambda}}R_{\varphi_{\lambda}}\xi)\big{|}$
$\displaystyle\lesssim\frac{\min\Big{\\{}1,s_{\lambda}^{-1}+|[A^{-1}_{\alpha,s_{\lambda}}R_{\theta_{\lambda}}R_{\varphi_{\lambda}}\xi]_{d}|+s_{\lambda}^{-(1-\alpha)}|A^{-1}_{\alpha,s_{\lambda}}R_{\theta_{\lambda}}R_{\varphi_{\lambda}}\xi|_{[d-1]}\Big{\\}}^{M}}{\langle|A^{-1}_{\alpha,s_{\lambda}}R_{\theta_{\lambda}}R_{\varphi_{\lambda}}\xi|\rangle^{N_{1}}\langle|A^{-1}_{\alpha,s_{\lambda}}R_{\theta_{\lambda}}R_{\varphi_{\lambda}}\xi|_{[d-1]}\rangle^{N_{2}}}$