DIV=10,numbers=noenddot twoside=semi, twocolumn=false,
headinclude=false,footinclude=false,mpinclude=false,headlines=2.1,headsepline=true,footsepline=false,cleardoublepage=empty
parskip=relative, bibliography=totoc ection]section section subsection
subsubsection paragraph pageheadfoot

Sampling Rates for $\ell^{1}$-Synthesis

[2em]2em

Maximilian März§, Claire Boyer∗, Jonas Kahn†, Pierre Weiss‡

Affiliations: §Technische Universität Berlin; ∗LPSM, Sorbonne Université, ENS
Paris; †Université de Toulouse; ‡ITAV, CNRS, Université de Toulouse

E-Mail of corresponding author<EMAIL_ADDRESS>
Abstract. This work investigates the problem of signal recovery from
undersampled noisy sub-Gaussian measurements under the assumption of a
synthesis-based sparsity model. Solving the $\ell^{1}$-synthesis basis pursuit
allows for a simultaneous estimation of a coefficient representation as well
as the sought-for signal. However, due to linear dependencies within redundant
dictionary atoms it might be impossible to identify a specific representation
vector, although the actual signal is still successfully recovered. The
present manuscript studies both estimation problems from a non-uniform,
signal-dependent perspective. By utilizing recent results on the convex
geometry of linear inverse problems, the sampling rates describing the phase
transitions of each formulation are identified. In both cases, they are given
by the conic Gaussian mean width of an $\ell^{1}$-descent cone that is
linearly transformed by the dictionary. In general, this expression does not
allow a simple calculation by following the polarity-based approach commonly
found in the literature. Hence, two upper bounds involving the sparsity of
coefficient representations are provided: The first one is based on a local
condition number and the second one on a geometric analysis that makes use of
the thinness of high-dimensional polyhedral cones with not too many
generators. It is furthermore revealed that both recovery problems can differ
dramatically with respect to robustness to measurement noise – a fact that
seems to have gone unnoticed in most of the related literature. All insights
are carefully undermined by numerical simulations.

Key words. Compressed sensing, inverse problems, sparse representations,
redundant dictionaries, non-uniform recovery, Gaussian mean width,
circumangle.

##  1 Introduction

In the last two decades, the methodology of _compressive sensing_ promoted the
use of sparsity based methods for many signal processing tasks. Following the
seminal works of Candès, Donoho, Romberg and Tao [CRT06, CT06, Don06], a vast
amount of research has extended the understanding, how additional structure
can be exploited for solving ill-posed inverse problems. The classical setup
in this area considers a _non-adaptive, linear measurement model,_ which reads
as follows:

Let $\bm{x}_{0}\in\mathbb{R}^{n}$ be a fixed vector, which is typically
referred to as the _signal_. Assume that we are given $m$ _measurements_
$\bm{y}\in\mathbb{R}^{m}$ of $\bm{x}_{0}$ via the linear acquisition model
$\bm{y}=\bm{A}\bm{x}_{0}+\bm{e},$ (1.1) where $\bm{A}\in\mathbb{R}^{m\times
n}$ is the so-called _measurement matrix_ and $\bm{e}\in\mathbb{R}^{m}$ models
_measurement noise_ with $\left\|\bm{e}\right\|_{2}\leq\eta$ for some
$\eta\geq 0$.

The goal of compressive sensing is to solve this inverse problem by
reconstructing an approximation of the signal $\bm{x}_{0}$ from its indirect
measurements $\bm{y}$. Remarkably, even if $m\ll n$, this task can be achieved
by incorporating additional information during the reconstruction process.
Most classical compressive sensing works directly assume that $\bm{x}_{0}$ is
_$s$ -sparse_, i.e., that at most $s\ll n$ entries of $\bm{x}_{0}$ are nonzero
or in symbols
$\left\|\bm{x}_{0}\right\|_{0}=\\#\operatorname{supp}(\bm{x}_{0})\leq s$.
However, this assumption is hardly satisfied in any real-world application.
Nevertheless, many signals allow for sparse representations using specific
transforms, such as Gabor dictionaries, wavelet systems or data-adaptive
representations, which are inferred from a given set of training samples. Such
a model is referred to as _synthesis formulation_ , since it assumes that
there exists a matrix $\bm{D}\in\mathbb{R}^{n\times d}$ and a low-complexity
representation $\bm{z}_{0}\in\mathbb{R}^{d}$ such that $\bm{x}_{0}$ can be
“synthesized” as

$\bm{x}_{0}=\bm{D}\cdot\bm{z}_{0}.$ (1.2)

Following the standard terminology of the field, the matrix
$\bm{D}=[\bm{d}_{1},\dots,\bm{d}_{d}]$ will be henceforth refered to as
_dictionary_ and its columns as _dictionary atoms_. It can be expected that
the coefficient vector $\bm{z}_{0}$ is dominated by just a few large entries,
provided that $\bm{D}$ allows to capture the signal’s inherent structure
reasonably well.

The synthesis formulation of compressive sensing exploits such a
representation model, for instance, by employing greedy-based reconstruction
algorithms or by utilizing the sparsity-promoting effect of the
$\ell^{\smash{1}}$-norm. In this work, we will consider the following convex
program, which we refer to as _synthesis basis pursuit for coefficient
recovery_ :

$\hat{Z}\coloneqq\operatorname*{argmin}_{\bm{z}\in\mathbb{R}^{d}}\left\|\bm{z}\right\|_{1}\quad\mbox{
s.t. }\quad\left\|\bm{y}-\bm{A}\bm{D}\bm{z}\right\|_{2}\leq\eta.$
($\text{BP}_{\eta}^{\text{\smash{coef}}}$)

Under suitable assumptions, one might hope that solutions $\hat{\bm{z}}$ of
this minimization program approximate $\bm{z}_{0}$ reasonably well. Indeed, if
$\bm{D}=\operatorname{\textbf{Id}}$, the formulation
($\text{BP}_{\eta}^{\text{\smash{coef}}}$) turns into the classical basis
pursuit. It allows to recover any $s$-sparse vector $\bm{z}_{0}$ with
overwhelming probability, if $\bm{A}$ additionally follows a suitable random
distribution and $m\gtrsim s\cdot\log(2n/s)$ [FR13].

In many practical and theoretical situations, it turns out that using
redundant dictionaries, i.e., choosing $d\gg n$, is beneficial. For instance,
the stationary wavelet transform overcomes the lack of translation invariance
and learned dictionaries typically infer a larger set of convolutional
filters, which are adapted to a particular data distribution. If $\bm{D}$ does
not form a basis, representations as in (1.2) are not necessarily unique
anymore. Hence, it is not to be expected that a specific representation can be
identified by solving ($\text{BP}_{\eta}^{\text{\smash{coef}}}$). However, in
many situations of interest, the representation vector itself is irrelevant
and a recovery of the actual signal $\bm{x}_{0}$ is of primary interest. Thus,
one rather cares about the _synthesis basis pursuit for signal recovery_ ,
which amounts to solving

$\hat{X}\coloneqq\bm{D}\cdot\left(\operatorname*{argmin}_{\bm{z}\in\mathbb{R}^{d}}\left\|\bm{z}\right\|_{1}\quad\mbox{
s.t. }\quad\left\|\bm{y}-\bm{A}\bm{D}\bm{z}\right\|_{2}\leq\eta\right).$
($\text{BP}_{\eta}^{\text{\smash{sig}}}$)

In the noiseless case (i.e., when $\bm{e}=\bm{0}$ and $\eta=0$), it might be
the case that $\hat{Z}\neq\left\\{\bm{z}_{0}\right\\}$, but there is still
hope that $\hat{X}=\bm{D}\cdot\hat{Z}=\left\\{\bm{x}_{0}\right\\}$. In other
words, although solving ($\text{BP}_{\eta}^{\text{\smash{coef}}}$) might fail
in identifying a specific coefficient representation, it is still possible
that the actual signal is successfully recovered by a subsequent synthesis
with $\bm{D}$.

(a)

(b)

Figure 1: Phase transitions of coefficient and signal recovery by
$\ell^{1}$-synthesis. Subfigure 1(a) shows the empirical probability that
atomic coefficient representations are successfully recovered via solving
($\text{BP}_{\smash{\eta=0}}^{\text{\smash{coef}}}$), whereas Subfigure 1(b)
shows the empirical probability for the associated signal reconstruction by
($\text{BP}_{\smash{\eta=0}}^{\text{\smash{sig}}}$). The underlying dictionary
is a redundant Haar wavelet frame with three decomposition levels and the
defining $s$-sparse coefficients are chosen at random; see Section 5.3 for a
precise documentation of the experiment. The brightness of each pixel reflects
the observed probability of success, reaching from certain failure (black) to
certain success (white). The dotted line shows our predictions for the
location of the phase transitions, see Theorem 3.6 and Theorem 3.8,
respectively.

###  1.1 What This Paper Is About

The goal of this work is to broaden the understanding of the conditions that
guarantee _coefficient_ and _signal recovery_ by solving
($\text{BP}_{\eta}^{\text{\smash{coef}}}$) and
($\text{BP}_{\eta}^{\text{\smash{sig}}}$), respectively. To that end, we
believe that addressing the following, non-exhaustive list of questions will
be of particular importance:

  1. (Q1)

Under which circumstances does coefficient and signal recovery differ, i.e.,
when is it impossible to reconstruct a specific coefficient representation
although the signal itself might still be identified?

  2. (Q2)

If possible, how many measurements are required to reconstruct a specific
coefficient representation? Analogously, how many measurements are required to
recover the associated signal?

  3. (Q3)

In case that coefficients and signals can both be identified, are there still
differences between the two formulations, for instance with respect to
robustness to measurement noise?

Set out to find answers to these questions, we first restrict ourselves to the
following sub-Gaussian measurement model, which will be considered in this
work unless stated otherwise:

Let $\bm{a}\in\mathbb{R}^{n}$ be an isotropic
($\mathbb{E}[\bm{a}\bm{a}^{T}]=\operatorname{\textbf{Id}}$), zero mean, sub-
Gaussian111A random variable $a$ is _sub-Gaussian_ if
$\left\|a\right\|_{\psi_{2}}\coloneqq\sup_{q\geq
1}q^{-1/2}(\mathbb{E}[|a|^{q}])^{1/q}<\infty$, with
$\left\|\cdot\right\|_{\psi_{2}}$ being the _sub-Gaussian norm of $a$._ For a
random vector $\bm{a}\in\mathbb{R}^{n}$ the sub-Gaussian norm is then given by
$\left\|\bm{a}\right\|_{\psi_{2}}\coloneqq\sup_{\bm{v}\in\mathcal{S}^{\smash{n-1}}}\left\|\left\langle\bm{a},\bm{v}\right\rangle\right\|_{\psi_{2}}$
and $\bm{a}$ is called sub-Gaussian if
$\left\|\bm{a}\right\|_{\psi_{2}}<\infty$; see for instance [Ver12] for
further details. random vector with
$\left\|\bm{a}\right\|_{\psi_{2}}\leq\gamma$. The sampling matrix $\bm{A}$ is
formed by drawing $m$ independent copies $\bm{a}_{1},\dots,\bm{a}_{m}$ of
$\bm{a}$ and setting $\bm{A}=\begin{bmatrix}-\bm{a}_{1}^{T}-\\\ \vdots\\\
-\bm{a}_{m}^{T}-\end{bmatrix}.$ (1.3)

This model has been established as a somewhat classical benchmark setup in the
context of compressive sensing. It allows us to follow the methodology
initiated in [RV07, MPT07] and extended in [Sto09, CRPW12, Tro15, ALMT14]. In
a nutshell, the aim is to determine the _sampling rate_ of a convex program
(i.e., the number of required measurements for successful recovery) by
calculating the so-called _Gaussian mean width_.

We now briefly outline our work and summarize its main contributions:

  * (C1)

A cornerstone of our analysis is formed by the set of _minimal
$\ell^{1}$-representers_ of $\bm{x}_{0}$:

$Z_{\ell^{\smash{1}}}\coloneqq\operatorname*{argmin}_{\bm{z}\in\mathbb{R}^{d}}\left\|\bm{z}\right\|_{1}\quad\mbox{
s.t. }\quad\bm{x}_{0}=\bm{D}\bm{z}.$ ($\text{BP}_{\ell^{1}}$)

Independently of Model 1.1, Section 3.1 reveals that if
$Z_{\ell^{\smash{1}}}=\left\\{\bm{z}_{0}\right\\}$, exact recovery of
$\bm{z}_{0}$ via ($\text{BP}_{\smash{\eta=0}}^{\text{\smash{coef}}}$) is
equivalent to perfect recovery of $\bm{x}_{0}$ by solving
($\text{BP}_{\smash{\eta=0}}^{\text{\smash{sig}}}$). Furthermore, exact
recovery of a coefficient vector $\bm{z}_{0}$ by
($\text{BP}_{\smash{\eta=0}}^{\text{\smash{coef}}}$) is only possible, if
$\bm{z}_{0}$ is the unique minimal $\ell^{\smash{1}}$-representer of
$\bm{x}_{0}=\bm{D}\bm{z}_{0}$, i.e., if
$Z_{\ell^{\smash{1}}}=\left\\{\bm{z}_{0}\right\\}$.

  * (C2)

In Section 3.2 and Section 3.3, it will be shown that the sampling rate of
both formulations can be expressed by the squared conic mean width
$w^{2}_{\wedge}(\bm{D}\cdot\mathcal{D})$, where $\mathcal{D}$ denotes the
descent cone of the $\ell^{\smash{1}}$-norm at any
$\bm{z}_{\ell^{\smash{1}}}\in Z_{\ell^{\smash{1}}}$ (see Section 2 for a brief
summary of the general recovery framework and definitions of these notions).
This observation holds unconditionally true in the case of signal recovery by
($\text{BP}_{\eta}^{\text{\smash{sig}}}$). For coefficient recovery the
additional assumption that $Z_{\ell^{\smash{1}}}$ is a singleton needs to be
satisfied.

  * (C2’)

While $w^{2}_{\wedge}(\bm{D}\cdot\mathcal{D})$ forms a precise description of
the sampling rate, it is a quantity that is hard to analyze and compute, in
general. Therefore, an important goal of our work is to derive more
informative upper bounds for this expression. First, under the assumption that
$Z_{\ell^{\smash{1}}}=\left\\{\bm{z}_{\ell^{\smash{1}}}\right\\}$ is a
singleton, we show a condition number bound that relates
$w^{2}_{\wedge}(\bm{D}\cdot\mathcal{D})$ to the classical complexity
$w^{2}_{\wedge}(\mathcal{D})\lesssim s\cdot\log(2n/s)$, where
$s=\left\|\bm{z}_{\ell^{\smash{1}}}\right\|_{0}$ (see Section 4.1).

The second upper bound of Section 4.2 is central to our work. It is based on a
geometric analysis that makes use of generic arguments from high-dimensional
convex geometry. In comparison to the first bound, it is more general since we
do not assume that $Z_{\ell^{\smash{1}}}$ is a singleton. Hence, it
particularly addresses the recovery of signals, without requiring the
identification of a coefficient representation. The resulting upper bound on
the conic mean width relies on the thinness of high-dimensional polyhedral
cones with not exponentially many generators. We believe that such an argument
might be of general interest beyond its application to the synthesis
formulation of compressive sensing. Again,
$w^{2}_{\wedge}(\bm{D}\cdot\mathcal{D})$ is related to the sparsity of a
minimal $\ell^{1}$-representation and a further geometrical parameter
(referred to as _circumangle_) that measures the narrowness of the associated
cone.

  * (C3)

Lastly, our recovery statements reveal that recovery of signals by
$\eqref{eq:sig}$ is robust to measurement noise without any further
restrictions. In contrast, the robustness of coefficient recovery via solving
($\text{BP}_{\eta}^{\text{\smash{coef}}}$) is influenced by an additional
factor that is related to the convex program ($\text{BP}_{\ell^{1}}$).

All our findings are underpinned by extensive numerical experiments; see
Section 5. As a first “teaser” we refer the reader to Figure 1, which displays
two _phase transition plots_ and our sampling rates for a redundant Haar
wavelet system $\bm{D}$.

###  1.2 Related Literature

In the following, we first briefly discuss some historical references that are
of general interest for $\ell^{\smash{1}}$-norm minimization, sparse
representations in redundant dictionaries and compressive sensing.
Subsequently, we focus on the existing literature on the synthesis formulation
in more depth.

####  1.2.1 Some Historical Landmarks

The idea of promoting sparsity in discrete or continuous dictionaries by
$\ell^{1}$-norm minimization can be traced back to the works of Beurling
[Beu38] and Krein [Kre38]. Motivated by questions in Banach space geometry,
first theorems establishing sparsity of solutions of related minimization
problems can be found in the 1940’s [Zuh48]. In his PhD-thesis of 1965, Logan
utilized $\ell^{\smash{1}}$-minimization for sparse frequency estimation
[Log65] and in the 1970’s it was employed for solving deconvolution problems
in geophysics [CM73, TBM79]. Of particular importance became the so-called
_Rudin-Osher-Fatemi-model_ [ROF92], which pioneered the use of total variation
minimization for image processing tasks.

The field of sparse representations arose with the development of (greedy)
algorithms for finding expansions in redundant dictionaries such as time-
frequency systems [MZ93, PRK93]. Subsequently, the work [CDS98] triggered
notable interest in achieving this task by solving the basis pursuit
($\text{BP}_{\ell^{1}}$); see for instance [EB02, DH01, DE03]. A special
emphasis was thereby given to unions of orthogonal bases [EB02, GN03, CR06].
Next to the classical concepts of coherence and spark, which are _uniform_
across all $s$-sparse signals, also the _non-uniform_ notions of dual
certificates and exact recovery conditions were progressively introduced
[Fuc04, Tro04, Fuc05, Tro06].

Under the notion of _compressive sensing_ , Candès, Romberg and Tao [CRT06,
CRT06a] and Donoho [Don06] first proposed to capitalize on randomized models
in the basis pursuit. In these works, the structured dictionary $\bm{D}$ is
replaced by a random matrix $\bm{A}$, which follows for instance Model 1.1.
Such a design allows to overcome severe shortcomings of previous results, in
particular the _quadratic/square root-bottleneck_ ; see next subsection or
[FR13, Chapter 5.4]. Indeed, under such a randomness assumption, it can be
shown that any $s$-sparse vector can be recovered with overwhelming
probability if the number of measurements obeys $m\gtrsim s\cdot\log(2n/s)$.
These seminal works can furthermore be acknowledged for highlighting the
remarkable potential of sparsity-based methods for many signal recovery tasks.

####  1.2.2 Results on the Synthesis Formulation of Compressed Sensing

An important insight on solving the inverse problem of Model 1 by means of
redundant dictionaries was provided by Elad, Milanfar and Rubinstein [EMR07].
Therein, the authors compare two different formulations: The synthesis basis
pursuit ($\text{BP}_{\eta}^{\text{\smash{sig}}}$) and an alternative
formulation, which is referred to as _$\ell^{\smash{1}}$ -analysis basis
pursuit_:

$\min\nolimits_{\bm{x}\in\mathbb{R}^{n}}\left\|\bm{\Psi}\bm{x}\right\|_{1}\quad\mbox{
s.t. }\quad\left\|\bm{y}-\bm{A}\bm{x}\right\|_{2}\leq\eta.$ (1.4)

The analysis operator $\bm{\Psi}\in\mathbb{R}^{d\times n}$ is thereby chosen
in such a way that the coefficient vector $\bm{\Psi}\bm{x}_{0}$ is of low-
complexity. It turns out that the latter formulation and the program
($\text{BP}_{\eta}^{\text{\smash{sig}}}$) are only equivalent if $\bm{\Psi}$
(or $\bm{D}$) forms a basis. In particular for redundant choices of
$\bm{\Psi}$ and $\bm{D}$, the geometry of both formulations departs
significantly from each other. While the synthesis variant appears to be more
natural from a historical perspective, its analysis-based counterpart gained
considerable attention in the past years [CENR11, NDEG13, GNEGD14, KNW15,
KR15, KRZ15]. Recently, the non-uniform approach of [GKM20] revealed that the
measure of “low-complexity” in the analysis model goes beyond pure sparsity of
$\bm{\Psi}\bm{x}_{0}$. Instead, a novel sampling-rate bound was proposed that
is based on a generalized notion of sparsity, taking the support and the
coherence structure of the underlying analysis operator into account.

The earliest reference that deals with the synthesis formulation for the
recovery of coefficient vectors appears to be by Rauhut, Schnass and
Vandergheynst [RSV08]. Therein, the formulation
($\text{BP}_{\eta}^{\text{\smash{coef}}}$) is studied under a randomized
measurement model. The main result roughly reads as follows: Assume that the
dictionary $\bm{D}$ satisfies a _restricted isometry property (RIP)_ with
sparsity level $s$. If the random matrix $\bm{A}\in\mathbb{R}^{m\times n}$
follows Model 1.1 and $m\gtrsim s\cdot\log(n/s)$, then the composition
$\bm{A}\bm{D}$ will also satisfy an RIP with sparsity level $s$ with high
probability. This property then implies stable and robust recovery of all
$s$-sparse coefficient vectors by solving
($\text{BP}_{\eta}^{\text{\smash{coef}}}$). The assumption that $\bm{D}$
satisfies an RIP is crucial for the previous result. It can be for instance
achieved if the dictionary is sufficiently incoherent, i.e., if it satisfies

$\mu(\bm{D})\coloneqq\max\nolimits_{i\neq
j}\left|\left\langle\bm{d}_{i},\bm{d}_{j}\right\rangle\right|/({\left\|\bm{d}_{i}\right\|_{2}\cdot\left\|\bm{d}_{j}\right\|_{2}})\leq
1/(16\cdot(s-1)).$ (1.5)

However, as the authors of [RSV08] point out, such a coherence-based estimate
is rather crude and suffers from the so-called square-root bottleneck: The
Welch bound [FR13, Theorem 5.7] reveals that condition (1.5) can only be
satisfied for mild sparsity values $s\lesssim\sqrt{n}$.

In [CWW14], Chen, Wang and Wang study conditions for signal recovery via a
dictionary-based _null space property (NSP)_ : For a given dictionary
$\bm{D}$, a matrix $\bm{A}$ is said to satisfy the $\bm{D}$-NSP of order $s$,
if for any index set $S\subseteq[d]$ with $\\#S\leq s$ and any
$\bm{h}\in\bm{D}^{-1}(\ker{\bm{A}}\setminus\\{\bm{0}\\})$, there exists
$\bm{z}\in\ker{\bm{D}}$, such that
$\left\|\bm{h}_{S}+\bm{z}\right\|_{1}<\left\|\bm{h}_{S^{c}}\right\|_{1}$. It
can be shown that this condition is necessary and sufficient for the uniform
recovery of all signals $\bm{x}_{0}=\bm{D}\bm{z}_{0}$ with
$\left\|\bm{z}_{0}\right\|_{0}\leq s$ via
($\text{BP}_{\eta}^{\text{\smash{sig}}}$). Note that the $\bm{D}$-NSP is in
general weaker than requiring that $\bm{A}\bm{D}$ satisfies the standard NSP.
This means that the previous result is addressing signal recovery without
necessarily requiring coefficient recovery. However, the authors then show
that under the additional assumption that $\bm{D}$ is of _full spark_ (i.e.,
every $n$ columns of $\bm{D}$ are linearly independent), both conditions are
in fact equivalent. Hence, in this case, signal and coefficient recovery are
also equivalent. In the recent work [CCL19], this serves as a motivation to
study coefficient recovery by analyzing how many measurements are required in
order to guarantee that $\bm{A}\bm{D}$ has an NSP. To that end, a result is
provided that is conceptually similar to [RSV08], however, it reduces the
assumptions on $\bm{D}$. Instead of requiring that $\bm{D}$ satisfies an RIP,
the authors operate under the weaker assumption that $\bm{D}$ satisfies an
NSP. The main result essentially reads as follows: Under a sub-Gaussian
measurement setup similar to Model 1.1 and under the assumption that $\bm{D}$
satisfies an NSP of order $s$, a number of $m\gtrsim s\cdot\log(n/s)$
measurements guarantees that also $\bm{A}\bm{D}$ satisfies an NSP. This
condition then allows for robust recovery of all $s$-sparse coefficient
vectors by solving ($\text{BP}_{\eta}^{\text{\smash{coef}}}$).

To the best of our knowledge, the only work that provides a bound on the
required number of measurement for signal recovery (without necessarily
requiring coefficient recovery) is the tutorial [Ver15, Theorem 7.1]: Assume
that $\left\|\bm{d}_{i}\right\|_{2}\leq 1$, $i\in[d]$ and that
$\bm{x}_{0}=\bm{D}\bm{z}_{0}$ for an $s$-sparse representation
$\bm{z}_{0}\in\mathbb{R}^{\smash{d}}$. For a Gaussian measurement matrix
$\bm{A}\in\mathbb{R}^{m\times n}$, Vershynin establishes the following
recovery bound in expectation:

$\mathbb{E}\left\|\hat{\bm{x}}-\bm{x}_{0}\right\|_{2}\leq
c\cdot\sqrt{\tfrac{s\cdot\log(d)}{m}}\cdot\left\|\bm{z}_{0}\right\|_{2}+\sqrt{2\pi}\cdot\tfrac{\eta}{\sqrt{m}},$
(1.6)

where $c$ is a constant and $\hat{\bm{x}}\in\hat{X}$ is a solution of
($\text{BP}_{\eta}^{\text{\smash{sig}}}$). Note that we have slightly adapted
the statement of [Ver15, Theorem 7.1] for a better match with our setup. Due
to the first summand on the right hand side, the previous error bound is
suboptimal, cf. Theorem 3.8. In particular, it does not guarantee exact
recovery from noiseless measurements. We emphasize that parts of our work are
inspired by Vershynin, who also studies the gauge of the set
$K=\bm{D}\cdot\text{B}_{1}^{\smash{d}}$ in [Ver15].

We conclude by mentioning a few more works in the literature on synthesis
based compressed sensing that appear to be of less relevance for this work.
The influential paper [CRPW12] studies signal recovery via atomic
minimization, however, it does not provide specific insights when redundant
dictionaries are used. In [DNW13], a (theoretical) CoSaMP algorithm is adapted
to the recovery of signals with sparse representations in redundant
dictionaries. Based on the $\bm{D}$-RIP [CENR11] and on a connection to the
analyis formulation with so-called optimal dual frames, [LLMLY12] derives a
theorem concerning signal recoery. Finally, [SF09] provides numerical
experiments, which empirically compare the analysis and the synthesis
formulation.

####  1.2.3 The Gap that We Intend to Fill

In order to obtain statements that are _uniform_ across all $s$-sparse
signals, most existing results assume that the dictionary $\bm{D}$ satisfies
strong assumptions, e.g., incoherent atoms, an NSP or an RIP [RSV08, CWW14,
CCL19]. Such notions are well established and allow for appealing results that
often resemble known principles of compressive sensing. However, in many
situations of interest, these assumptions are too restrictive. In particular,
redundant representation systems (such as Gabor systems, wavelets, curvelets,
…) or data-adaptive dictionaries do not satisfy any such property. Their atoms
are typically highly coherent and share many linear dependencies. We aim to
address this issue by following a local, non-uniform approach, which avoids
strong assumptions on the dictionary. We believe that such a signal-dependent
refinement is crucial for redundant representation systems, cf. [GKM20].

Similarly, it is occasionally argued that distinguishing signal and
coefficient recovery is of minor importance, cf. [CCL19]. This is justified by
the observation that exact recovery of coefficients and signals is equivalent
if $\bm{D}$ is in general position. However, due to the linear dependencies in
many structured representation systems, such an argumentation is often not
valid. Indeed, simple numerical experiments with popular dictionaries reveal
that signal recovery can be frequently observed without reconstructing a
specific coefficient representation, see Figure 1 and Section 5. Hence, we
believe that it is important to study both formulations and to identify under
which conditions coefficient recovery might be expected, see (C1) above.

To the best of our knowledge, this is the first work that provides a precise
description of the phase transition behavior of both formulations, see (C2).
While the identified conic mean width of a linearly transformed set
$w^{2}_{\wedge}(\bm{D}\cdot\mathcal{D})$ is a rather implicit quantity, it
constitutes an important step towards the understanding of
$\ell^{\smash{1}}$-synthesis. By deriving more explicit upper bounds on the
sampling rate, coefficient sparsity is identified as an important factor.
However, additional properties that account for the local geometry are also
taken into account, see (C2’).

Last but not least, we establish that both formulations behave differently
with respect to robustness to measurement noise, see (C3). To the best of our
knowledge, this aspect has gone unnoticed in the literature so far, although
it might have dramatic implications on the reconstruction quality of
coefficient representations.

###  1.3 Notation

For the convenience of the reader, we have collected the most important and
frequently used objects in Table 1.

Notation | Term
---|---
$\bm{x}_{0}\in\mathbb{R}^{n}$ | (ground truth) signal vector
$\bm{A}\in\mathbb{R}^{m\times n}$ | measurement matrix
$\bm{e}\in\mathbb{R}^{m}$, with $\left\|\bm{e}\right\|_{2}\leq\eta$ | (adversarial) noise
$\bm{y}=\bm{A}\bm{x}_{0}+\bm{e}\in\mathbb{R}^{m}$ | linear, noisy measurements of $\bm{x}_{0}$
$\bm{d}_{1},\dots,\bm{d}_{d}\in\mathbb{R}^{n}$ | dictionary atoms
$\bm{D}=[\bm{d}_{1},\dots,\bm{d}_{d}]\in\mathbb{R}^{n\times d}$ | dictionary
$\hat{\bm{x}}\in\mathbb{R}^{n}$ | a solution of ($\text{BP}_{\eta}^{\text{\smash{sig}}}$)
$\hat{X}=\bm{D}\cdot\hat{Z}\subseteq\mathbb{R}^{n}$ | solution set of ($\text{BP}_{\eta}^{\text{\smash{sig}}}$)
$\bm{z}_{\ell^{\smash{1}}}\in\mathbb{R}^{d}$ | a minimal $\ell^{1}$-decomposition of $\bm{x}_{0}$ in $\bm{D}$, i.e., a solution of ($\text{BP}_{\ell^{1}}$)
$Z_{\ell^{\smash{1}}}\subseteq\mathbb{R}^{d}$ | solution set of ($\text{BP}_{\ell^{1}}$)
$\bm{z}_{0}\in\mathbb{R}^{d}$ | a sparse representation of $\bm{x}_{0}$ in $\bm{D}$, without $\bm{z}_{0}\in Z_{\ell^{\smash{1}}}$, in general
$\hat{\bm{z}}\in\mathbb{R}^{d}$ | a solution of ($\text{BP}_{\eta}^{\text{\smash{coef}}}$)
$\hat{Z}\subseteq\mathbb{R}^{d}$ | solution set of ($\text{BP}_{\eta}^{\text{\smash{coef}}}$)
Table 1: A summary of the central notations used in this work.

Throughout this manuscript we will use the following notation and conventions:
for an integer $n\in\mathbb{N}$ we set $[n]\coloneqq\\{1,2,\dots,n\\}$. If
$\mathcal{I}\subseteq[n]$, we let
$\mathcal{I}^{c}\coloneqq[n]\setminus\mathcal{I}$ denote the complement of
$\mathcal{I}$ in $[n]$. Vectors and matrices are symbolized by lower- and
uppercase bold letters, respectively. Let
$\bm{x}=(x_{1},\dots,x_{n})\in\mathbb{R}^{n}$. For an index set
$\mathcal{I}\subseteq[n]$, we let the vector
$\bm{x}_{\mathcal{I}}\in\mathbb{R}^{\\#\mathcal{I}}$ denote the restriction to
the components indexed by $\mathcal{I}$. The _support_ of $\bm{x}$ is defined
by the set of its non-zero entries
$\operatorname{supp}(\bm{x})\coloneqq\\{k\in[n]\mid x_{k}\neq 0\\}$ and the
_sparsity_ of $\bm{x}$ is
$\|\bm{x}\|_{0}\coloneqq\\#\operatorname{supp}(\bm{x})$. For $1\leq
p\leq\infty$, $\|\cdot\|_{p}$ denotes the _$\ell^{p}({})$ -norm_ on
$\mathbb{R}^{n}$. The associated _unit ball_ is given by
$\text{B}_{p}^{\smash{n}}\coloneqq\\{\bm{x}\in\mathbb{R}^{n}\mid\|\bm{x}\|_{p}\leq
1\\}$ and the _Euclidean unit sphere_ is
$S^{n-1}\coloneqq\\{\bm{x}\in\mathbb{R}^{n}\mid\|\bm{x}\|_{2}=1\\}$. The
$i$-th standard basis vector of $\mathbb{R}^{n}$ is refered to as $\bm{e}_{i}$
and $\operatorname{\textbf{Id}}\in\mathbb{R}^{n\times n}$ denotes the identity
matrix. Furthermore, let $\operatorname{cone}(K)$ denote the _conic hull_ of a
set $K\subset\mathbb{R}^{n}$. If $L\subset\mathbb{R}^{n}$ is a linear
subspace, the associated _orthogonal projection onto $L$_ is given by
$\bm{P}_{L}\in\mathbb{R}^{n\times n}$. Then, we have
$\bm{P}_{{L}^{\perp}}=\operatorname{\textbf{Id}}-\bm{P}_{L}$, where
${L}^{\perp}\subset\mathbb{R}^{n}$ is the orthogonal complement of $L$. The
letter $c$ is usually reserved for a (generic) constant, whose value could
change from time to time. We refer to $c$ as a _numerical constant_ if its
value does not depend on any other involved parameter. If an (in-)equality
holds true up to a numerical constant $c$, we sometimes write $a\lesssim b$
instead of $a\leq c\cdot b$. For a matrix $\bm{A}\in\mathbb{R}^{m\times n}$ we
let $\left\|\bm{A}\right\|_{2}$ denote its _spectral norm_. For a set
$K\subseteq\mathbb{R}^{n}$, $\lambda\in\mathbb{R}$ and
$\bm{A}\in\mathbb{R}^{m\times n}$ we set $\lambda\cdot
K\coloneqq\\{\lambda\bm{k}:\bm{k}\in K\\}$ and $\bm{A}\cdot
K\coloneqq\\{\bm{A}\bm{k}:\bm{k}\in K\\}$. Lastly, the term _orthonormal
basis_ is abbreviated by ONB.

##  2 A Primer on the Convex Geometry of Linear Inverse Problems

In this section, we give a brief introduction to a well-established
methodology that addresses the recovery of structured signals from independent
linear random measurements. This summary mainly serves the purpose of
introducing the required technical notions for our subsequent analysis of the
$\ell^{\smash{1}}$-synthesis formulation. It is inspired by [CRPW12, Tro15,
ALMT14] and we refer the interested reader to these works for a more detailed
discussion of the presented material.

###  2.1 Minimum Conic Singular Value

Assume that Model 1 is satisfied. For a robust recovery of $\bm{x}_{0}$ from
its linear, noisy measurements $\bm{y}$, we consider the _generalized basis
pursuit_

$\min_{\bm{x}\in\mathbb{R}^{n}}f(\bm{x})\quad\mbox{ s.t.
}\quad\left\|\bm{y}-\bm{A}\bm{x}\right\|_{2}\leq\eta,$
($\text{BP}_{\eta}^{\smash{f}}$)

where $f\colon\mathbb{R}^{n}\to\mathbb{R}$ is a convex function that is
supposed to reflect the “low complexity” of the signal $\bm{x}_{0}$. Hence,
the previous minimization problem searches for the most structured signal that
is still consistent with the given measurements $\bm{y}$.

The recovery performance of ($\text{BP}_{\eta}^{\smash{f}}$) can be understood
by a fairly standard geometric analysis. It seeks to understand the geometric
interplay of the structure-promoting functional $f$ and the measurement matrix
$\bm{A}$ in a neighborhood of the signal vector $\bm{x}_{0}$. To that end, we
first introduce the following notions of descent cones and minimum conic
singular values.

######  Definition 2.1 (Descent cone)

Let $f\colon\mathbb{R}^{n}\to\mathbb{R}$ be a convex function and let
$\bm{x}_{0}\in\mathbb{R}^{n}$. The _descent set_ of $f$ at $\bm{x}_{0}$ is
given by

$\mathcal{D}(f,\bm{x}_{0})\coloneqq\left\\{\bm{h}\in\mathbb{R}^{n}:f(\bm{x}_{0}+\bm{h})\leq
f(\bm{x}_{0})\right\\},$ (2.1)

and the corresponding _descent cone_ is defined by
$\mathcal{D}_{\wedge}(f,\bm{x}_{0})\coloneqq\operatorname{cone}(\mathcal{D}(f,\bm{x}_{0}))$.

The notion of minimum conic singular values describes the behavior of a matrix
$\bm{A}$ when it is restricted to a cone $C\subseteq\mathbb{R}^{n}$.

######  Definition 2.2 (Minimum conic singular value)

Consider a matrix $\bm{A}\in\mathbb{R}^{m\times n}$ and a cone
$C\subseteq\mathbb{R}^{n}$. The minimum conic singular value of $\bm{A}$ with
respect to the cone $C$ is defined by

$\lambda_{\text{min}}\left(\bm{A};C\right)\coloneqq\inf_{\bm{x}\in
C\cap\mathcal{S}^{\smash{n-1}}}\left\|\bm{A}\bm{x}\right\|_{2}.$ (2.2)

The following result characterizes exact recoverability of the signal
$\bm{x}_{0}$ and provides a deterministic error bound for the solutions to
($\text{BP}_{\eta}^{\smash{f}}$). The statement is an adapted version of
Proposition 2.1 and Proposition 2.2 in [CRPW12]; see also Proposition 2.6 in
[Tro15].

######  Proposition 2.3 (A deterministic error bound for
($\text{BP}_{\eta}^{\smash{f}}$))

Assume that $\bm{x}_{0},\bm{A},\bm{y},\bm{e}$ and $\eta$ follow Model 1 and
let $f\colon\mathbb{R}^{n}\to\mathbb{R}$ be a convex function. Then the
following holds true:

  1. (a)

If $\eta=0$, exact recovery of $\bm{x}_{0}$ by solving
($\text{BP}_{\eta=0}^{\smash{f}}$) is equivalent to
$\lambda_{\text{min}}\left(\bm{A};\mathcal{D}_{\wedge}(f,\bm{x}_{0})\right)>0$.

  2. (b)

In addition, any solution $\hat{\bm{x}}$ of ($\text{BP}_{\eta}^{\smash{f}}$)
satisfies

$\left\|\bm{x}_{0}-\hat{\bm{x}}\right\|_{2}\leq\frac{2\eta}{\lambda_{\text{min}}\left(\bm{A};\mathcal{D}_{\wedge}(f,\bm{x}_{0})\right)}.$
(2.3)

###  2.2 Conic Mean Width

While Proposition 2.3 provides an elegant analysis of the solutions to the
optimization problem ($\text{BP}_{\eta}^{\smash{f}}$), it can be difficult to
apply. The notion of a minimum conic singular value is related to the concept
of co-positivity [HS10b] and its computation is known to be an NP-hard task
for general matrices and cones [MK87, HS10b].

However, when $\bm{A}$ is chosen at random, sharp estimates can be obtained by
exploring a connection to the _statistical dimension_ or _Gaussian mean
width_. These geometric parameters stem from geometric functional analysis and
convex geometry (e.g., see [Gor85, Gor88, GM04, Mil85]), but they also show up
in _Talagrand’s $\gamma_{2}$-functional_ in stochastic processes [Tal14], or
under the name of _Gaussian complexity_ in statistical learning theory [BM02].
Their benefits for compressive sensing have first been exploited in [RV07,
MPT07]. More important for our work is their use in the more recent line of
research [Sto09, CRPW12, ALMT14, Tro15], which aims for non-uniform signal
recovery statements.

###### Definition 2.4

Let $K\subseteq\mathbb{R}^{n}$ be a set.

  1. (a)

The _(global) mean width_ of $K$ is defined as

$w(K)\coloneqq\mathbb{E}\left[\sup_{\bm{h}\in
K}\langle\bm{g},\bm{h}\rangle\right],$ (2.4)

where $\bm{g}\sim\mathcal{N}(\bm{0},\bm{Id})$ is a standard Gaussian random
vector.

  2. (b)

The _conic mean width_ of $K$ is given by

$w_{\wedge}(K)\coloneqq w(\operatorname{cone}(K)\cap\mathcal{S}^{n-1}).$ (2.5)

We refer to $w_{\wedge}(\mathcal{D}(f,\bm{x}_{0}))$ as the _conic mean width_
of $f$ at $x_{0}$.

The next theorem is known as _Gordon’s Escape Through a Mesh_ and dates back
to [Gor88]. The version presented here follows from [LMPV17].

######  Theorem 2.5 (Theorem 3 in [LMPV17])

Assume that $\bm{A}$ satisfies the assumption in Model 1.1 and let
$K\subseteq\mathcal{S}^{\smash{n-1}}$ be a set. Then there exists a numerical
constant $c>0$ such that, for every $u>0$, we have

$\inf_{\bm{x}\in
K}\left\|\bm{A}\bm{x}\right\|_{2}>\sqrt{m-1}-c\cdot\gamma^{2}\cdot(w(K)+u),$
(2.6)

with probability at least $1-e^{-u^{2}/2}$. If
$\bm{a}\sim\mathcal{N}(\bm{0},\bm{Id})$, we have $c=\gamma=1$.

Thus, a straightforward combination the error bound in (2.3) and the estimate
in (2.6) for the set
$K=\mathcal{D}_{\wedge}(f,\bm{x}_{0})\cap\mathcal{S}^{\smash{n-1}}$ reveals
that robust recovery via ($\text{BP}_{\eta}^{\smash{f}}$) is possible if the
number of sub-Gaussian measurements obeys

$m\geq c^{2}\cdot\gamma^{4}\cdot w^{2}_{\wedge}(\mathcal{D}(f,\bm{x}_{0}))+1.$
(2.7)

In the case of Gaussian measurements, it is known that this bound yields a
tight description of the so-called _phase transition_ of
($\text{BP}_{\eta=0}^{\smash{f}}$). Indeed, for a convex cone
$C\subseteq\mathbb{R}^{n}$ it can be shown that
$\lambda_{\text{min}}\left(\bm{A};C\right)=0$ with high probability when
$m\leq w^{2}_{\wedge}(C)-c\cdot w_{\wedge}(C)$, where $c>0$ denotes a
numerical constant. Applying this statement to the descent cone
$\mathcal{D}_{\wedge}(f,\bm{x}_{0})$ reveals that exact recovery of
$\bm{x}_{0}$ by solving ($\text{BP}_{\eta=0}^{\smash{f}}$) fails with high
probability when

$m\leq w^{2}_{\wedge}(\mathcal{D}(f,\bm{x}_{0}))-c\cdot
w_{\wedge}(\mathcal{D}(f,\bm{x}_{0})).$ (2.8)

Hence, exact signal recovery by solving ($\text{BP}_{\eta=0}^{\smash{f}}$)
obeys a sharp phase transition at $m\approx
w^{2}_{\wedge}(\mathcal{D}(f,\bm{x}_{0}))$ Gaussian measurements. We refer to
[ALMT14] and [Tro15, Remark 3.4] for more details on this matter and conclude
our discussion by the following summary:

> Robust signal recovery via the generalized basis pursuit
> ($\text{BP}_{\eta}^{\smash{f}}$) is characterized by the minimum conic
> singular value
> $\lambda_{\text{min}}\left(\bm{A};\mathcal{D}_{\wedge}(f,\bm{x}_{0})\right)$.
> The required number of sub-Gaussian random measurements can be determined by
> the conic mean width of $f$ at $\bm{x}_{0}$, in symbols
> $w^{2}_{\wedge}(\mathcal{D}(f,\bm{x}_{0}))$.

##  3 Coefficient and Signal Recovery

Our study of the synthesis formulation in this section is based on the
differentiation between coefficient and signal recovery. First, we introduce
the set of minimal $\ell^{\smash{1}}$-representers in Section 3.1 and discuss
its importance for the relationship between both formulations. Section 3.2 is
then dedicated to the fact that signal recovery via
($\text{BP}_{\eta}^{\text{\smash{sig}}}$) can be cast as an instance of atomic
norm minimization, in which the gauge of the synthesis defining polytope is
minimized. Finally, in Section 3.3, we derive two non-uniform recovery
theorems that determine the sampling rates of robust coefficient and signal
recovery, respectively.

###  3.1 Recovery and Minimal $\ell^{1}$-Representers

In this section, we discuss how the uniqueness of a minimal
$\ell^{1}$-representer impacts coefficient and signal recovery.

######  Definition 3.1 (Minimal $\ell^{1}$-representers)

The set of _minimal $\ell^{1}$-representers_ of a signal $\bm{x}_{0}$ with
respect to a dictionary $\bm{D}$ is defined by

$Z_{\ell^{\smash{1}}}\coloneqq\operatorname*{argmin}_{\bm{z}\in\mathbb{R}^{d}}\left\|\bm{z}\right\|_{1}\quad\mbox{
s.t. }\quad\bm{x}_{0}=\bm{D}\bm{z}.$ ($\text{BP}_{\ell^{1}}$)

In general, $Z_{\ell^{\smash{1}}}$ may not be a singleton. Indeed, a
coefficient vector $\bm{z}_{\ell^{\smash{1}}}$ can only be the unique minimal
$\ell^{\smash{1}}$-representer of the associated signal
$\bm{x}_{0}=\bm{D}\bm{z}_{\ell^{\smash{1}}}$, if the set of atoms
$\\{\bm{d}_{i}:i\in\operatorname{supp}(\bm{z}_{\ell^{\smash{1}}})\\}$ is
linearly independent [FR13, Theorem 3.1]. However, many dictionaries of
practical interest possess linear dependent and coherent atoms. Hence, typical
notions that would certify uniqueness for all signals with sparse
representations in $\bm{D}$ (e.g., the NSP [FR13, Theorem 4.5]) are not
expected to hold for such dictionaries.

The following simple lemma shows that exact coefficient recovery by solving
($\text{BP}_{\smash{\eta=0}}^{\text{\smash{coef}}}$) requires
$Z_{\ell^{\smash{1}}}$ to be a singleton. Otherwise, it is impossible to
recover a specific coefficient representation, while a retrieval of the signal
by ($\text{BP}_{\smash{\eta=0}}^{\text{\smash{sig}}}$) might still be
possible.

###### Lemma 3.2

Assume that $\bm{x}_{0},\bm{A}$ and $\bm{y}$ follow Model 1 with $\eta=0$. Let
$\bm{D}\in\mathbb{R}^{n\times d}$ be a dictionary such that
$\bm{x}_{0}\in\operatorname{ran}(\bm{D})$.

  1. (a)

Assume that $\bm{x}_{0}=\bm{D}\bm{z}_{0}$ and that we wish to reconstruct
$\bm{z}_{0}$. If $Z_{\ell^{\smash{1}}}\neq\left\\{\bm{z}_{0}\right\\}$, then
recovering $\bm{z}_{0}$ by solving
($\text{BP}_{\smash{\eta=0}}^{\text{\smash{coef}}}$) is impossible.

  2. (b)

Signal recovery by solving
($\text{BP}_{\smash{\eta=0}}^{\text{\smash{sig}}}$), i.e., having
$\hat{X}=\left\\{\bm{x}_{0}\right\\}$, is equivalent to the condition
$Z_{\ell^{\smash{1}}}=\hat{Z}$.

A short proof of the previous result is given in Appendix A.1. Thus, under the
assumption that $\bm{x}_{0}$ has a unique minimal
$\ell^{\smash{1}}$-representer, exact coefficient recovery by
($\text{BP}_{\smash{\eta=0}}^{\text{\smash{coef}}}$) and signal recovery by
($\text{BP}_{\smash{\eta=0}}^{\text{\smash{sig}}}$) are equivalent.

###  3.2 Signal Recovery and the Convex Gauge

The literature on compressive sensing predominantly focuses on a recovery of
coefficient representations. However, if the goal is to recover the associated
signal, this approach may be insufficient for structured dictionaries, as
argued previously. In this section, we express the initial optimization
problem over the coefficient domain ($\text{BP}_{\eta}^{\text{\smash{sig}}}$)
as a minimization problem over the signal space. The $\ell^{\smash{1}}$-ball
$\text{B}_{1}^{\smash{d}}$ in the coefficient domain is thereby mapped to the
convex body $\bm{D}\cdot\text{B}_{1}^{\smash{d}}$, which is referred to as
_synthesis defining polytope_ in [EMR07]. The formulation
($\text{BP}_{\eta}^{\text{\smash{sig}}}$) can be equivalently expressed as a
constrained minimization of its corresponding _convex gauge_.

######  Definition 3.3 (Convex gauge)

Let $K\subseteq\mathbb{R}^{n}$ be a closed convex set that contains the
origin. The _gauge_ of $K$ (also referred to as _Minkowski functional_) is
defined as

$p_{K}(\bm{x})\coloneqq\inf\left\\{\lambda>0:\bm{x}\in\lambda\cdot
K\right\\}.$

For a symmetric set (i.e., $-K=K$) the gauge defines a semi-norm on
$\mathbb{R}^{n}$, which becomes a norm if $K$ is additionally bounded.

The following lemma provides an alternative characterization of the solutions
$\hat{X}$ to ($\text{BP}_{\eta}^{\text{\smash{sig}}}$).

###### Lemma 3.4

Assume that $\bm{x}_{0},\bm{A},\bm{y},\bm{e}$ and $\eta$ follow Model 1 and
let $\bm{D}\in\mathbb{R}^{n\times d}$ be a dictionary. Then we have:

$\hat{X}=\operatorname*{argmin}_{\bm{x}\in\mathbb{R}^{n}}p_{\bm{D}\cdot\text{B}_{1}^{\smash{d}}}(\bm{x})\quad\mbox{
s.t. }\quad\left\|\bm{y}-\bm{A}\bm{x}\right\|_{2}\leq\eta.$ (3.1)

A short proof for his equivalence is given in Appendix A.2. Under the heading
of _atomic norm minimization_ , problems of the form (3.1) were previously
considered in greater generality in [CRPW12]: Given a collection of atoms
$\mathcal{A}\subseteq\mathbb{R}^{n}$, Chandrasekaran et al. study the geometry
of signal recovery based on minimizing the associated gauge
$p_{\operatorname{conv}(\mathcal{A})}$ in (3.1). It turns out that many
popular methods such as classical $\ell^{\smash{1}}$-, or nuclear norm-
minimization can be cast in such a form, e.g., by choosing $\mathcal{A}$ as
the set of one-sparse unit-norm vectors, or the set of rank-one matrices with
unit-Euclidean-norm. Note that in the considered case of signal recovery via
($\text{BP}_{\eta}^{\text{\smash{sig}}}$), one would choose the atoms
$\mathcal{A}=\left\\{\pm\bm{d}_{i}:i\in[d]\right\\}$ to obtain
$\operatorname{conv}(\mathcal{A})=\bm{D}\cdot\text{B}_{1}^{\smash{d}}$. With
this reformulation it is evident that dictionary atoms that are convex
combinations of the remaining atoms in $\mathcal{A}$ can be removed without
altering $\hat{X}$ [EMR07, Corollary 1].

For some specific problem instances novel sampling rate bounds are derived in
[CRPW12]. Although this work plays a key role for the foundation of our work,
we wish to emphasize that no explicit insights or bounds are derived in the
case of signal recovery with dictionaries. In particular, the connection
between ($\text{BP}_{\eta}^{\text{\smash{sig}}}$) and
($\text{BP}_{\eta}^{\text{\smash{coef}}}$) has not been studied.

With regard to the recovery framework of Section 2.1, it is of interest to
determine the descent cone of the functional
$p_{\bm{D}\cdot\text{B}_{1}^{\smash{d}}}$ at $\bm{x}_{0}$. The following lemma
shows how this cone is related to descent cones of the $\ell^{\smash{1}}$-norm
in the coefficient space.

###### Lemma 3.5

Let $\bm{D}\in\mathbb{R}^{n\times d}$ be a dictionary and let
$\bm{x}_{0}\in\operatorname{ran}(\bm{D})$. For any
$\bm{z}_{\ell^{\smash{1}}}\in Z_{\ell^{\smash{1}}}$ we have

$\mathcal{D}_{\wedge}(p_{\bm{D}\cdot\text{B}_{1}^{\smash{d}}},\bm{x}_{0})=\bm{D}\cdot\mathcal{D}_{\wedge}(\left\|\cdot\right\|_{1},\bm{z}_{\ell^{\smash{1}}})\quad\mbox{
and
}\quad\mathcal{D}(p_{\bm{D}\cdot\text{B}_{1}^{\smash{d}}},\bm{x}_{0})=\bm{D}\cdot\mathcal{D}(\left\|\cdot\right\|_{1},\bm{z}_{\ell^{\smash{1}}}).$

The proof is given in Appendix A.3.

###  3.3 Sampling Rates for Signal and Coefficient Recovery

The purpose of this section is to determine the sampling rates for robust
coefficient and signal recovery from sub-Gaussian measurements.

##### Coefficient recovery

With Lemma 3.2 in mind, studying coefficient recovery is meaningful only if
the signal $\bm{x}_{0}$ has a unique minimal $\ell^{1}$-representer
$\bm{z}_{\ell^{\smash{1}}}$ with respect to $\bm{D}$. Proposition 2.3 implies
that this condition can be equivalently expressed by

$\lambda_{\text{min}}\left(\bm{D};\mathcal{D}_{\wedge}(\left\|\cdot\right\|_{1},\bm{z}_{\ell^{\smash{1}}})\right)>0.$
(3.2)

Equipped with this assumption, we now state our main theorem regarding the
recovery of coefficient vectors via
($\text{BP}_{\eta}^{\text{\smash{coef}}}$).

######  Theorem 3.6 (Coefficient recovery)

Assume that $\bm{x}_{0},\bm{A},\bm{y},\bm{e}$ and $\eta$ follow Model 1, where
$\bm{A}$ is drawn according to the sub-Gaussian Model 1.1 with sub-Gaussian
norm $\gamma$. Let $\bm{D}\in\mathbb{R}^{n\times d}$ be a dictionary and
$\bm{z}_{\ell^{\smash{1}}}\in\mathbb{R}^{d}$ be a coefficient vector for the
signal $\bm{x}_{0}=\bm{D}\bm{z}_{\ell^{\smash{1}}}\in\mathbb{R}^{n}$, such
that

$\lambda_{\text{min}}\left(\bm{D};\mathcal{D}_{\wedge}(\left\|\cdot\right\|_{1},\bm{z}_{\ell^{\smash{1}}})\right)>0.$

Then there exists a numerical constant $c>0$ such that for every $u>0$, the
following holds true with probability at least $1-\text{e}^{-u^{2}/2}$: If the
number of measurements obeys

$m>m_{0}\coloneqq
c^{2}\cdot\gamma^{4}\cdot\left(w_{\wedge}(\bm{D}\cdot\mathcal{D}(\left\|\cdot\right\|_{1};\bm{z}_{\ell^{\smash{1}}}))+u\right)^{2}+1,$
(3.3)

then any solution $\hat{\bm{z}}$ to the program
($\text{BP}_{\eta}^{\text{\smash{coef}}}$) satisfies

$\left\|\bm{z}_{\ell^{\smash{1}}}-\hat{\bm{z}}\right\|_{2}\leq\frac{2\eta}{\lambda_{\text{min}}\left(\bm{D};\mathcal{D}_{\wedge}(\left\|\cdot\right\|_{1};\bm{z}_{\ell^{\smash{1}}})\right)\cdot(\sqrt{m-1}-\sqrt{m_{0}-1})}.$
(3.4)

If $\bm{a}\sim\mathcal{N}(\bm{0},\bm{Id})$, then $c=\gamma=1$.

A proof is given in Appendix A.4. Before turning towards signal recovery, let
us highlight a few observations regarding the previous theorem.

###### Remark 3.7

  1. (a)

Note that Theorem 3.6 does not assume anything on the dictionary $\bm{D}$ and
the coefficient representation $\bm{z}_{\ell^{\smash{1}}}$, except for
$\lambda_{\text{min}}\left(\bm{D};\mathcal{D}_{\wedge}(\left\|\cdot\right\|_{1},\bm{z}_{\ell^{\smash{1}}})\right)>0$,
which is a necessary condition for the theorem to hold true. As pointed out
above, it reflects that $\bm{z}_{\ell^{\smash{1}}}$ is a unique
$\ell^{\smash{1}}$-representer of $\bm{x}_{0}$ with respect to $\bm{D}$, i.e.,
that $\bm{z}_{\ell^{\smash{1}}}$ is the unique solution to
($\text{BP}_{\ell^{1}}$). In general, verifying this property is involved (cf.
the discussion in Section 2.2) and forms a trail of research on its own, e.g.,
see [Mal09, Chapter 12] or [CK13, Chapter 9]. In this regard, we think that an
important contribution of Theorem 3.6 is that it allows to isolate the minimum
prerequisite of a unique $\ell^{\smash{1}}$-representer in $\bm{D}$ from the
actual task of compressive coefficient recovery.

  2. (b)

Equation (3.3) identifies
$w^{2}_{\wedge}(\bm{D}\cdot\mathcal{D}(\left\|\cdot\right\|_{1};\bm{z}_{\ell^{\smash{1}}}))$
as the essential component of the sampling rate for coefficient recovery by
($\text{BP}_{\eta}^{\text{\smash{coef}}}$). Indeed, the proof reveals (in
combination with the discussion subsequent to Theorem 2.5) that $m_{0}$ is a
tight description of the required number of noiseless Gaussian measurements
for exact recovery.

  3. (c)

Lastly, the error bound (3.4) shows that coefficient recovery is robust to
measurement noise, provided that
$\lambda_{\text{min}}\left(\bm{D};\mathcal{D}_{\wedge}(\left\|\cdot\right\|_{1},\bm{z}_{\ell^{\smash{1}}})\right)\gg
0$; cf. the numerical experiments in Section 5, which confirm this
observation. However, we note that this bound might not be tight, in general
(cf. the intermediate inequality (A.5) in the proof, which is not necessarily
sharp).

##### Signal recovery

Considering signal recovery by ($\text{BP}_{\eta}^{\text{\smash{sig}}}$), a
combination of the gauge formulation (3.1), its description of the descent
cone in Lemma 3.5, and Theorem 2.5 directly yields the next result.

######  Theorem 3.8 (Signal recovery)

Assume that $\bm{x}_{0},\bm{A},\bm{y},\bm{e}$ and $\eta$ follow the
measurement Model 1, where $\bm{A}$ is drawn according to the sub-Gaussian
Model 1.1 with sub-Gaussian norm $\gamma$. Let $\bm{D}\in\mathbb{R}^{n\times
d}$ be a dictionary with $\bm{x}_{0}\in\operatorname{ran}(\bm{D})$ and pick
any $\bm{z}_{\ell^{\smash{1}}}\in Z_{\ell^{\smash{1}}}$.

Then there exists a numerical constant $c>0$ such that for every $u>0$, the
following holds true with probability at least $1-\text{e}^{-u^{2}/2}:$ If the
number of measurements obeys

$m>m_{0}\coloneqq
c^{2}\cdot\gamma^{4}\cdot\left(w_{\wedge}(\bm{D}\cdot\mathcal{D}(\left\|\cdot\right\|_{1};\bm{z}_{\ell^{\smash{1}}}))+u\right)^{2}+1,$
(3.5)

then any solution $\hat{\bm{x}}$ to the program
($\text{BP}_{\eta}^{\text{\smash{sig}}}$) satisfies

$\left\|\bm{x}_{0}-\hat{\bm{x}}\right\|_{2}\leq\frac{2\eta}{\sqrt{m-1}-\sqrt{m_{0}-1}}.$
(3.6)

If $\bm{a}\sim\mathcal{N}(\bm{0},\bm{Id})$, then $c=\gamma=1$.

Let us discuss the previous result in view of its counterpart for coefficient
recovery, Theorem 3.6.

###### Remark 3.9

  1. (a)

Similarly as for coefficient recovery, (3.5) identifies
$w^{2}_{\wedge}(\bm{D}\cdot\mathcal{D}(\left\|\cdot\right\|_{1};\bm{z}_{\ell^{\smash{1}}}))$
as the main quantity of the sampling rate for signal recovery by
($\text{BP}_{\eta}^{\text{\smash{sig}}}$). An important difference is that the
set minimal of $\ell^{\smash{1}}$-representers is not required to be a
singleton: The descent cone in the signal space may be evaluated at any
possible $\bm{z}_{\ell^{\smash{1}}}\in Z_{\ell^{\smash{1}}}$ and the resulting
sampling rate for signal recovery does not depend on this choice.

  2. (b)

In the case of noiseless Gaussian measurements, the number $m_{0}$ is a tight
description of the phase transition of signal recovery, cf. the discussion
subsequent to Theorem 2.5.

  3. (c)

While the sampling rates for coefficient and signal recovery are similar, the
error bounds of the two theorems differ. The inequality (3.6) does not involve
the minimal conic singular value as in Theorem 3.6. This suggests the
following noteworthy consequence: In the case of simultaneous coefficient and
signal recovery, the robustness to noise of
($\text{BP}_{\eta}^{\text{\smash{coef}}}$) and
($\text{BP}_{\eta}^{\text{\smash{sig}}}$) might still be different. Indeed,
while a reconstruction of $\bm{x}_{0}$ is independent of the value of
$\lambda_{\text{min}}\left(\bm{D};\mathcal{D}_{\wedge}(\left\|\cdot\right\|_{1},\bm{z}_{\ell^{\smash{1}}})\right)$
– in fact, even 0 is allowed–, the error with respect to
$\bm{z}_{\ell^{\smash{1}}}$ is directly influenced by it. We emphasize that
the bound (3.6) cannot be retrieved from the analysis conducted for
coefficient recovery. Indeed, the estimate (3.4) of Theorem 3.6 only implies
that

$\left\|\bm{x}_{0}-\hat{\bm{x}}\right\|_{2}=\left\|\bm{D}(\bm{z}_{\ell^{\smash{1}}}-\hat{\bm{z}})\right\|_{2}\leq\frac{\|\bm{D}\|_{2}}{\lambda_{\text{min}}\left(\bm{D};\mathcal{D}_{\wedge}(\left\|\cdot\right\|_{1},\bm{z}_{\ell^{\smash{1}}})\right)}\cdot\frac{2\eta}{\sqrt{m-1}-\sqrt{m_{0}-1}},$
(3.7)

which is worse than (3.6), in general.

While the bound (3.5) is accurate for an exact recovery from noiseless
measurements, it can be improved when an approximate recovery of $\bm{x}_{0}$
is already sufficient. This is reflected by the following proposition on
_stable recovery_ , which is an adaptation of a result in [GKM20]; see
Appendix A.5 for a proof. Note that such an argumentation does not allow for a
similar statement about stable coefficient recovery, due to the product
$\bm{A}\bm{D}$ in ($\text{BP}_{\eta}^{\text{\smash{coef}}}$).

######  Proposition 3.10 (Stable signal recovery)

Assume that $\bm{x}_{0},\bm{A},\bm{y},\bm{e}$ and $\eta$ follow the
measurement Model 1, where $\bm{A}$ is drawn according to the sub-Gaussian
Model 1.1 with sub-Gaussian norm $\gamma$. Let $\bm{D}\in\mathbb{R}^{n\times
d}$ be a dictionary with $\bm{x}_{0}=\bm{D}\bm{z}_{0}$. For a desired
precision $\varepsilon>0$ let

$\bm{z}^{\ast}\in\operatorname*{argmin}_{\begin{subarray}{c}\bm{z}:\left\|\bm{x}_{0}-\bm{D}\bm{z}\right\|_{2}\leq\varepsilon\\\
\left\|\bm{z}_{0}\right\|_{1}=\left\|\bm{z}\right\|_{1}\end{subarray}}w_{\wedge}(\bm{D}\cdot\mathcal{D}(\left\|\cdot\right\|_{1};\bm{z})).$
(3.8)

Then there exists a numerical constant $c>0$ such that for every $r>0$ and
$u>0$ the following holds true with probability at least
$1-\text{e}^{-u^{2}/2}$: If the number of measurements obeys

$m>\tilde{m}_{0}\coloneqq
c^{2}\cdot\gamma^{4}\cdot\left(\frac{r+1}{r}\cdot[w_{\wedge}(\bm{D}\cdot\mathcal{D}(\left\|\cdot\right\|_{1};\bm{z}^{\ast}))+1]+u\right)^{2}+1,$
(3.9)

then any solution $\hat{\bm{x}}$ to ($\text{BP}_{\eta}^{\text{\smash{sig}}}$)
satisfies

$\left\|\bm{x}_{0}-\hat{\bm{x}}\right\|_{2}\leq\max\left(r\varepsilon,\frac{2\eta}{\sqrt{m-1}-\sqrt{\tilde{m}_{0}-1}}\right).$
(3.10)

If $\bm{a}\sim\mathcal{N}(\bm{0},\bm{Id})$, then $c=\gamma=1$.

The previous result extends Theorem 3.8 by an intuitive trade-off regarding
stable signal recovery: By allowing for a lower recovery precision
$\varepsilon>0$, the number of required measurements $\tilde{m}_{0}$ can be
significantly lowered in comparison to $m_{0}$ in (3.5). Indeed, (3.8)
searches for surrogate representations $\bm{z}^{\ast}$ of $\bm{x}_{0}$ in
$\bm{D}$ that yield a minimal sampling rate. Note that the original
coefficient vector $\bm{z}_{0}$ is not required to be a minimal
$\ell^{1}$-representer of $\bm{x}_{0}$ with respect to $\bm{D}$. Thus,
Proposition 3.10 enables to trade off the required number of measurements
against the desired recovery accuracy. The factor $r>0$ is an additional
oversampling parameter that may assist in balancing out this trade-off.

We emphasize that this approach to stability is centered around a Euclidean
approximation in the signal domain $\mathbb{R}^{n}$. This is in stark contrast
to a stability theory in the coefficient domain, which is typically based on
an approximation of compressible vectors by ordinary _best $s$-term
approximations_. We refer to Section 2.4 and 6.1 in [GKM20] as well as Section
2.4 in [GMS20] for more details on the presented approach to stable recovery
and related results in the literature.

###### Remark 3.11

The normalization condition
$\left\|\bm{z}_{0}\right\|_{1}=\left\|\bm{z}\right\|_{1}$ in (3.8) can be
discarded at the expense of a slightly worse error bound. Under the same
conditions as in Proposition 3.10, we can also derive the following result.
Set $\varepsilon>0$ and let

$\bm{x}^{\ast}\in\mathop{\mathrm{argmin}}_{\|\bm{x}-\bm{x}_{0}\|_{2}\leq\varepsilon}w_{\wedge}(\mathcal{D}(p_{\bm{D}\cdot\text{B}_{1}^{\smash{d}}};\bm{x}))\quad\mbox{
and }\quad
K=\mathcal{D}(p_{\bm{D}\cdot\text{B}_{1}^{\smash{d}}},\bm{x}^{\ast}).$

For every $u>0$ and

$m>\tilde{m}_{0}:=c^{2}\cdot\gamma^{4}\cdot(w_{\wedge}(K)+u)^{2}+1,$

the inequality

$\|\bm{x}_{0}-\hat{\bm{x}}\|_{2}\leq\frac{4(\eta+\varepsilon(\sqrt{m}+C\gamma^{2}+u))}{\sqrt{m-1}-\sqrt{\tilde{m}_{0}-1}}+\varepsilon$
(3.11)

holds true with probability larger than $1-2\text{e}^{-u^{2}}$ for some
constant $C$ depending only on the distribution of $\bm{A}$. For instance,
letting $m=r\tilde{m}_{0}$ with $r>1$ as an oversampling factor, the latter
bound essentially becomes:

$\|\bm{x}_{0}-\hat{\bm{x}}\|_{2}\lesssim\frac{4\eta}{(\sqrt{r}-1)\tilde{m}_{0}}+\frac{4\varepsilon\sqrt{r}}{(\sqrt{r}-1)}+\varepsilon.$

We conclude this section by an illustration of stable recovery in two simple
examples.

###### Example 3.12

  1. (a)

Assume that $\bm{D}=\operatorname{\textbf{Id}}$ and let
$\bm{x}_{0}\in\mathbb{R}^{n}$ denote a fully populated vector, which is
without loss of generality assumed to be positive and nonincreasing. Standard
results on the computation of the conic mean width (see for instance [Tro15,
Example 4.3]) stipulate that
$w^{2}_{\wedge}(\mathcal{D}(\left\|\cdot\right\|_{1};\bm{x}_{0}))=n$. Hence,
it is impossible to exactly recover $\bm{x}_{0}$ from noiseless compressive
measurements. However, if we are satisfied with an approximate recovery of
$\bm{x}_{0}$, we can set the precision for instance to
$\varepsilon=3\cdot\sigma_{s}(\bm{x}_{0})_{1}/\sqrt{s}$, where
$\sigma_{s}(\bm{x}_{0})_{p}$ denotes the $\ell^{p}$-error of the best $s$-term
approximation to $\bm{x}_{0}$. Then, the surrogate vector
$\bm{x}^{\ast}\in\mathbb{R}^{n}$ defined as $x^{\ast}_{i}\coloneqq
x_{0,i}+\sigma_{s}(\bm{x}_{0})_{1}/s$ for $i=1,\dots,s$ and
$x^{\ast}_{i}\coloneqq 0$ for $i=s+1,\dots,n$, satisfies
$\left\|\bm{x}^{\ast}\right\|_{1}=\left\|\bm{x}_{0}\right\|_{1}$. A
straightforward calculation shows that
$\left\|\bm{x}^{\ast}-\bm{x}_{0}\right\|_{2}^{2}\leq\sigma_{s}(\bm{x}_{0})_{1}^{2}/s+\sigma_{s}(\bm{x}_{0})_{2}^{2}$,
which eventually leads to $\left\|\bm{x}^{\ast}-\bm{x}_{0}\right\|_{2}\leq
3\cdot\sigma_{s}(\bm{x}_{0})_{1}/\sqrt{s}$. Furthermore, a computation of the
conic mean width yields that
$w^{2}_{\wedge}(\mathcal{D}(\left\|\cdot\right\|_{1};\bm{x}^{\ast}))\lesssim
2s\log(n/s)$. Hence, Proposition 3.10 shows that
($\text{BP}_{\smash{\eta=0}}^{\text{\smash{sig}}}$) allows for the
reconstruction of an approximation $\hat{\bm{x}}$ from $m\gtrsim 2s\log(n/s)$
noiseless sub-Gaussian measurements that satisfies
$\left\|\bm{x}_{0}-\hat{\bm{x}}\right\|_{2}\lesssim
3\cdot\sigma_{s}(\bm{x}_{0})_{1}/\sqrt{s}$. A comparison with [FR13, Theorem
4.22 and Section 11.1] shows that such a stability result is essentially
optimal.

  2. (b)

Let us provide another simple result highlighting the important difference
between signal and coefficient recovery. Consider a dictionary consisting of a
convolution with a low pass filter $\bm{h}\in\mathbb{R}^{n}$, i.e., for any
$\bm{z}\in\mathbb{R}^{d}$, $\bm{D}\bm{z}=\bm{h}\star\bm{z}$. The problem
($\text{BP}_{\eta}^{\text{\smash{sig}}}$) then becomes a _deconvolution_
problem and it could be turned to a super-resolution problem by considering
non integer shifts of the kernel. In this setting, it is well known [CF14]
that coefficients of the form $\bm{z}_{0}=[1,-1,0,\ldots,0]$ are hard to
recover by solving ($\text{BP}_{\eta}^{\text{\smash{coef}}}$) since
$\bm{h}\star\bm{z}_{0}\simeq 0$. There is a minimum separation distance to
respect to guarantee the recovery of sparse spikes with arbitrary signs. We
can however use the result (3.11) by setting
$\varepsilon=\|\bm{D}\bm{z}_{0}\|_{2}$. In that case, we obtain
$\tilde{m}_{0}=c^{2}\gamma^{4}u^{2}+1$ by picking $\bm{x}^{\star}=0$. Hence,
we can recover an $\varepsilon$-approximation of $\bm{x}_{0}=\bm{D}\bm{z}_{0}$
with a few measurements.

##  4 Upper Bounds on the Conic Gaussian Width

The previous results identify the conic mean width
$w^{2}_{\wedge}(\bm{D}\cdot\mathcal{D}(\left\|\cdot\right\|_{1};\bm{z}_{\ell^{\smash{1}}}))$
as the key quantity that controls coefficient and signal recovery by
$\ell^{\smash{1}}$-synthesis. However, this expression does not convey an
immediate understanding without further simplification. While tight and
informative upper bounds are available for simple dictionaries such as
orthogonal matrices, the situation becomes significantly more involved for
general, possibly redundant transforms. Indeed, note that the polar cone of
$\bm{D}\cdot\mathcal{D}(\left\|\cdot\right\|_{1};\bm{z}_{\ell^{\smash{1}}})$
is given by
$(\bm{D}\cdot\mathcal{D}(\left\|\cdot\right\|_{1};\bm{z}_{\ell^{\smash{1}}}))^{\circ}=(\bm{D}^{T})^{-1}(\mathcal{D}(\left\|\cdot\right\|_{1};\bm{z}_{\ell^{\smash{1}}})^{\circ})$.
The appearance of the preimage $(\bm{D}^{T})^{-1}$ hinders the application of
the standard approach based on polarity; see for instance [ALMT14, Recipe
4.1].

Hence, the goal of this section is to provide two upper bounds for
$w^{2}_{\wedge}(\bm{D}\cdot\mathcal{D}(\left\|\cdot\right\|_{1};\bm{z}_{\ell^{\smash{1}}}))$
that are more accessible and intuitive: Section 4.1 is based on a local
conditioning argument, and addresses recovery when a unique minimal
$\ell^{\smash{1}}$-representer exists. The second bound of Section 4.2 follows
a geometric analysis that explores the thinness of high-dimensional polyhedral
cones with not too many generators. This approach possesses a broader scope
and plays a central role in our work.

###  4.1 A Condition Number Bound

In this section, we aim at “pulling” the dictionary $\bm{D}$ “out of” the
expression
$w^{2}_{\wedge}(\bm{D}\cdot\mathcal{D}(\left\|\cdot\right\|_{1};\bm{z}_{\ell^{\smash{1}}}))$,
in order to make use of the fact that
$w^{2}_{\wedge}(\mathcal{D}(\left\|\cdot\right\|_{1};\bm{z}_{\ell^{\smash{1}}}))$
is well understood. We begin by introducing the following notation of a local
condition number.

######  Definition 4.1 (Local condition number)

Let $\bm{D}\in\mathbb{R}^{n\times d}$ be a dictionary and let
$C\subseteq\mathbb{R}^{d}$ be closed convex cone. Then, we define the _local
condition number of $\bm{D}$ with respect to $C$_ by

$\kappa_{{\bm{D},C}}\coloneqq\frac{\left\|\bm{D}\right\|_{2}}{\lambda_{\text{min}}\left(\bm{D};C\right)},$
(4.1)

with the convention $\kappa_{{\bm{D},C}}=+\infty$ if
$\lambda_{\text{min}}\left(\bm{D};C\right)=0$. We also use the notation
$\kappa_{{\bm{D},\bm{z}_{0}}}\coloneqq\kappa_{{\bm{D},\mathcal{D}_{\wedge}(\left\|\cdot\right\|_{1};\bm{z}_{0})}}$,
which we refer to as _local condition number of $\bm{D}$ at $\bm{z}_{0}$ with
respect to the $\ell^{\smash{1}}$-norm_.

Before the previous quantity will be used to simplify
$w^{2}_{\wedge}(\bm{D}\cdot\mathcal{D}(\left\|\cdot\right\|_{1};\bm{z}_{\ell^{\smash{1}}}))$,
we first comment on the origin of its name and give an intuitive
interpretation of its meaning in the following remark.

###### Remark 4.2

  1. (a)

First, recall that the classical, generalized condition number of a matrix is
defined as the ratio of the largest and the smallest nonzero singular value.
Hence, referring to $\kappa_{{\bm{D},C}}$ as a local condition number is
motivated by the fact that it can also be written as

$\kappa_{{\bm{D},C}}=\frac{\left\|\bm{D}\right\|_{2}}{\lambda_{\text{min}}\left(\bm{D};C\right)}=\frac{\lambda_{\text{max}}\left(\bm{D};\mathbb{R}^{d}\right)}{\lambda_{\text{min}}\left(\bm{D};C\right)},$
(4.2)

where
$\lambda_{\text{max}}\left(\bm{D};\mathbb{R}^{d}\right)\coloneqq\max_{\bm{z}\in\mathbb{R}^{d}\cap\mathcal{S}^{\smash{d-1}}}\left\|\bm{D}\bm{z}\right\|_{2}=\left\|\bm{D}\right\|_{2}$
is the largest singular value of $\bm{D}$.

  2. (b)

Furthermore, note that $\kappa_{{\bm{D},\bm{z}_{0}}}$ acts as a local measure
for the conditioning of $\bm{D}$ at $\bm{z}_{0}$ with respect to the
$\ell^{\smash{1}}$-norm. It quantifies how robustly $\bm{z}_{0}$ can be
recovered as the minimal $\ell^{\smash{1}}$-representer of
$\bm{x}_{0}=\bm{D}\bm{z}_{0}$: Consider the perturbation
$\widehat{\bm{z}_{0}}=\bm{z}_{0}+\hat{\bm{e}}$, where
$\hat{\bm{e}}\in\mathbb{R}^{d}$ with
$\left\|\hat{\bm{e}}\right\|_{2}\leq\hat{\eta}$. Thus, in the signal domain we
obtain
$\left\|\bm{D}\bm{z}_{0}-\bm{D}\cdot\widehat{\bm{z}_{0}}\right\|_{2}=\left\|\bm{D}\hat{\bm{e}}\right\|_{2}\leq\left\|\bm{D}\right\|_{2}\cdot\hat{\eta}$.
Proposition 2.3 then yields that any solution $\hat{\bm{z}}$ of the program

$\min_{z\in\mathbb{R}^{d}}\left\|\bm{z}\right\|_{1}\quad\mbox{ s.t.
}\quad\left\|\bm{D}\widehat{\bm{z}_{0}}-\bm{D}\bm{z}\right\|_{2}\leq\left\|\bm{D}\right\|_{2}\cdot\hat{\eta}$
(4.3)

satisfies

$\left\|\bm{z}_{0}-\hat{\bm{z}}\right\|_{2}\leq\frac{2\cdot\left\|\bm{D}\right\|_{2}\cdot\hat{\eta}}{\lambda_{\text{min}}\left(\bm{D};\mathcal{D}_{\wedge}(\left\|\cdot\right\|_{1};\bm{z}_{0})\right)}\lesssim\kappa_{{\bm{D},\bm{z}_{0}}}\cdot\hat{\eta},$
(4.4)

which shows that $\kappa_{{\bm{D},\bm{z}_{0}}}$ can be seen as a measure for
the stability of $\bm{z}_{0}$ with respect to $\ell^{1}$-minimization with
$\bm{D}$.

The following proposition provides a generic upper bound for the conic mean
width of a linearly transformed cone.

###### Proposition 4.3

Let $C\subseteq\mathbb{R}^{d}$ denote a closed convex cone. For any dictionary
$\bm{D}\in\mathbb{R}^{n\times d}$, we have

$w^{2}_{\wedge}(\bm{D}\cdot
C)\leq\kappa^{2}_{{\bm{D},C}}\cdot\left(w^{2}_{\wedge}(C)+1\right).$ (4.5)

###### Proof.

See Appendix B. ∎

Note that for sparse coefficient vectors $\bm{z}_{0}$ the quantity
$w^{2}_{\wedge}(\mathcal{D}(\left\|\cdot\right\|_{1};\bm{z}_{0}))$ is well
understood and has been frequently calculated in the literature, see for
instance [Tro15, Example 4.3]. It turns out that it can be bounded from above
by

$w^{2}_{\wedge}(\mathcal{D}(\left\|\cdot\right\|_{1};\bm{z}_{0}))\leq
2s\log(d/s)+2s,$ (4.6)

where $s=\\#\operatorname{supp}(\bm{z}_{0})$. Hence, we directly obtain the
following corollary.

###### Corollary 4.4

If $\bm{z}_{\ell^{\smash{1}}}$ is the unique minimal $\ell^{1}$-representer of
the associated signal $\bm{x}_{0}=\bm{D}\bm{z}_{\ell^{\smash{1}}}$, the
critical number of measurements $m_{0}$ in (3.3) and (3.5) satisfies

$m_{0}\leq
c^{2}\cdot\gamma^{4}\cdot\left(\kappa_{{\bm{D},\bm{z}_{\ell^{\smash{1}}}}}\cdot\left(w^{2}_{\wedge}(\mathcal{D}(\left\|\cdot\right\|_{1};\bm{z}_{\ell^{\smash{1}}}))+1\right)^{1/2}+u\right)^{2}+1\lesssim\kappa^{2}_{{\bm{D},\bm{z}_{\ell^{\smash{1}}}}}\cdot
s\log(d/s),$ (4.7)

where $s=\\#\operatorname{supp}(\bm{z}_{\ell^{\smash{1}}})$.

We have assumed $\bm{z}_{\ell^{\smash{1}}}$ to be a unique minimal
$\ell^{1}$-representer since otherwise the previous statement becomes
meaningless due to $\kappa_{{\bm{D},\bm{z}_{\ell^{\smash{1}}}}}=+\infty$.
Thus, the condition number bound of Corollary 4.4 foremost addresses
coefficient recovery via ($\text{BP}_{\eta}^{\text{\smash{coef}}}$), as well
as a reconstruction of signals with unique minimal
$\ell^{\smash{1}}$-representers in $\bm{D}$ by
($\text{BP}_{\eta}^{\text{\smash{sig}}}$). In both cases,
$m\gtrsim\kappa^{2}_{{\bm{D},\bm{z}_{\ell^{\smash{1}}}}}\cdot s\log(d/s)$ sub-
Gaussian measurements are sufficient (recall that the two formulations might
nevertheless differ with respect to robustness to measurement noise). Hence,
the results of this section identify the following three decisive factors for
successful recovery:

  1. (i)

The uniqueness of $\bm{z}_{\ell^{\smash{1}}}$ as the minimal
$\ell^{1}$-representer of $\bm{x}_{0}=\bm{D}\bm{z}_{\ell^{\smash{1}}}$;

  2. (ii)

The complexity of $\bm{z}_{\ell^{\smash{1}}}$ with respect to $\ell^{1}$-norm,
which is measured by
$w^{2}_{\wedge}(\mathcal{D}(\left\|\cdot\right\|_{1};\bm{z}_{\ell^{\smash{1}}}))$,
or by its sparsity $s=\\#\operatorname{supp}(\bm{z}_{\ell^{\smash{1}}})$;

  3. (iii)

The quantity $\kappa_{{\bm{D},\bm{z}_{\ell^{\smash{1}}}}}$, which resembles a
local measure for the conditioning of $\bm{D}$ at $\bm{z}_{\ell^{\smash{1}}}$.

We demonstrate in the numerical experiments of Section 5.1 that such a
condition number approach might be accurate for some specific problems,
however, it is overly pessimistic in general. Indeed, it is possible that
$w^{2}_{\wedge}(\bm{D}\cdot\mathcal{D}(\left\|\cdot\right\|_{1};\bm{z}_{\ell^{\smash{1}}}))\leq
w^{2}_{\wedge}(\mathcal{D}(\left\|\cdot\right\|_{1};\bm{z}_{\ell^{\smash{1}}}))$,
but $\kappa_{{\bm{D},\bm{z}_{\ell^{\smash{1}}}}}\gg 1$. We suspect that a more
accurate description might require a detailed analysis of random conic spectra
[ST03].

###### Remark 4.5

  1. (a)

In the case $\bm{D}=\operatorname{\textbf{Id}}$, observe that Corollary 4.4 is
consistent with standard compressed sensing results. Indeed, in this
situation, it holds true that

$\kappa_{{\operatorname{\textbf{Id}},\bm{z}_{\ell^{\smash{1}}}}}=1=\left\|\operatorname{\textbf{Id}}\right\|_{2}=\lambda_{\text{min}}\left(\operatorname{\textbf{Id}};\mathcal{D}_{\wedge}(\left\|\cdot\right\|_{1},\bm{z}_{\ell^{\smash{1}}})\right),$
(4.8)

implying that $m\gtrsim s\log(n/s)$ measurements are sufficient for robust
recovery of $s$-sparse signals.

  2. (b)

During completion of this work, we discovered that similar bounds as (4.5)
were recently derived in [ALW20]. Amelunxen et al. do not address the
synthesis formulation of compressed sensing, but they study the statistical
dimension of linearly transformed cones in a general setting. Their results
are based on a notion of _Renegar’s condition number_ , which can be defined
as

$\mathcal{R}_{C}(\bm{D})=\min\left\\{\frac{\left\|\bm{D}\right\|_{2}}{\lambda_{\text{min}}\left(\bm{D};C\right)},\frac{\left\|\bm{D}\right\|_{2}}{\sigma_{\mathbb{R}^{n}\to
C}(-\bm{D}^{T})}\right\\},$ (4.9)

where $C\subseteq\mathbb{R}^{d}$ is a closed, convex cone,
$\sigma_{\mathbb{R}^{n}\to
C}(-\bm{D}^{T})\coloneqq\min_{\bm{x}\in\mathcal{S}^{\smash{n-1}}}\left\|\bm{\Pi}_{C}(-\bm{D}^{T}\bm{x})\right\|_{2}$
and $\bm{\Pi}_{C}$ denotes the orthogonal projection on $C$. [ALW20, Theorem
A] then establishes the bound $\delta(\bm{D}\cdot
C)\leq\mathcal{R}^{2}_{C}(\bm{D})\cdot\delta(C)$, where $\delta$ denotes the
_statistical dimension_ , which is essentially equivalent to the conic mean
width; see proof of Proposition 4.3 in Appendix B for details.

Additionally, the authors of [ALW20] provide a “preconditioned”, probabilistic
version of the latter bound: For $m\leq n$ let $\bm{P}_{m}$ denote the
projection onto the first $m$ coordinates and define the quantity
$\mathcal{R}_{C,m}^{2}(\bm{D})\coloneqq\mathbb{E}_{\bm{Q}}[\mathcal{R}_{C}(\bm{P}_{m}\bm{Q}\bm{D})^{2}]$,
where the expectation is with respect to a random orthogonal matrix $\bm{Q}$,
distributed according to the normalized Haar measure on the orthogonal group.
[ALW20, Theorem B] then states that for any parameter $\nu\in(0,1)$ and
$m\geq\delta(C)+2\sqrt{\log(2/\nu)m}$, we have that $\delta(\bm{D}\cdot
C)\leq\mathcal{R}_{C,m}^{2}(\bm{D})\cdot\delta(C)+(n-m)\cdot\nu$. Due to the
second term in (4.9), both versions of Renegar’s condition number will be not
greater than $\kappa_{{\bm{D},C}}$, in general. Hence, ignoring the dependence
on $\nu$ and the condition on $m$ for simplicity, the bound on the required
samples of Corollary 4.4 could also be formulated with
$\mathcal{R}_{\mathcal{D}_{\wedge}(\left\|\cdot\right\|_{1},\bm{z}_{\ell^{\smash{1}}})}^{2}(\bm{D})$
or
$\mathcal{R}_{\mathcal{D}_{\wedge}(\left\|\cdot\right\|_{1},\bm{z}_{\ell^{\smash{1}}}),m}^{2}(\bm{D})$
instead of $\kappa_{{\bm{D},\bm{z}_{\ell^{\smash{1}}}}}$.

###  4.2 A Geometric Bound

In this section, we derive an upper bound for
$w^{2}_{\wedge}(\bm{D}\cdot\mathcal{D}(\left\|\cdot\right\|_{1};\bm{z}_{\ell^{\smash{1}}}))$
that is based on generic arguments from high-dimensional convex geometry. We
exploit the fact that the cone
$\bm{D}\cdot\mathcal{D}_{\wedge}(\left\|\cdot\right\|_{1};\bm{z}_{\ell^{\smash{1}}})$
is finitely generated by at most $2d$ vectors (see the proof of Proposition
4.16 in Appendix C.3) – a number that is typically significantly smaller than
exponential in the ambient dimension $n$. The resulting upper bound depends on
the maximal sparsity of elements in $Z_{\ell^{\smash{1}}}$ and on a single
geometric parameter that we refer to as _circumangle_ , whereas the number of
generators only has a logarithmic influence. This is comparable to the mean
width of a convex polytope, which is mainly determined by its diameter (cf.
Lemma C.1) and by the logarithm of its number of vertices.

In Section 4.2.1, we first introduce the required notation and show an upper
bound on the conic mean width of pointed polyhedral cones. We then focus on
the geometry of the descent cone
$\mathcal{D}_{\wedge}(p_{\bm{D}\cdot\text{B}_{1}^{\smash{d}}},\bm{x}_{0})$
(see Section 4.2.2) in order to derive the desired upper bound on the
expression
$w^{2}_{\wedge}(\bm{D}\cdot\mathcal{D}(\left\|\cdot\right\|_{1};\bm{z}_{\ell^{\smash{1}}}))$
in Section 4.2.3. Finally, we show how this bound can be used in practical
examples; see Section 4.2.4.

####  4.2.1 The Circumangle

The goal of this section is to relate the conic mean width of a pointed
polyhedral cone to its _circumangle_ , which describes the angle of an
enclosing circular cone. To that end, recall that a _circular cone_ (also
referred to as _revolution cone_) with _axis_
$\bm{\theta}\in\mathcal{S}^{\smash{n-1}}$ and _(half-aperture) angle_
$\alpha\in[0,\pi/2]$ is defined as

$C(\alpha,\bm{\theta})\coloneqq\\{\bm{x}\in\mathbb{R}^{n},\langle\bm{x},\bm{\theta}\rangle\geq\left\|\bm{x}\right\|_{2}\cdot\cos(\alpha)\\}.$
(4.10)

The conic mean width of a circular cone depends linearly on the ambient
dimension $n$, i.e.,
$w^{2}_{\wedge}(C(\alpha,\bm{\theta}))=n\cdot\sin^{2}(\alpha)+O(1)$, see for
instance [ALMT14, Proposition 3.4]. Although not directly related, it will be
insightful to compare this result with the subsequent upper bound of
Proposition 4.9.

The following definition introduces the so-called circumangle of a nontrivial
(different from $\left\\{\bm{0}\right\\}$ and $\mathbb{R}^{n}$) closed convex
cone $C$. It describes the angle of the smallest circular cone that contains
$C$.

######  Definition 4.6 (Circumangle)

Let $C\subset\mathbb{R}^{n}$ denote a nontrivial closed convex cone. Its
_circumangle_ $\alpha$ is defined by

$\alpha\coloneqq\inf\left\\{\hat{\alpha}\in[0,\pi/2]:\exists\bm{\theta}\in\mathcal{S}^{\smash{n-1}},C\subseteq
C(\hat{\alpha},\bm{\theta})\right\\}.$ (4.11)

The previous notion can be found under various names in the literature, see
for instance [FV99, Ren95, IS08, HS10a]. In particular, the previous quantity
arises in the definition of an outer center of a cone [HS10]. It turns out
that the circumangle satisfies

$\cos(\alpha)=\sup_{\bm{\theta}\in\mathcal{S}^{\smash{n-1}}}\inf_{\bm{x}\in
C\cap\mathcal{S}^{\smash{n-1}}}\langle\bm{\theta},\bm{x}\rangle,$ (4.12)

where a vector $\bm{\theta}$ that maximizes the right hand side is referred to
as _circumcenter_ (or _outer center_ 222Note that the notions of circumcenter
and outer centers generally differ, however, in the Euclidean setting of this
work they are equivalent [HS10, Section 5].) of $C$ [HS10, IS08]. Furthermore,
if $C$ is pointed (i.e., if it does not contain a line), the circumcenter is
unique and $\alpha\in[0,\pi/2)$ [HS10].

Note that the function $\bm{\theta}\mapsto\inf_{\bm{x}\in
C\cap\mathcal{S}^{\smash{n-1}}}\langle\bm{\theta},\bm{x}\rangle$ is concave as
a minimum of concave functions. Hence, if $C$ is pointed, it is easy to see
that determining the circumcenter and the circumangle amounts to solving the
following convex optimization problem:

$\cos(\alpha)=\sup_{\bm{\theta}\in\text{B}_{2}^{\smash{n}}}\inf_{\bm{x}\in
C\cap\mathcal{S}^{\smash{n-1}}}\langle\bm{\theta},\bm{x}\rangle.$ (4.13)

We now show that this characterization can be further simplified for pointed
polyhedral cones. The simple characterization of the following proposition
makes it possible to numerically compute the circumangle of such cones. We
emphasize that this stands in contrast to previously discussed notions such as
the minimum conic singular value, which is intractable in general. A short
proof is included in Appendix C.1.

######  Proposition 4.7 (Circumangle and circumcenter of polyhedral cones)

Let $\bm{x}_{i}\in\mathcal{S}^{\smash{n-1}}$ for $i\in[k]$ and let
$C=\operatorname{cone}(\bm{x}_{1},\ldots,\bm{x}_{k})$ be a nontrivial pointed
polyhedral cone. Finding the circumcenter and circumangle of $C$ amounts to
solving the convex problem:

$\cos(\alpha)=\sup_{\bm{\theta}\in\text{B}_{2}^{\smash{n}}}\inf_{i\in[k]}\langle\bm{\theta},\bm{x}_{i}\rangle.$
(4.14)

The goal of this section is to upper bound the conic mean width of all
polyhedral cones $C\subset\mathbb{R}^{n}$ with $k$ generators that are
contained in a circular cone of angle $\alpha$. To that end, we first
introduce the following notation:

###### Definition 4.8

A _$k$ -polyhedral $\alpha$-cone_ $C\subset\mathbb{R}^{n}$ is a nontrivial
pointed polyhedral cone generated by $k$ vectors that is included in a
circular cone with angle $\alpha\in[0,\pi/2)$. Furthermore, we let
$\mathcal{C}_{k}^{\alpha}$ denote the set of all $k$-polyhedral
$\alpha$-cones.

Note that $C$ being a nontrivial pointed polyhedral cone implies that such an
encompassing circular cone with angle $\alpha\in[0,\pi/2)$ exists. The next
result provides a simple upper bound on the quantity

$W(\alpha,k,n):=\sup_{C\in\mathcal{C}_{k}^{\alpha},C\subset\mathbb{R}^{n}}w_{\wedge}(C).$
(4.15)

The underlying geometric idea is explained in Figure 2 and its proof is
detailed in Appendix C.2. Note that the bound does not depend on the ambient
dimension $n$, which is in contrast to the conic width of a circular cone.

Figure 2: Geometry of Proposition 4.9. The figure shows a polyhedral cone
(transparent gray) truncated at $z=1$ and included in a circular cone with
angle $\alpha$ (wire-frame). The standard basis vector $\bm{e}_{z}$
corresponds to the circumcenter of the polyhedral cone and $\alpha$ is chosen
as its circumangle. The thick line is the intersection of the unit sphere with
the faces of the polyhedral cone. Right view is from above, or equivalently,
the projection on the plane $z=1$. The conic mean width of the polyhedral cone
can be bounded by evaluating the mean width of any set containing the thick
line plus 1 (as a subset of the plane). The proposed bound is based on using
the intersection of the polyhedral cone and the plane $z=1$. Notice that this
convex body is included in the disk with radius $\tan\alpha$. In high
dimensions, it will be thin if the polyhedral cone does not have
overwhelmingly many extremal rays.

###### Proposition 4.9

For $k\geq 5$, the conic mean width of a $k$-polyhedral $\alpha$-cone $C$ in
$\mathbb{R}^{n}$ is bounded by

$\displaystyle W(\alpha,k,n)$
$\displaystyle\leq\tan\alpha\cdot\left(\sqrt{2\log\left(k/\sqrt{2\pi}\right)}+\frac{1}{\sqrt{2\log\left(k/\sqrt{2\pi}\right)}}\right)+\frac{1}{\sqrt{2\pi}}.$
(4.16)

We conclude this section with the following remark:

###### Remark 4.10

The previous upper bound is based on Lemma C.1, which provides a basic bound
on the Gaussian mean width of a convex polytope; see also [Ver18, Ex. 7.5.10 &
Prop. 7.5.2]. Using a tighter estimate there (possibly an implicit description
as in [ALMT14, Proposition 4.5]) would in turn also improve Proposition 4.9.

####  4.2.2 Geometry of the Descent Cone

In order to derive an upper bound for the quantity
$w^{2}_{\wedge}(\bm{D}\cdot\mathcal{D}(\left\|\cdot\right\|_{1};\bm{z}_{\ell^{\smash{1}}}))$
based on the previous result, we first need a more geometrical description of
the descent cones of the $\ell^{\smash{1}}$-norm and of the gauge
$p_{\bm{D}\cdot\text{B}_{1}^{\smash{d}}}$.

###### Lemma 4.11

Let $\bm{z}\in\mathbb{R}^{d}$ with support
$\operatorname{supp}{\bm{z}}=\mathcal{S}$ and $\\#\mathcal{S}=s$. Then,

$\mathcal{D}_{\wedge}(\left\|\cdot\right\|_{1},\bm{z})=\operatorname{cone}(\pm
s\cdot\bm{e}_{i}-\bm{v}:i\in[d]).$ (4.18)

where $\bm{v}$ is any vector such that $\|\bm{v}\|_{1}=s$ and
$\operatorname{sign}\bm{v}=\operatorname{sign}\bm{z}$, e.g.,
$\bm{v}=\operatorname{sign}\bm{z}$ or $\bm{v}=s\cdot\bm{z}/\|\bm{z}\|_{1}$.

A proof of the previous lemma can be found in Appendix C.3. The statement is
illustrated in Figure 3 for dimension $d=3$. Observe that sliding $\bm{z}$
along the edge linking $\bm{e}_{2}$ with $\bm{e}_{3}$ leaves the descent cone
unchanged.

Figure 3: Illustration of Lemma 4.11. Left: $\ell^{1}$-ball in
$\mathbb{R}^{3}$ and a $2$-sparse vector $\bm{z}$. Center: The rays of the
descent cone are supported by the vectors
$\bm{r}_{i}^{\pm}=\pm\bm{e}_{i}-\bm{z}$, which corresponds to the generators
of Lemma 4.11 with $\bm{v}=s\cdot\bm{z}/\left\|\bm{z}\right\|_{1}$, multiplied
by $1/2$. Right: The resulting descent cone (shifted by $\bm{z}$). Note that
it contains a linear subspace spanned by $\bm{r}_{2}^{+}$ and
$\bm{r}_{3}^{+}$.

Whenever a convex cone contains a subspace, its circumangle is $\pi/2$ and the
bound of Proposition 4.9 is not applicable. As can be seen in Figure 3, the
descent cone of the $\ell^{1}$-norm at $\bm{z}$ contains the subspace spanned
by the face of minimal dimension containing $\bm{z}$. To avoid this pitfall,
let us recall the notion of lineality.

######  Definition 4.12 (Lineality [Roc70])

For a non-empty convex set $C\subseteq\mathbb{R}^{n}$, the _lineality space
$C_{L}$ of $C$_ is defined as

$C_{L}\coloneqq\left\\{\bm{x}\in\mathbb{R}^{n}:\forall\bm{\tilde{x}}\in
C:\left\\{\bm{\tilde{x}}+\alpha\cdot\bm{x}:\alpha\in\mathbb{R}\right\\}\subseteq
C\right\\}.$ (4.19)

It defines a subspace of $R^{n}$ and its dimension is referred to as the
_lineality_ of $C$.

Any non-empty convex set $C$ can be expressed as the direct sum

$C=C_{L}\oplus C_{R}\mbox{ with }C_{R}\coloneqq\bm{P}_{C_{L}^{\perp}}(C),$
(4.20)

where $\bm{P}_{\smash{C_{L}^{\perp}}}$ is the orthogonal projection onto
$C_{L}^{\perp}$. The notation $C_{R}$ is used in analogy to the _range_ in
linear algebra. The set $C_{R}$ is “line-free” (i.e., its lineality is
$\left\\{\bm{0}\right\\}$) and its dimension is called the _rank_ of $C$. If
$C$ is a convex cone, the lineality space is the largest subspace contained in
$C$ and the circumangle of the range $C_{R}$ is less than $\pi/2$. In the
following, we will therefore apply Proposition 4.9 to the latter set only.
Figure 4 illustrates the orthogonal decomposition of (4.20) for the descent
cone of Figure 3.

The following lemma characterizes the lineality space and the range for
descent cones of the $\ell^{1}$-norm. A proof is given in Appendix C.3.

###### Lemma 4.13

Let $\bm{z}=(z_{1},\ldots,z_{d})$ be a vector with support
$\operatorname{supp}{\bm{z}}=\mathcal{S}$ and $\\#\mathcal{S}=s\geq 1$. The
lineality space of $C=\mathcal{D}_{\wedge}(\left\|\cdot\right\|_{1},\bm{z})$
is then given by

$C_{L}=\operatorname{\operatorname{span}}\left(s\cdot\operatorname{sign}(z_{i})\cdot\bm{e}_{i}-\operatorname{sign}(\bm{z}):i\in\mathcal{S}\right),$
(4.21)

with lineality $\dim(C_{L})=s-1$.

Notice that the lineality space is nothing but the face of the
$\ell^{\smash{1}}$-ball of smallest dimension containing $\bm{z}$.

Figure 4: Decomposition into the direct sum of the lineality space and range.
Left: Decomposition of $\mathbb{R}^{3}$ into the lineality space $C_{L}$ and
its orthogonal complement $C_{L}^{\perp}$, where $C$ is the descent cone of
Figure 3. Middle: Different view of $C$, where
$\bm{r}_{i}^{\pm\perp}\coloneqq\bm{P}_{\smash{C_{L}^{\perp}}}(\bm{r}_{i}^{\pm})$.
Right: Visualization of the orthogonal decomposition of $C$ into its lineality
space and range $C_{R}=\bm{P}_{\smash{C_{L}^{\perp}}}(C)$. The angle $\alpha$
corresponds to the circumangle of $C_{R}$ and $\bm{\theta}$ denotes its
circumcenter.

We now turn to the decomposition of the descent cone of the gauge
$p_{\bm{D}\cdot\text{B}_{1}^{\smash{d}}}$ into lineality space and range. To
that end, let us first make the following simple observation.

######  Lemma 4.14 (Sign pattern of $\ell^{1}$-representers)

All minimal $\ell^{1}$-representers of $\bm{x}_{0}$ with respect to $\bm{D}$
share the same sign pattern, in the sense that for all
$\bm{z}_{\ell^{\smash{1}}}^{1}$, $\bm{z}_{\ell^{\smash{1}}}^{2}\in
Z_{\ell^{\smash{1}}}$, the coordinate-wise product
$\bm{z}_{\ell^{\smash{1}}}^{1}\cdot\bm{z}_{\ell^{\smash{1}}}^{2}$ is
nonnegative.

This lemma allows us to define the maximal $\ell^{1}$-support.

######  Definition 4.15 (Maximal $\ell^{1}$-support)

Let $\bm{x}_{0}\in\mathbb{R}^{n}$ and $\bm{D}\in\mathbb{R}^{n\times d}$ be a
dictionary. The maximal $\ell^{1}$-support $\bar{\mathcal{S}}$ of $\bm{x}_{0}$
in $\bm{D}$ (or simply maximal support) is defined as
$\bar{\mathcal{S}}\coloneqq\cup_{\bm{z}_{\ell^{\smash{1}}}\in
Z_{\ell^{\smash{1}}}}\mathrm{supp}(\bm{z}_{\ell^{\smash{1}}})$. In what
follows, we let $\bar{s}=\\#\bar{\mathcal{S}}$ denote its cardinality.

Since all solutions $\bm{z}_{\ell^{\smash{1}}}\in Z_{\ell^{\smash{1}}}$ have
the same sign pattern, any point $\bm{z}_{\ell^{\smash{1}}}$ in the relative
interior of $Z_{\ell^{\smash{1}}}$ has maximal support. The next decomposition
forms the main result of this section; see Appendix C.3 for a proof.

###### Proposition 4.16

Let $\bm{D}\in\mathbb{R}^{n\times d}$ be a dictionary and let
$\bm{x}_{0}\in\operatorname{ran}(\bm{D})\setminus\\{\bm{0}\\}$. Let
$C=\mathcal{D}_{\wedge}(p_{\bm{D}\cdot\text{B}_{1}^{\smash{d}}},\bm{x}_{0})$
denote the descent cone of the gauge at $\bm{x}_{0}$. Let
$\bm{z}_{\ell^{\smash{1}}}\in\mathrm{ri}(Z_{\ell^{\smash{1}}})$ be any minimal
$\ell^{\smash{1}}$-representer of $\bm{x}_{0}$ in $\bm{D}$ with maximal
support and set
$\bar{\mathcal{S}}=\operatorname{supp}(\bm{z}_{\ell^{\smash{1}}})$ as well as
$\bar{s}=\\#\bar{\mathcal{S}}$. Assume $\bar{s}<d$. Then we have:

  1. (a)

The lineality space of $C$ has a dimension less than $\bar{s}-1$ and is given
by

$C_{L}=\operatorname{\operatorname{span}}(\bar{s}\cdot\operatorname{sign}(z_{\ell^{1},i})\cdot\bm{d}_{i}-\bm{D}\cdot\operatorname{sign}(\bm{z}_{\ell^{\smash{1}}}):i\in\bar{\mathcal{S}}).$
(4.22)

  2. (b)

The range of $C$ is a $2(d-\bar{s})$-polyhedral $\alpha$-cone given by:

$C_{R}=\mathrm{cone}(\bm{r}_{j}^{\pm\perp}:j\in\bar{\mathcal{S}}^{c})\mbox{
with
}\bm{r}_{j}^{\pm\perp}\coloneqq\bm{P}_{C_{L}^{\perp}}\left(\pm\bar{s}\cdot\bm{d}_{j}-\bm{D}\cdot\operatorname{sign}(\bm{z}_{\ell^{\smash{1}}})\right).$
(4.23)

####  4.2.3 Consequence for the Sampling Rates

We now combine the main results of the previous two sections to derive an
upper bound on the conic mean width of
$\mathcal{D}_{\wedge}(p_{\bm{D}\cdot\text{B}_{1}^{\smash{d}}},\bm{x}_{0})$.

###### Theorem 4.17

If $\bar{s}\leq d-3$, we obtain that

$w^{2}_{\wedge}(\mathcal{D}_{\wedge}(p_{\bm{D}\cdot\text{B}_{1}^{\smash{d}}},\bm{x}_{0}))\leq\bar{s}+\left(\tan\alpha\cdot\left(\sqrt{2\log\left(\frac{2(d-\bar{s})}{\sqrt{2\pi}}\right)}+1\right)+\frac{1}{\sqrt{2\pi}}\right)^{2},$

where we have used the same notation and assumptions as in Proposition 4.16.

A proof of the previous result is given in Appendix C.4. As a direct
consequence, we get the following upper bound on the sampling rates for
coefficient and signal recovery.

###### Corollary 4.18

The critical number of measurements $m_{0}$ in (3.3) and (3.5) satisfies

$m_{0}\lesssim\bar{s}+\tan^{2}\alpha\cdot\log(2(d-\bar{s})/\sqrt{2\pi}).$
(4.24)

This result shows that robust coefficient and signal recovery is possible,
when the number of measurements obeys
$m\gtrsim\bar{s}+\cdot\tan^{2}\alpha\cdot\log(d)$. Hence, the sampling rate is
mainly governed by the sparsity of maximal support $\ell^{1}$-representations
of $\bm{x}_{0}$ in $\bm{D}$ and the “narrowness” of the remaining cone
$C_{R}$, which is captured by its circumangle $\alpha\in[0,\pi/2)$. The number
of dictionary atoms only has a logarithmic influence. The next section is
devoted to applying the previous result to various examples.

###### Remark 4.19

For the sake of clarity, the previous results are given in terms of the
maximal sparsity. However, (potentially) more precise bounds can be achieved
when replacing $\bar{s}$ by $\dim(C_{L})$. Furthermore note, that the proof of
Theorem 4.17 reveals that $\dim(C_{L})$ is a necessary component in the
required number of measurements. Indeed, since
$w^{2}_{\wedge}(\mathcal{D}_{\wedge}(p_{\bm{D}\cdot\text{B}_{1}^{\smash{d}}},\bm{x}_{0}))$
is a sharp description for the required number of measurements, equation
(C.31) shows that the number of measurements for successful recovery is lower
bounded by $\dim(C_{L})$.

####  4.2.4 Examples

In this section, we discuss four applications of the previous upper bound on
the conic mean width. First, we show that prediction for the required number
of measurements agrees with the standard theory of compressed sensing. We then
analytically compute the sampling rate of Corollary 4.18 for a specific
scenario, in which the dictionary is formed by a concatenation of
convolutions. The third example focuses on a numerical simulation in the case
of 1D total variation. Lastly, we demonstrate how the circumangle can be
controlled by the classical notion of coherence.

##### The Standard Basis

Our first example is dedicated to showing that the result of Corollary 4.18 is
consistent with the standard theory of compressed sensing when
$\bm{D}=\operatorname{\textbf{Id}}$. Hence, assume that we are given a sparse
vector $\bm{x}_{0}\in\mathbb{R}^{n}$ with
$\mathcal{S}=\operatorname{supp}(\bm{x}_{0})$ and $s=\\#\mathcal{S}\leq n-3$.
Trivially, $\bm{x}_{0}$ is then its own, unique $\ell^{1}$-representation with
respect to $\operatorname{\textbf{Id}}$. According to Lemma 4.13, the
$(s-1)$-dimensional lineality space of
$C=\mathcal{D}_{\wedge}(\left\|\cdot\right\|_{1},\bm{x}_{0})$ is given by

$C_{L}=\operatorname{\operatorname{span}}\left(\bm{r}_{i}^{+}:i\in\mathcal{S}\right),$
(4.25)

where
$\bm{r}_{i}^{+}=s\cdot\operatorname{sign}(x_{0,i})\cdot\bm{e}_{i}-\operatorname{sign}(\bm{x}_{0})$.
For $i\in\mathcal{S}^{c}$ a simple calculation shows that
$\bm{\theta},\bm{r}^{\pm}_{i}\in C_{L}^{\perp},$ where
$\bm{\theta}=-\operatorname{sign}(\bm{x}_{0})/\sqrt{s}\in\mathcal{S}^{\smash{n-1}}$
and $\bm{r}^{\pm}_{i}=\pm s\cdot\bm{e}_{i}-\operatorname{sign}(\bm{x}_{0})$.
Furthermore, for $i\in\mathcal{S}^{c}$ it holds true that

$\left\langle\bm{\theta},\bm{r}^{\pm}_{i}\right\rangle=\sqrt{s}=(1/\sqrt{s+1})\cdot\left\|\bm{r}^{\pm}_{i}\right\|,$
(4.26)

so that the vectors $\bm{r}^{\pm}_{i}$ generate a $2(n-s)$-polyhedral
$\alpha$-cone $C_{R}$ with $\tan^{2}\alpha=s$. Hence, Corollary 4.18 states
that robust recovery of $\bm{x}_{0}$ is possible for $m\gtrsim
2s\log(2(n-s)/\sqrt{2\pi})$ measurements. This bound is to be compared with
the classical compressed sensing result, which prescribes to take $m\gtrsim
2s\log(n/s)$ measurements. Note that the slight difference in the logarithmic
factor is due to our simple bound on $W(\alpha,k,n)$, cf. Remark 4.10.

##### A Convolutional Dictionary

Consider a dictionary $\bm{D}$ defined by the concatenation of two convolution
matrices $\mathbf{H}_{1}$ and $\mathbf{H}_{2}$ with convolution kernels
$\bm{h}_{1}=[1,1]$ and $\bm{h}_{2}=[1,-1]$, respectively. For instance, in
dimension $n=4$, this would yield the following matrix:

$\bm{D}=\begin{pmatrix}1&1&0&0&1&-1&0&0\\\ 0&1&1&0&0&1&-1&0\\\
0&0&1&1&0&0&1&-1\\\ 1&0&0&1&-1&0&0&1\end{pmatrix}.$ (4.27)

In particular for imaging applications, popular signal models are based on
sparsity in such concatenations of convolutional matrices, e.g., translation
invariant wavelets [Mal09] or learned filters in the convolutional sparse
coding model [Woh14, BEL13]. Note that the resulting dictionary is highly
redundant and correlated, so that existing coherence- and RIP-based arguments
cannot provide satisfactory recovery guarantees. For the same reason, a
recovery of a unique minimal $\ell^{1}$-representer by
($\text{BP}_{\eta}^{\text{\smash{coef}}}$) is unlikely, cf. the numerical
simulation in Section 5.2. However, in the following, we will show how the
previous upper bound based on the circumangle can be used in order to analyze
signal recovery by ($\text{BP}_{\eta}^{\text{\smash{sig}}}$).

To that end, we consider the recovery of a simple vector
$\bm{x}_{0}\in\mathbb{R}^{n}$ supported on the first and the last component
only, i.e., $x_{0,i}=0$ for all $2\leq i\leq n-1$. A generalization to vectors
supported on supports made of pairs of contiguous indices separated by pairs
of contiguous zeros is doable, but we prefer this simple setting for didactic
reasons. In this case, the set of minimal $\ell^{1}$-representers can be
completely characterized. Assuming additionally that $x_{0,1}>x_{0,n}>0$, one
can show that

$\displaystyle Z_{\ell^{1}}=\big{\\{}$
$\displaystyle\bm{z}_{\ell^{\smash{1}}}=[\bm{z}^{(1)};\bm{z}^{(2)}]\in\mathbb{R}^{2n},\textrm{
with
}\operatorname{supp}(\bm{z}^{(1)})=\operatorname{supp}(\bm{z}^{(2)})=\\{1,2\\},$
$\displaystyle
z_{1}^{(1)}=\frac{x_{0,1}+x_{0,n}}{2}-\delta,z_{1}^{(1)}=\delta,z_{2}^{(1)}=\frac{x_{0,1}-x_{0,n}}{2}-\delta,z_{2}^{(1)}=-\delta,$
$\displaystyle 0\leq\delta\leq\frac{x_{0,1}-x_{0,n}}{2}\big{\\}}.$

Let $\bm{z}_{\ell^{\smash{1}}}\in Z_{\ell^{1}}$ denote any representer with
maximal support
$S=\operatorname{supp}(\bm{z}_{\ell^{\smash{1}}})=\left\\{1,2,n+1,n+2\right\\}$
and set $\bm{v}=\bm{D}\cdot\operatorname{sign}(\bm{z}_{\ell^{\smash{1}}})$.
According to Proposition 4.16, we then decompose the descent cone
$C=\mathcal{D}_{\wedge}(p_{\bm{D}\cdot\text{B}_{1}^{\smash{d}}},\bm{x}_{0})$
into $C=C_{L}\oplus C_{R}$, where $C_{L}$ is the lineality space given by

$C_{L}=\operatorname{\operatorname{span}}(4\cdot\operatorname{sign}(z_{\ell^{1},i})\cdot\bm{d}_{i}-\bm{v}:i\in
S),$

and the range is given by
$C_{R}=\operatorname{cone}(\bm{P}_{\smash{C_{L}^{\perp}}}(\pm
4\cdot\bm{d}_{j}-\bm{v}:j\in S^{c}))$. It is easy to see that $\dim(C_{L})=2$,
and that the projection on $C_{L}^{\perp}$ can be expressed as

$(\bm{P}_{C_{L}^{\perp}}(\bm{x}))_{i}=\begin{cases}0,&\textrm{ if
}i\in\\{2,n\\},\\\ x_{i},&\textrm{ otherwise}.\end{cases}$

The goal is now to show that $C_{R}$ is contained in a circular cone with
angle $\alpha=\arccos(1/\sqrt{3})$ and axis
$\bm{\theta}=-\bm{P}_{\smash{C_{L}^{\perp}}}(\bm{v})/\left\|\bm{P}_{\smash{C_{L}^{\perp}}}(\bm{v})\right\|_{2}=-\bm{e}_{1}$.
Indeed, a straightforward computation shows that for $j\in S^{c}$ we have

$\left(\bm{P}_{C_{L}^{\perp}}(\pm
4\cdot\bm{d}_{j}-\bm{v})/\left\|\bm{P}_{C_{L}^{\perp}}(\pm
4\cdot\bm{d}_{j}-\bm{v})\right\|_{2}\right)_{1}\in\left\\{-1/\sqrt{2},-1/\sqrt{3}\right\\}.$

Hence, Corollary 4.18 implies that robust recovery of $\bm{x}_{0}$ is possible
for $m\gtrsim 2+2\log(4n)$ measurements.

##### 1D Total Variation

As a third example we consider the problem of total variation minimization in
1D. Assume that $\bm{x}_{0},\bm{A},\bm{y},\bm{e}$ and $\eta$ follow Model 1
with $\eta=0$ and that $\bm{A}$ obeys Model 1.1. Total variation minimization
is based on the assumption that $\bm{x}_{0}$ is gradient-sparse, i.e., that
$\\#\operatorname{supp}(\nabla\bm{x}_{0})\leq s\ll n$, where
$\nabla\in\mathbb{R}^{n-1\times n}$ denotes a discrete gradient operator,
which is for instance based on forward differences with von Neumann boundary
conditions. In order to recover $\bm{x}_{0}$ from its noiseless, compressed
measurements $\bm{y}$, one solves the program

$\min_{\bm{x}\in\mathbb{R}^{n}}\left\|\nabla\bm{x}\right\|_{1}\quad\mbox{ s.t.
}\quad\bm{y}=\bm{A}\bm{x}.$ (4.28)

For signals with $\mathbf{1}^{T}\cdot\bm{x}_{0}=0$ it is easy to see that the
previous formulation is equivalent to solving the synthesis basis pursuit
($\text{BP}_{\smash{\eta=0}}^{\text{\smash{sig}}}$) with
$\bm{D}=\nabla^{\dagger}$, where $\nabla^{\dagger}\in\mathbb{R}^{n\times n-1}$
denotes the Moore-Penrose inverse of $\nabla$.

The research of the past three decades demonstrates that encouraging a small
total variation norm often efficaciously reflects the inherent structure of
real-world signals. Although not as popular as its counterpart in 2D, total
variation methods in one spatial dimension find application in many practical
applications, see for instance [LJ11]. Somewhat surprisingly, Cai and Xu have
shown that a _uniform_ recovery of all $s$-gradient-sparse signals is possible
if and only if the number of (Gaussian) measurements obeys
$m\gtrsim\sqrt{sn}\cdot\log(n)$; see [CX15]. Recently, [GMS20] has proven that
this square-root bottleneck can be broken for signals with well separated jump
discontinuities. This result is also based on establishing a non-trivial upper
bound on the conic mean width. For such “natural” signals, $m\gtrsim
s\cdot\log^{\smash{2}}(n)$ measurements are already sufficient for exact
recovery. See also [GLCS20, DHL17] for closely related results in a denoising
context.

We want to demonstrate that the upper bound on the conic mean width based on
the circumangle is capable of breaking the square-root bottleneck of the
synthesis-based reformulation above. A theoretical analysis appears to be
doable, however, it is beyond the scope of this work. Instead, we restrict
ourselves to a simple numerical simulation. We consider signals that are
defined by the pointwise discretization of a function on an interval with a
few equidistant discontinuities and zero average. Note that for such a signal
$\bm{x}_{0}$ the unique minimal $\ell^{1}$-representer with respect to
$\nabla^{\dagger}$ is simply given by $\nabla\bm{x}_{0}$. Hence, we are only
left with numerically computing the circumangle $\alpha$ of the range $C_{R}$
in Proposition 4.16, which is done by means of Proposition 4.7. In order to
confirm that required number of measurements scales logarithmically in the
ambient dimension $n$, we analyze the behavior of $\tan^{2}\alpha$ when the
resolution is increased, i.e., for $n=500,1000,\dots 10000$. The result is
shown in Figure 5. The logarithmic scaling of $\tan^{2}\alpha$ (note that the
$n$-axis is logarithmic) indeed suggests that the bound of Corollary 4.18
predicts that $m\gtrsim s\cdot\log^{\smash{2}}(n)$ measurements suffice for
exact recovery. Hence, the presented upper bound based on the circumangle
appears to be sharp enough to break the square-root bottleneck of total
variation minimization in 1D.

Figure 5: Logarithmic scaling of $\tan^{2}\alpha$. The figure displays the
behavior of $\tan^{2}\alpha$ for increasing ambient dimension $n$, where
$\alpha$ denotes the circumangle of the range $C_{R}$ in Proposition 4.9.
Here, the dictionary is chosen as $\bm{D}=\nabla^{\dagger}$ and the considered
signals $\bm{x}_{0}$ have equidistant jump discontinuities and zero average.
The plot indicates that the upper bound based on the circumangle is sharp
enough to break the square-root bottleneck of [CX15].

##### Coherence and Circumangle

In our last example, we show that the circumangle of $C_{R}$ of Proposition
4.16 can be controlled in terms of the _mutual coherence_ of the dictionary
(see Equation (1.5)). This notion is a classical concept in the literature on
sparse representations, which is frequently used to derive uniform recovery
statements; see for instance [FR13, Chapter 5] for an overview. Note that the
assumption $s<\tfrac{1}{2}(1+\mu^{-1})$ of the following result guarantees
that every $s$-sparse $\bm{z}_{\ell^{\smash{1}}}$ is the unique minimal
$\ell^{\smash{1}}$-representer of its associated signal
$\bm{D}\bm{z}_{\ell^{\smash{1}}}$ [DE03, GN03]. Hence, in this situation,
coefficient and signal recovery are equivalent, and both formulations are
governed by the conic mean width of the cone
$C=\mathcal{D}_{\wedge}(p_{\bm{D}\cdot\text{B}_{1}^{\smash{d}}},\bm{D}\bm{z}_{\ell^{\smash{1}}})=\bm{D}\cdot\mathcal{D}_{\wedge}(\left\|\cdot\right\|_{1},\bm{z}_{\ell^{\smash{1}}})$.

###### Proposition 4.20

Let $\bm{D}\in\mathbb{R}^{n\times d}$ be a dictionary that spans
$\mathbb{R}^{n}$ with $\|\bm{d}_{i}\|_{2}\leq 1$ for $i\in[d]$ and mutual
coherence $\mu=\mu(\bm{D})$. Let
$\bm{z}_{\ell^{\smash{1}}}\in\mathbb{R}^{d}\setminus\left\\{\bm{0}\right\\}$
denote an arbitrary $s$-sparse vector with $s<\frac{1}{2}(1+\mu^{-1})$. Then
the circumangle $\alpha$ of the range $C_{R}$ of the descent cone
$C=\mathcal{D}_{\wedge}(p_{\bm{D}\cdot\text{B}_{1}^{\smash{d}}},\bm{D}\bm{z}_{\ell^{\smash{1}}})$
obeys:

$\displaystyle\tan^{2}\alpha$
$\displaystyle\leq\frac{s(1-s\mu)}{(1-2s\mu)^{2}}.$

A proof of the previous result can be found in Appendix C.5. The statement
allows us to retrieve a bound of the order $m\gtrsim s\log(d)$ for the needed
number of measurements. For example, with $s\mu=1/10$, the bound of Corollary
4.18 results in a sampling rate of $m_{0}\leq 4s\log(d)$. Observe that this is
essentially the same result as [RSV08, Corollary II.4], however, the constants
of Proposition 4.20 are better controlled.

Note that the mutual coherence of a dictionary (sometimes also referred to as
_worst-case coherence_ [CK13, Chapter 9]) is a global quantity that is usually
used to derive recovery guarantees that are uniform across all $s$-sparse
signals. Approaches based on this notion suffer from the so-called square-root
bottleneck: The Welch bound [FR13, Theorem 5.7] reveals that the condition
$s<\tfrac{1}{2}(1+\mu^{-1})$ can only be satisfied for mild sparsity values
$s\lesssim\sqrt{n}$. We emphasize that this is in contrast to the strategy of
this work, which is tailored for a non-uniform recovery of individual signals.
Indeed, the circumangle is a signal-dependent notion that allows to describe
the local geometry.

##  5 Numerical Experiments

In this section, we illustrate our main findings regarding the
$\ell^{1}$-synthesis formulation by performing numerical simulations. First,
we study the recovery of coefficient representations by
($\text{BP}_{\smash{\eta=0}}^{\text{\smash{coef}}}$); see Section 5.1. In
Section 5.2, we then focus on signal recovery by
($\text{BP}_{\smash{\eta=0}}^{\text{\smash{sig}}}$) in situations, where the
identification of a coefficient representation is impossible. Section 5.3 is
dedicated to the experiment of Figure 1, in which both formulations are
compared. Lastly, we investigate the differences concerning robustness to
measurement noise in Section 5.4. For general design principles and more
details on our simulations we refer the interested reader to Appendix D.

To the best of our knowledge, all other compressed sensing results on the
$\ell^{\smash{1}}$-synthesis formulation with redundant dictionaries describe
the sampling rate as an asymptotic order bound. Hence, these results are not
compatible with the experiments in this section and will not be further
considered.

###  5.1 Sampling Rates for Coefficient Recovery

In order to study coefficient recovery by
($\text{BP}_{\smash{\eta=0}}^{\text{\smash{coef}}}$), we create _phase
transition plots_ by running Experiment 5.1 for different dictionary and
signal combinations reported below.

######  Experiment 5.1 (Phase transition for a fixed coefficient vector)

Input: Dictionary $\bm{D}\in\mathbb{R}^{n\times d}$, coefficient vector
$\bm{z}_{\ell^{\smash{1}}}\in\mathbb{R}^{d}$.

Compute: Repeat the following procedure $100$ times for every $m=1,2,\dots,n$:

  * $\blacktriangleright$

Draw a standard i.i.d. Gaussian random matrix $\bm{A}\in\mathbb{R}^{m\times
n}$ and determine the measurement vector
$\bm{y}=\bm{A}\bm{D}\bm{z}_{\ell^{\smash{1}}}$.

  * $\blacktriangleright$

Solve the program ($\text{BP}_{\smash{\eta=0}}^{\text{\smash{coef}}}$) to
obtain an estimator $\hat{\bm{z}}\in\mathbb{R}^{d}$.

  * $\blacktriangleright$

Compute and store the recovery error
$\left\|\bm{z}_{\ell^{\smash{1}}}-\hat{\bm{z}}\right\|_{2}$. Declare success
if $\left\|\bm{z}_{\ell^{\smash{1}}}-\hat{\bm{z}}\right\|_{2}<10^{-5}$.

##### Simulation Settings

Our first two examples are based on a redundant Haar wavelet frame, which can
be seen as a typical representation system in the field of applied harmonic
analysis, see [Mal09] for more details on wavelets and Section 3.1 in [GKM20]
for a short discussion in the context of compressed sensing. As a back-end for
defining the wavelet transform, we are using the Matlab software package spot
[BF13], which is in turn based on the Rice Wavelet Toolbox [B+17]. We set the
ambient dimension to $n=256$ and consider a Haar system with $3$ decomposition
levels and normalized atoms. The resulting dictionary is denoted by
$\bm{D}=\bm{D}_{\texttt{Haar}}\in\mathbb{R}^{256\times 1024}$. The first
coefficient vector $\bm{z}_{\ell^{\smash{1}}}^{\smash{1}}\in\mathbb{R}^{1024}$
is obtained by selecting a random support set of cardinality $s=16$, together
with random coefficients; see Subfigure 6(c) for a visualization of
$\bm{z}_{\ell^{\smash{1}}}^{1}$ and Subfigure 6(b) for the resulting signal
$\bm{x}_{1}=\bm{D}_{\texttt{Haar}}\cdot\bm{z}_{\ell^{\smash{1}}}^{1}$. The
second coefficient vector $\bm{z}_{\ell^{\smash{1}}}^{2}$ is created by
defining two contiguous blocks of non-zero coefficients in the low frequency
part, again with $s=16$; see Subfigure 6(f) for a plot of
$\bm{z}_{\ell^{\smash{1}}}^{2}$ and Subfigure 6(e) for the resulting signal
$\bm{x}_{2}=\bm{D}_{\texttt{Haar}}\cdot\bm{z}_{\ell^{\smash{1}}}^{\smash{2}}$.
For each signal we run Experiment 5.1 and report the empirical success rate in
the Subfigures 6(a), 6(d), respectively.

In the third example, the dictionary is chosen as a Gaussian random matrix,
which is a typical benchmark system for compressed sensing with redundant
frames, see for instance [GKM20, KR15, CWW14]. Also in this case, we set
$n=256$, but we choose $d=512$. The resulting dictionary is denoted by
$\bm{D}_{\texttt{rand}}\in\mathbb{R}^{256\times 512}$. The coefficient vector
$\bm{z}_{\ell^{\smash{1}}}^{3}$ is defined in the same manner as
$\bm{z}_{\ell^{\smash{1}}}^{1}$ above (see Subfigure 6(i)), where we again
have $\|\bm{z}_{\ell^{\smash{1}}}^{3}\|_{0}=16$. The resulting signal
$\bm{x}_{3}$ is shown in Subfigure 6(h) and the empirical success rate in
Subfigure 6(g).

Our fourth and last dictionary is inspired by super-resolution; see for
instance [CF14]. We again set $n=256$ and choose the dictionary
$\bm{D}_{\texttt{super}}\in\mathbb{R}^{256\times 256}$ as a convolution with a
discrete Gaussian function of large variance. This example can therefore be
considered as a finely discretized super-resolution problem. The coefficient
vector $\bm{z}_{\ell^{\smash{1}}}^{4}$ is then chosen as a sparse vector with
$z_{\ell^{\smash{1}},128}^{\smash{4}}=1$ and
$z_{\ell^{\smash{1}},129}^{\smash{4}}=-1$, see Subfigure 6(l). Hence, in the
signal $\bm{x}_{4}$, the two neighboring peaks almost cancel out and result in
the low amplitude signal shown in Subfigure 6(k). Finally, the empirical
success rate is depicted in Subfigure 6(j). Note that for each example we have
verified the condition
$\lambda_{\text{min}}\left(\bm{D};\mathcal{D}_{\wedge}(\left\|\cdot\right\|_{1},\bm{z}_{\ell^{\smash{1}}}^{i})\right)>0$
heuristically by verifying that
$Z_{\ell^{\smash{1}}}=\left\\{\bm{z}_{\ell^{\smash{1}}}^{\smash{i}}\right\\}$,
respectively.

##### Results

Let us now analyze the empirical success rates of Figure 6 and compare them
with the estimates of
$w^{2}_{\wedge}(\bm{D}\cdot\mathcal{D}(\left\|\cdot\right\|_{1};\bm{z}_{\ell^{\smash{1}}}^{i}))$
and
$w^{2}_{\wedge}(\mathcal{D}(\left\|\cdot\right\|_{1};\bm{z}_{\ell^{\smash{1}}}^{i}))$.
Our findings are summarized in the following:

  1. (i)

The convex program ($\text{BP}_{\smash{\eta=0}}^{\text{\smash{coef}}}$) obeys
a sharp phase transition in the number of measurements $m$: Recovery of a
coefficient vector fails if $m$ is below a certain threshold and succeeds with
overwhelming probability once a small transition region is surpassed. This
observation could have been anticipated, given for instance the works [ALMT14,
Tro15]. However, note that the product structure of the matrix $\bm{A}\bm{D}$
in ($\text{BP}_{\smash{\eta=0}}^{\text{\smash{coef}}}$) does not allow for a
direct application of these results.

  2. (ii)

The quantity
$w^{2}_{\wedge}(\bm{D}\cdot\mathcal{D}(\left\|\cdot\right\|_{1};\bm{z}_{\ell^{\smash{1}}}))$
accurately describes the sampling rate of
($\text{BP}_{\smash{\eta=0}}^{\text{\smash{coef}}}$). Indeed, in all four
simulation settings of Figure 6, the phase transition occurs near the
estimated conic mean width of
$\bm{D}\cdot\mathcal{D}_{\wedge}(\left\|\cdot\right\|_{1};\bm{z}_{\ell^{\smash{1}}}^{i})$,
as predicted by Theorem 3.6.

  3. (iii)

In contrast,
$w^{2}_{\wedge}(\mathcal{D}(\left\|\cdot\right\|_{1};\bm{z}_{\ell^{\smash{1}}}))$
does not describe the sampling rate of
($\text{BP}_{\smash{\eta=0}}^{\text{\smash{coef}}}$), in general. Indeed,
$w^{2}_{\wedge}(\bm{D}\cdot\mathcal{D}(\left\|\cdot\right\|_{1};\bm{z}_{\ell^{\smash{1}}}^{2}))\ll
w^{2}_{\wedge}(\mathcal{D}(\left\|\cdot\right\|_{1};\bm{z}_{\ell^{\smash{1}}}^{2}))$
and
$w^{2}_{\wedge}(\bm{D}\cdot\mathcal{D}(\left\|\cdot\right\|_{1};\bm{z}_{\ell^{\smash{1}}}^{4}))\gg
w^{2}_{\wedge}(\mathcal{D}(\left\|\cdot\right\|_{1};\bm{z}_{\ell^{\smash{1}}}^{4}))$;
see Subfigure 6(d) and 6(j), respectively.

  4. (iv)

For two minimal $\ell^{1}$-representations
$\bm{z}_{\ell^{\smash{1}}}^{1},\bm{z}_{\ell^{\smash{1}}}^{2}$ with the same
sparsity, but with different supports, the quantities
$w^{2}_{\wedge}(\bm{D}\cdot\mathcal{D}(\left\|\cdot\right\|_{1};\bm{z}_{\ell^{\smash{1}}}^{1}))$
and
$w^{2}_{\wedge}(\bm{D}\cdot\mathcal{D}(\left\|\cdot\right\|_{1};\bm{z}_{\ell^{\smash{1}}}^{2}))$
might differ significantly, while
$w^{2}_{\wedge}(\mathcal{D}(\left\|\cdot\right\|_{1};\bm{z}_{\ell^{\smash{1}}}^{1}))=w^{2}_{\wedge}(\mathcal{D}(\left\|\cdot\right\|_{1};\bm{z}_{\ell^{\smash{1}}}^{2}))$;
see Subfigures 6(a) and 6(d). Hence, sparsity alone does not appear to be a
good proxy for the sampling complexity of
($\text{BP}_{\smash{\eta=0}}^{\text{\smash{coef}}}$). A refined understanding
of coefficient recovery requires a theory that is non-uniform across the class
of all $s$-sparse signals.

  5. (v)

The local condition number $\kappa_{{\bm{D},\bm{z}_{\ell^{\smash{1}}}}}$ might
explode, which often renders a condition bound as in Proposition 4.3 unusable.
Indeed, we report upper bounds for
$\smash{\lambda_{\text{min}}\left(\bm{D};\mathcal{D}_{\wedge}(\left\|\cdot\right\|_{1},\bm{z}_{\ell^{\smash{1}}}^{\smash{i}})\right)}$
in the first column of Figure 6. Since the norms of each dictionary are well
controlled, this quantity is responsible for the large values of the local
condition number.

(a)

(b)

(c)

(d)

(e)

(f)

(g)

(h)

(i)

(j)

(k)

(l)

Figure 6: Phase transitions of coefficient recovery by solving
($\text{BP}_{\smash{\eta=0}}^{\text{\smash{coef}}}$). Empirical success rates
and other key figures are reported in the first column, where we use the
notation
$\mathcal{D}=\mathcal{D}(\left\|\cdot\right\|_{1},\bm{z}_{\ell^{\smash{1}}}^{\smash{i}})$.
The coefficient vectors $\bm{z}_{\ell^{\smash{1}}}^{i}$ that are used in each
experiment are shown in the third column. The associated signal vectors
$\bm{x}_{i}=\bm{D}\bm{z}_{\ell^{\smash{1}}}^{\smash{i}}$ are displayed in the
second column. The first two rows are relying on a redundant Haar wavelet
frame, the third row is based on a Gaussian random matrix and the last row is
using a dictionary inspired by super-resolution.

###  5.2 Sampling Rates for Signal Recovery

For the investigation of signal recovery via
($\text{BP}_{\smash{\eta=0}}^{\text{\smash{sig}}}$), we also create phase
transition plots by running Experiment 5.1 for different dictionary and signal
combinations. Note that we also compute and store the signal error
$\|\bm{x}_{i}-\hat{\bm{x}}\|_{2}=\|\bm{D}\bm{z}_{\ell^{\smash{1}}}^{\smash{{i}}}-\bm{D}\hat{\bm{z}}\|_{2}$
in the third step of the experiment (in addition to
$\|\bm{z}_{\ell^{\smash{1}}}^{\smash{{i}}}-\hat{\bm{z}}\|_{2}$). Recovery is
declared successful if $\left\|\bm{x}_{i}-\hat{\bm{x}}\right\|_{2}<10^{-5}$.

##### Simulation Settings

Our first two examples are based on the same Haar wavelet system with 3
decomposition levels that is used in Section 5.1. The first signal is
constructed by defining a coefficient vector $\bm{z}_{1}\in\mathbb{R}^{1024}$
with a random support set of cardinality $s=35$ and random coefficients; see
Subfigure 7(j) for a visualization of $\bm{z}_{1}$ and Subfigure 7(d) for the
resulting signal $\bm{x}_{1}=\bm{D}_{\texttt{Haar}}\cdot\bm{z}_{1}$. In order
to apply the result of Theorem 3.8, we compute a minimal
$\ell^{1}$-representer $\bm{z}_{\ell^{\smash{1}}}^{\smash{1}}\in
Z_{\ell^{\smash{1}}}$ of $\bm{x}_{1}$; see Subfigure 7(g). The second
coefficient vector $\bm{z}_{2}$ is created by defining two contiguous blocks
of non-zero coefficients in a lower frequency decomposition scale, again with
$s=35$; see Subfigure 7(k) for a plot of $\bm{z}_{2}$ and Subfigure 7(e) for
the resulting signal $\bm{x}_{2}=\bm{D}_{\texttt{Haar}}\cdot\bm{z}_{2}$. A
corresponding minimal $\ell^{1}$-representer
$\bm{z}_{\ell^{\smash{1}}}^{\smash{2}}\in Z_{\ell^{\smash{1}}}$ of
$\bm{x}_{2}$ is shown in Subfigure 7(h).

Finally, for the third setup we are choosing a simple example in 2D. In order
to keep the computational burden manageable, we restrict ourselves to a
$28\times 28$-dimensional digit from the MNIST data set [LBBH98], i.e., the
vectorized image is of size $n=28^{2}=784$. As a sparsifying system we utilize
a dictionary that is based on the 2D discrete cosine transform (dct-2). It
makes use of Matlab’s standard dct-2 transform as convolution filters on
$3\times 3$ patches. The resulting operator is denoted by
$\bm{D}=\bm{D}_{\text{dct-2}}\in\mathbb{R}^{n\times 9n}$, i.e., $d=9n$. Note
that such a convolution sparsity model is frequently used in the literature,
in particular also with learned filters, e.g., see _convolutional sparse
coding_ in [BEL13]. Although the dct-2 filters might not be a perfect match
for MNIST digits, we consider them as a classical representative that is well
suited to demonstrate the predictive power of our results. In order to
construct a suitable sparse representation $\bm{z}_{3}\in\mathbb{R}^{d}$ of an
arbitrarily picked digit in the database, we make use of the orthogonal
matching pursuit algorithm [PRK93]; see Subfigure 7(l) for a visualization of
$\bm{z}_{3}$. The resulting digit
$\bm{x}_{3}=\bm{D}_{\text{dct-2}}\cdot\bm{z}_{3}$ is displayed in Figure 7(f).
A minimal $\ell^{1}$-representer $\bm{z}_{\ell^{\smash{1}}}^{\smash{3}}$,
which is needed to apply Theorem 3.8, is shown in Subfigure 7(i).

##### Results

Our conclusions on the numerical experiments shown in Figure 7 are reported in
the following:

  1. (vi)

The convex program ($\text{BP}_{\smash{\eta=0}}^{\text{\smash{sig}}}$) obeys a
sharp phase transition in the number of measurements. Due to the equivalent,
gauge-based reformulation (3.1) of
($\text{BP}_{\smash{\eta=0}}^{\text{\smash{sig}}}$), this observation is
predicted by the works [ALMT14, Tro15]. However, a recovery of a coefficient
representation via solving
($\text{BP}_{\smash{\eta=0}}^{\text{\smash{coef}}}$) is impossible in all
three examples, even for $m=n$.

  2. (vii)

For any $\bm{z}_{\ell^{\smash{1}}}\in Z_{\ell^{\smash{1}}}$, the conic mean
width
$w^{2}_{\wedge}(\bm{D}\cdot\mathcal{D}(\left\|\cdot\right\|_{1};\bm{z}_{\ell^{\smash{1}}}))$
accurately describes the sampling rate of
($\text{BP}_{\smash{\eta=0}}^{\text{\smash{sig}}}$), as predicted by Theorem
3.8. Indeed, in all three cases of Figure 7, the estimated
$w^{2}_{\wedge}(\bm{D}\cdot\mathcal{D}(\left\|\cdot\right\|_{1};\bm{z}_{\ell^{\smash{1}}}^{{i}}))$
matches precisely the 50% recovery rate.

  3. (viii)

In contrast, for any other sparse representation $\bm{z}\not\in
Z_{\ell^{\smash{1}}}$, the conic width
${w^{2}_{\wedge}(\bm{D}\cdot\mathcal{D}(\left\|\cdot\right\|_{1};\bm{z}))}$
does not describe the sampling rate of
($\text{BP}_{\smash{\eta=0}}^{\text{\smash{sig}}}$), in general. Indeed,
observe that we have
$w^{2}_{\wedge}(\bm{D}\cdot\mathcal{D}(\left\|\cdot\right\|_{1};\bm{z}_{i}))\approx
n$ in all three examples. Also note that
$\left\|\bm{z}_{1}\right\|_{0}=35=\left\|\bm{z}_{2}\right\|_{0}$, however, the
locations of the phase transitions deviate considerably. Similarly, although
$\|\bm{z}_{\ell^{\smash{1}}}^{{1}}\|_{0}<\|\bm{z}_{\ell^{\smash{1}}}^{{2}}\|_{0}$,
we have that
$w^{2}_{\wedge}(\bm{D}\cdot\mathcal{D}(\left\|\cdot\right\|_{1};\bm{z}_{\ell^{\smash{1}}}^{\smash{1}}))>w^{2}_{\wedge}(\bm{D}\cdot\mathcal{D}(\left\|\cdot\right\|_{1};\bm{z}_{\ell^{\smash{1}}}^{\smash{2}}))$.
This observation is yet another indication that sparsity alone is not a good
proxy for the sampling rate of $\ell^{\smash{1}}$-synthesis, in general.

###  5.3 Creating a “Full” Phase Transition

Let us now focus on the phase transition plots shown in Figure 1. Up to now,
we have only considered one specific signal at a time. However, it is also of
interest to assess the quality of our results if the “complexity” of the
underlying signals is varied. In the classical situation of $\bm{D}$ being an
ONB, the location of the phase transition is entirely determined by the
sparsity of the underlying signal. Hence, it is a natural choice to create
phase transitions over the sparsity, as it is for instance done in [ALMT14].
Recalling Claims (iv) and (viii), it might appear odd to do the same in the
case of a redundant dictionary. However, as the result of Figure 1 shows, if
the support is chosen uniformly at random, sparsity is still a somewhat
reasonable proxy for the sampling rate. Indeed, these plots are created by
running Experiment 5.2 with
$\bm{D}=\bm{D}_{\texttt{Haar}}\in\mathbb{R}^{256\times 1024}$, maximal
sparsity $s_{0}=125$ and displaying the empirical success rates of coefficient
and signal recovery, respectively. Additionally the dotted line shows the
averaged conic mean width values
$w^{2}_{\wedge}(\bm{D}\cdot\mathcal{D}(\left\|\cdot\right\|_{1};\bm{z}_{\ell^{\smash{1}}}))$.

######  Experiment 5.2 (Phase transition of Figure 1)

Input: Dictionary $\bm{D}\in\mathbb{R}^{n\times d}$, maximal sparsity
$s_{0}\in[n]$.

Compute: Repeat the following procedure $500$ times for each
$s\in\\{1,\dots,s_{0}\\}$:

  * $\blacktriangleright$

Select a set $S\subset[n]$ uniformly at random with $\\#S=s$. Then draw a
standard Gaussian random vector $\bm{c}\in\mathbb{R}^{s}$ and define
$\bm{z}_{0}$ by setting $(\bm{z}_{0})_{S}=\bm{c}$ and
$(\bm{z}_{0})_{S^{c}}=\bm{0}$.

  * $\blacktriangleright$

Define the signal $\bm{x}_{0}=\bm{D}\bm{z}_{0}$ and compute a minimal
$\ell^{1}$-representation $\bm{z}_{\ell^{\smash{1}}}\in Z_{\ell^{\smash{1}}}$
of $\bm{x}_{0}$. Compute the conic mean width
$w^{2}_{\wedge}(\bm{D}\cdot\mathcal{D}(\left\|\cdot\right\|_{1};\bm{z}_{\ell^{\smash{1}}}))$.

  * $\blacktriangleright$

Run Experiment 5.1 with $\bm{D}$ and $\bm{z}_{\ell^{\smash{1}}}$ as input,
where the number of repetitions is lowered to 5. In the third step,
coefficient/signal recovery is declared successful if
$\left\|\bm{z}_{\ell^{\smash{1}}}-\hat{\bm{z}}\right\|_{2}<10^{-5}$ or if
$\left\|\bm{D}\bm{z}_{\ell^{\smash{1}}}-\hat{\bm{x}}\right\|_{2}=\left\|\bm{x}_{0}-\bm{D}\hat{\bm{z}}\right\|_{2}<10^{-5}$,
respectively.

First note, that the averaged values of the conic mean width perfectly match
the center of the phase transition
of($\text{BP}_{\smash{\eta=0}}^{\text{\smash{sig}}}$) in Subfigure 1(b), as it
is predicted by Theorem 3.8. However, observe that for sparsity values between
$s\approx 20$ and $s\approx 80$ the transition region is spread out in the
vertical direction, cf. [ALMT14]. This phenomenon can be related to Claim
(viii): Given that sparsity alone is not a good proxy for the sample
complexity of ($\text{BP}_{\smash{\eta=0}}^{\text{\smash{sig}}}$), averaging
over different instances with the same sparsity necessarily results in a
smeared out transition area.

Regarding the phase transition in Subfigure 1(a), we observe that the location
of the phase transition is also determined by
$w^{2}_{\wedge}(\bm{D}\cdot\mathcal{D}(\left\|\cdot\right\|_{1};\bm{z}_{\ell^{\smash{1}}}))$;
provided that coefficient recovery is possible, i.e., if
$\lambda_{\text{min}}\left(\bm{D};\mathcal{D}_{\wedge}(\left\|\cdot\right\|_{1};\bm{z}_{\ell^{\smash{1}}})\right)>0$.
For sparsity values $s\geq 50$, recovery of coefficients appears to be
impossible, whereas signal and coefficient recovery seems to be equivalent for
very small sparsity values (i.e., $s\leq 5$). The interval in between forms a
transition region, in which coefficient recovery becomes gradually less
likely. We suspect that with more repetitions in Experiment 5.2, the empirical
success rates on this interval would eventually smooth out.

We conclude that:

  1. (ix)

Whether
$\lambda_{\text{min}}\left(\bm{D};\mathcal{D}_{\wedge}(\left\|\cdot\right\|_{1};\bm{z}_{\ell^{\smash{1}}})\right)\neq
0$, i.e., whether coefficient recovery is possible, is again a property that
is non-uniform in the sparsity of $\bm{z}_{\ell^{\smash{1}}}$.

(a)

(b)

(c)

(d)

(e)

(f)

(g)

(h)

(i)

(j)

(k)

(l)

Figure 7: Phase transitions of signal recovery by solving
($\text{BP}_{\smash{\eta=0}}^{\text{\smash{sig}}}$). Empirical success rates
and other key figures are reported in the first row, where we use the notation
$\mathcal{D}_{1}=\mathcal{D}(\left\|\cdot\right\|_{1},\bm{z}_{\ell^{\smash{1}}}^{\smash{i}})$
and $\mathcal{D}_{0}=\mathcal{D}(\left\|\cdot\right\|_{1},\bm{z}_{i})$. The
signals $\bm{x}_{i}$ that are used in each experiment are shown in the second
row. The associated minimal $\ell^{1}$-representers
$\bm{z}_{\ell^{\smash{1}}}^{\smash{i}}$ are displayed in the third row and the
original coefficient representations $\bm{z}_{i}$ are shown in the fourth row.
The first two columns are relying on a redundant Haar wavelet frame and the
third column is based on the dct-2. Note that in all three examples,
coefficient recovery is not possible since
$\smash{\lambda_{\text{min}}\left(\bm{D};\mathcal{D}_{\wedge}(\left\|\cdot\right\|_{1},\bm{z}_{\ell^{\smash{1}}}^{\smash{i}})\right)=0}$.

###  5.4 Robustness to Noise

The purpose of this last numerical simulation is to analyze coefficient and
signal recovery with respect to robustness to measurement noise. To that end,
we run Experiment 5.3 for different setups, which are reported below.

######  Experiment 5.3 (Robustness to Measurement Noise)

Input: Dictionary $\bm{D}\in\mathbb{R}^{n\times d}$, number of measurements
$m$, minimal $\ell^{1}$-representation $\bm{z}_{\ell^{\smash{1}}}$ of the
signal $\bm{x}_{0}\in\mathbb{R}^{n}$, range of noise levels $H$.

Compute: Repeat the following procedure $100$ times for every $\eta\in H$:

  * $\blacktriangleright$

Draw a standard i.i.d. Gaussian random matrix $\bm{A}\in\mathbb{R}^{m\times
n}$ and determine the noisy measurement vector
$\bm{y}=\bm{A}\bm{x}_{0}+\eta\cdot\bm{e}$, where
$\left\|\bm{e}\right\|_{2}=1$.

  * $\blacktriangleright$

Solve the program ($\text{BP}_{\eta}^{\text{\smash{coef}}}$) to obtain an
estimator $\hat{\bm{z}}\in\mathbb{R}^{d}$.

  * $\blacktriangleright$

Compute and store the recovery errors
$\left\|\bm{z}_{\ell^{\smash{1}}}-\hat{\bm{z}}\right\|_{2}$ and
$\left\|\bm{x}_{0}-\hat{\bm{x}}\right\|_{2}=\left\|\bm{D}\bm{z}_{\ell^{\smash{1}}}-\bm{D}\hat{\bm{z}}\right\|_{2}$.

##### Simulation settings

First, we choose the same dictionary and signal combination as in Section 5.1
and restrict the noise level to $H=\left\\{0,0.05,0.1,0.15,\dots,1\right\\}$.
Furthermore, we consider the 1D examples of Section 5.2, together with the
noise range $H=\left\\{0,0.005,0.01,\dots,0.1\right\\}$. Recall that the
difference of these two setups is that
$\lambda_{\text{min}}\left(\bm{D};\mathcal{D}_{\wedge}(\left\|\cdot\right\|_{1},\bm{z}_{\ell^{\smash{1}}}^{\smash{i}})\right)>0$
in the first case, whereas
$\lambda_{\text{min}}\left(\bm{D};\mathcal{D}_{\wedge}(\left\|\cdot\right\|_{1},\bm{z}_{\ell^{\smash{1}}}^{\smash{i}})\right)=0$
in the second case. In all experiments, we roughly pick the number of
measurements as $m\approx
w^{2}_{\wedge}(\bm{D}\cdot\mathcal{D}(\left\|\cdot\right\|_{1};\bm{z}_{\ell^{\smash{1}}}^{\smash{i}}))+40$
to ensure that Theorem 3.6 (or Theorem 3.8, respectively) is applicable. The
averaged coefficient and signal recovery errors are displayed in Figure 8,
together with the theoretical upper bound on the signal error of Equation
(3.6). Note that it is not possible to show the corresponding error bound for
coefficient recovery. In the first set of examples, we do not have access to
$\lambda_{\text{min}}\left(\bm{D};\mathcal{D}_{\wedge}(\left\|\cdot\right\|_{1},\bm{z}_{\ell^{\smash{1}}}^{\smash{i}})\right)$
and in the last two cases,
$\lambda_{\text{min}}\left(\bm{D};\mathcal{D}_{\wedge}(\left\|\cdot\right\|_{1},\bm{z}_{\ell^{\smash{1}}}^{\smash{i}})\right)=0$
and therefore Theorem 3.6 is not applicable. Nevertheless, it is possible to
obtain an upper bound for the latter quantity, as outlined in the Appendix D.
If $\bm{D}=\bm{D}_{\texttt{rand}}$, it is additionally possible to use the
result on minimum conic singular values of Gaussian matrices to get a lower
bound with high probability [Tro15, Proposition 3.3].

##### Results

We summarize the findings of the results shown in Figure 8 below:

  1. (x)

If the number of measurements exceeds the sampling rate in Theorem 3.8, signal
recovery via solving the Program ($\text{BP}_{\eta}^{\text{\smash{sig}}}$) is
robust to measurement noise. This phenomenon holds true without any further
assumptions. Indeed, observe that in all simulations of Figure 8, the signal
error $\left\|\bm{x}_{0}-\hat{\bm{x}}\right\|$ lies below its theoretical
upper bound of Equation (3.6).

  2. (xi)

If $\bm{z}_{\ell^{\smash{1}}}$ is the unique minimal $\ell^{1}$-representation
of $\bm{x}_{0}$ (i.e., if
$\lambda_{\text{min}}\left(\bm{D};\mathcal{D}_{\wedge}(\left\|\cdot\right\|_{1},\bm{z}_{\ell^{\smash{1}}})\right)>0$)
and if the number of measurements exceeds the sampling rate in Theorem 3.6, it
is possible to robustly recovery $\bm{z}_{\ell^{\smash{1}}}$. However, in
contrast to signal recovery, the robustness is influenced by the “stability”
of the minimal $\ell^{1}$-representation of $\bm{z}_{\ell^{\smash{1}}}$ in
$\bm{D}$, i.e., by the value of
$\lambda_{\text{min}}\left(\bm{D};\mathcal{D}_{\wedge}(\left\|\cdot\right\|_{1},\bm{z}_{\ell^{\smash{1}}})\right)$
in the error bound (3.4). Indeed, it is possible that the signal $\bm{x}_{0}$