33footnotetext: Contact emails for paper<EMAIL_ADDRESS><EMAIL_ADDRESS> This publication is based on work
supported by the Alan Turing Institute under the EPSRC grant EP/N510129/1 and
the Ana Leaf Foundation. The authors thank David L. Donoho, Vardan Papyan for
motivating this work, Hemant Tyagi for his helpful feedback and Jeremias Sulam
for stimulating discussions.

# Towards an understanding of CNNs: analysing the recovery of activation
pathways via Deep Convolutional Sparse Coding

Michael Murray111Mathematical Institute, University of Oxford 222The Alan
Turing Institute , Jared Tanner 11footnotemark: 1 22footnotemark: 2

###### Abstract

Deep Convolutional Sparse Coding (D-CSC) is a framework reminiscent of deep
convolutional neural nets (DCNN), but by omitting the learning of the
dictionaries one can more transparently analyse the role of the activation
function and its ability to recover activation paths through the layers.
Papyan, Romano, and Elad conducted an analysis of such an architecture [1],
demonstrated the relationship with DCNNs and proved conditions under which a
D-CSC is guaranteed to recover activation paths. A technical innovation of
their work highlights that one can view the efficacy of the ReLU nonlinear
activation function of a DCNN through a new variant of the tensor’s sparsity,
referred to as stripe-sparsity.Using this they proved that representations
with an activation density proportional to the ambient dimension of the data
are recoverable. We extend their uniform guarantees to a modified model and
prove that with high probability the true activation is typically possible to
recover for a greater density of activations per layer. Our extension follows
from incorporating the prior work on one step thresholding by Schnass and
Vandergheynst [2] into the appropriately modified architecture of [1].

Keywords: Deep Learning, Deep Convolutional Neural Networks, Sparse Coding,
Deep Convolutional Sparse Coding, Rademacher Concentration

##  1 Introduction

Ever since the arrival of AlexNet (Krizhevsky et al, [3]) in 2012, Deep
Convolutional Neural Networks (DCNNs) have been the state of the art technique
for tackling many tasks in computer vision. The success of DCNNs is not only
limited to computer vision, achieving excellent results in a host of other
application areas such as Natural Language Processing (NLP) (Kim et al [4])
and Speech Recognition (Zhang et al )[5]). However, although their empirical
success and practical usefulness is undeniable, exactly why they are so
successful remains somewhat of a mystery. A large number of open questions
remain; for instance (and to consider just a few), how are DCNNs able to avoid
the curse of dimensionality during training? Why is training via gradient
based methods so effective? How do DCNNs achieve their invariance properties?
How should we design a neural network for a given task and why do they
generalise so well? In recent years, a large number of researchers have been
working to better understand DCNNs and we now highlight just a few
contributions in the context of the questions above. With regard to avoiding
the curse of dimensionality, Mhaskar and Poggio analysed the approximation
capabilites of shallow vs. deep networks for compositional functions, proving
that DCNNs, for the same level of approximation accuracy, require an
exponentially lower number of training points compared with shallow networks
[6]. The works of Pennington et al [7], Poggio [8], Freeman and Bruna [9]
indicate that although the loss functions of neural networks in general are
non-convex, for sufficiently large networks most local minima are in fact
close to being global minima, furthermore many of these global minima are flat
and degenerate. Additionally Haefele and Vidal in [10] where able to prove,
for a certain form of parallelised network architecture, that if the size of
the network is sufficiently large then local descent can reach a global
minimizer from any initialisation. Bruna and Mallat [11] analysed the
invariance properties of DCNNs, showing that invariance can also be achieved
by a wavelet based approach they termed the Scattering Transform. Wiatowski et
al [12] built on this work to specify the number of layers this approach
requires to capture most of an input signal’s energy, providing some insight
and potential guidelines for more general network architecture design. Finally
in regard to understanding how DCNNs generalise, Zhang et al [13]
experimentally demonstrated that DCNNs can fit random data with ease,
suggesting gaps in current theories concerning regularisation. In this paper
we build on another work by Papyan et al [1]. In this paper they seek to
answer questions concerning the role of the forward pass algorithm and of the
activation pathways (the pattern of nodes at each layer that are activated by
the forward pass). Inspired by the observation that the ReLU activation
function is a sparsifying operator, their paper connects deep learning with
the field of compressed sensing, interpreting the forward pass algorithm as
approximately solving a sequence of sparse coding problems. In doing so they
are able to leverage the tools of compressed sensing to analyse under which
circumstances an activation path is recovered.

ReLUs are a highly popular choice of activation function, playing a role in
most DCNN implementations. Indeed, it has been posited that the enforcement of
sparsity through ReLU functions may be one of the key ingredients behind
certain DCNNs’ effectiveness at developing composite representations at depth
[14]. By omitting the learning of the dictionaries in DCNNs, one can more
transparently analyse the role of the forward pass algorithm and its ability
to recover activation paths through the layers. Papyan et al [1] propose a
deep convolutional sparse coding (D-CSC) model with this aim and use
techniques from sparse coding to prove conditions under which a DCNN is
guaranteed to activate the desired nodes in a given layer. This analysis
however is based upon pessimistic worst case assumptions, which limit the
applicability of these results. In this paper we aim to address this issue,
extending from uniform guarantees to probabilistic bounds. The outline of this
paper is as follows. In Section 2 we will review the D-CSC model and the
conditions for uniform recovery of activation pathways, presented in [1]. In
Section 3 we present probabilistic bounds for the recovery of activation
pathways and provide a proof of this result. Finally, in Section 4 we conclude
by providing a summary and some practical implications of our results.

##  2 Background

###  2.1 A quick overview of notation

Before proceeding we define the following measures which we will use
extensively.

  * •

$\|\textbf{x}\|_{\alpha,\infty}^{P^{(l)}}\triangleq\max_{i}\|P_{i}^{(l)}\textbf{x}\|_{\alpha}$
where $P_{i}^{(l)}$, the patch operator, takes $m_{l}$ consecutive elements of
x (with wraparound) starting at $x_{i}$ (see [1] for further details). In this
paper we will only consider $\alpha\in\\{0,2\\}$, hence $\|\cdot\|_{\alpha}$
refers to the standard $l_{2}$ norm when $\alpha=2$, and a function counting
the number of non-zeros in the argument vector when $\alpha=0$.

  * •

$\|\textbf{x}\|_{\alpha,\infty}^{Q^{(l)}}\triangleq\max_{i}\|Q_{i}^{(l)}\textbf{x}\|_{\alpha}$
where $Q_{i}^{(l)}$, the stripe operator, takes
$\lfloor{((2(m_{l}/s_{l})-1)n_{l})}\rfloor$ consecutive elements of x (with
wraparound) starting at $x_{i}$ (see [1] for further details). As before we
will only consider $\alpha\in\\{0,2\\}$, hence $\|\cdot\|_{\alpha}$ refers to
the standard $l_{2}$ norm when $\alpha=2$, and a function counting the number
of non-zeros in the argument vector when $\alpha=0$.

  * •

$\|\textbf{X}^{(l)}\|_{\alpha,\infty}^{Q^{(l)}}\triangleq\max_{j}\|\textbf{x}_{j}\|_{\alpha,\infty}^{Q^{(l)}}$,
which is simply the maximum of the set of measures (defined above) on the
columns of $\textbf{X}^{(l)}$.

###  2.2 The D-CSC model - interpreting the forward pass algorithm of a CNN as
a sequence of sparse coding problems

To interpret the forward pass as solving a sequence of sparse coding problems
we firstly model the data in the classic compressed sensing setup. Denoting
the matrix containing our data as $\textbf{X}^{(0)}$, suppose that it is
formed from a linear combination of columns of a convolutional matrix A (a
convolutional matrix is a banded circular matrix created by shifting a locally
supported matrix across all spatial locations, see [15] and [1] for more
details). This can be expressed as
$\textbf{X}^{(0)}=\textbf{A}\textbf{X}^{(L)}$ where $\textbf{X}^{(L)}$ denotes
the matrix containing the sparse codes of our data (the reasons for this
particular choice of notation shall become clear). For the particulars and
details concerning convolutional sparse coding we refer the reader to [15].
Suppose now that A can in fact be factorized as a product of convolutional
matrices, $\textbf{A}=\Pi_{l=1}^{L}\textbf{A}^{(l)}$. To make the connection
to DCNNs consider examining the representation of $\textbf{X}^{(0)}$ at a
different level of the factorisation other than $L$. To explain through an
example denote
$\textbf{X}^{(l)}=\Pi_{j=l+1}^{L}\textbf{A}^{(j)}\textbf{X}^{(L)}$, then
$\textbf{X}^{(0)}=\Pi_{j=l}^{l}\textbf{A}^{(j)}\textbf{X}^{(l)}$. We define
$\textbf{X}^{(l)}$ as the latent representation of $\textbf{X}^{(0)}$ at layer
l. If we consider starting at the deepest representation and work backwards by
applying the matrix factors of A sequentially and in order, then expressing
each representation in terms of the next we formulate the model

$\begin{split}\textbf{X}^{(L-1)}&=\textbf{A}^{(L)}\textbf{D}^{(L)}\textbf{X}^{(L)}\\\
&...\\\ \textbf{X}^{(1)}&=\textbf{A}^{(2)}\textbf{D}^{(2)}\textbf{X}^{(2)}\\\
\textbf{X}^{(0)}&=\textbf{A}^{(1)}\textbf{D}^{(1)}\textbf{X}^{(1)}.\end{split}$
(2.1)

If we additionally impose certain sparsity constraints on the representations
at each layer then this model reduces to the $DCP_{\lambda}$ model proposed in
[1] when $\textbf{D}^{(l)}=\textbf{I}$ $\forall l$. The reason for the
inclusion $\textbf{D}^{(l)}$ at each layer shall become clear in Section 3. We
define the reverse pass of the D-CSC model as the generation of each
$\textbf{X}^{(l)}$ for $l=L-1,L-2...0$ starting at the deepest layer,
$\textbf{X}^{(L)}$. That is, given $\\{\textbf{A}^{(l)}\\}_{l=1}^{L}$,
$\\{\textbf{D}^{(l)}\\}_{l=1}^{L}$ and $\textbf{X}^{(L)}$, we sequentially
generate $\textbf{X}^{(l)}$ as in (2.1). For clarity we now describe each
variable in more detail.

  * •

$\textbf{X}^{(l)}\in\mathbb{R}^{n_{l}M\times d}$ is a matrix containing the
latent representation of the data at layer $l$, with each of the $d$ columns a
data point of dimension $M$. To be clear
$\textbf{X}^{(l)}=[\textbf{x}_{1}^{(l)}\ \textbf{x}_{2}^{(l)}\ ...\
\textbf{x}_{d}^{(l)}]$ where throughout lower case bold letters will denote
the columns of their respective capitalised bold letter denoted matrices. We
furthermore assume that there exists scalars $\\{S_{l}\\}_{l=1}^{L}$ such that
$\|\textbf{X}^{(l)}\|_{0,\infty}^{Q^{(l)}}\leq S_{l}$ for all $l$.

  * •

$\textbf{D}^{(l)}\sim\mathbb{B}^{n_{l}M\times n_{l}M}$ is a sample drawn from
the distribution of random, diagonal matrices whose diagonal components are
independent Rademacher random variables. To be clear, these are square
matrices with dimension $n_{l}M$, whose off diagonal elements are all zero and
whose diagonal elements are either $1$ or $-1$ with probability $0.5$.

  * •

$\textbf{A}^{(l)}\in\mathbb{R}^{(n_{l-1})M\times n_{l}M}$ is the transpose of
the weight matrix mapping between layers $l-1$ and $l$. This matrix has a
convolutional structure (described in [15] and [1]), is circular and banded,
and is created by shifting a local dictionary
$\textbf{A}_{Local}^{(l)}\in\mathbb{R}^{m_{l}\times n_{l}}$ across all spatial
locations. For $l\geq 2$ there is a stride between each spatially shifted
$\textbf{A}^{(l)}$ which we denote $s_{l}$, in [1] $s_{l}=n_{l-1}$. The
columns of $\textbf{A}^{(l)}$ have unit $\ell_{2}$ norm and as before we
denote the columns of the matrix as $\textbf{A}^{(l)}=[\textbf{a}_{1}^{(l)}\
\textbf{a}_{2}^{(l)}\ ...\ \textbf{a}_{d}^{(l)}]$.

Suppose that we know $\\{\textbf{A}^{(l)}\\}_{l=1}^{L}$, have access to
$\\{\textbf{D}^{(l)}\\}_{l=1}^{L}$ and are given $\hat{\textbf{X}}^{(0)}$,
where

$\begin{split}\hat{\textbf{X}}^{(0)}&=\textbf{X}^{(0)}+\textbf{V}^{(0)}\\\
&=\textbf{A}^{(1)}\textbf{D}^{(1)}\textbf{X}^{(1)}+\textbf{V}^{(0)}.\end{split}$

$\textbf{V}^{(0)}$ is the model error matrix that arises since our data may
only approximatly belong to this model, i.e., the data may only approximatly
be represented as a linear combination of elements from the global dictionary
$\textbf{A}=\Pi_{l=1}^{L}\textbf{A}^{(l)}$. We shall consider the efficacy of
the forward pass of the D-CSC model to recover the hidden or latent
representations $\\{\textbf{X}^{(l)}\\}_{l=1}^{L}$ from
$\hat{\textbf{X}}^{(0)}$. Suppose we compute an estimate
$\hat{\textbf{X}}^{(1)}$ and define the corresponding estimation error with
regard to $\textbf{X}^{(1)}$ as $\textbf{V}^{(1)}$ so that
$\hat{\textbf{X}}^{(1)}=\textbf{X}^{(1)}+\textbf{V}^{(1)}$. Continuing in this
vein we can therefore define the following sequence of noisy sparse coding
problems which we solve, sequentially, to estimate the sparse representations
$\textbf{X}^{(l)}$ for $l=1,2,...L$.

$\begin{split}\hat{\textbf{X}}^{(0)}&=\textbf{A}^{(1)}\textbf{D}^{(1)}\textbf{X}^{(1)}+\textbf{V}^{(0)}\\\
\hat{\textbf{X}}^{(1)}&=\textbf{A}^{(2)}\textbf{D}^{(2)}\textbf{X}^{(2)}+\textbf{V}^{(1)}\\\
&...\\\
\hat{\textbf{X}}^{(L-1)}&=\textbf{A}^{(L)}\textbf{D}^{(L)}\textbf{X}^{(L)}+\textbf{V}^{(L-1)}.\end{split}$
(2.2)

Note that the error propogates between each layer since the estimate of the
sparse representation in the previous layer is fed into the next layer. Our
notation is clarified below.

  * •

$\hat{\textbf{X}}^{(0)}\in\mathbb{R}^{M\times d}$ is a matrix containing the
observed noisy data, with each of the $d$ columns representing a data point of
dimension $M$. As before, we denote the columns of the matrix as
$\hat{\textbf{X}}^{(0)}=[\hat{\textbf{x}}_{1}^{(0)}\hat{\textbf{x}}_{2}^{(0)}\
...\ \hat{\textbf{x}}_{d}^{(0)}]$.

  * •

$\hat{\textbf{X}}^{(l)}\in\mathbb{R}^{n_{l}M\times d}$ is a matrix containing
the noisy representation of the observed data $\hat{\textbf{X}}^{(0)}$ at
layer $l$. As before, we denote the columns of the matrix as
$\hat{\textbf{X}}^{(l)}=[\hat{\textbf{x}}_{1}^{(l)}\
\hat{\textbf{x}}_{2}^{(l)}\ ...\ \hat{\textbf{x}}_{d}^{(l)}]$.

  * •

$\textbf{V}^{(l)}\in\mathbb{R}^{n_{l}M\times d}$ is an unknown error matrix
$\textbf{V}^{(l)}=\hat{\textbf{X}}^{(l)}-\textbf{X}^{(l)}$ which we assume has
bounded energy satisfying
$\|\textbf{V}^{(l)}\|_{2,\infty}^{P^{(l)}}\leq\zeta_{l}$. As before, we denote
the columns as $\textbf{V}^{(l)}=[\textbf{v}_{1}^{(l)}\ \textbf{v}_{2}^{(l)}\
...\ \textbf{v}_{d}^{(l)}].$

  * •

$\textbf{D}^{(l)}$ are the same samples as in 2.1 used to generate the
representations at each layer.

Hopefully the connection between the D-CSC framework and DCNNs is now
apparent. To summarise, we can view the forward pass of a neural network as
solving the sequence of sparse coding problems defined in (2.2) with
$\hat{\textbf{X}}^{(0)}$ being the data we feed into our network and
$\hat{\textbf{X}}^{(l)}$ the estimate of the latent representation of the data
at layer $l$. To dispel any potential confusion, note that the forward
activation pattern at layer l refers to the support, i.e. the location of the
nonzero entries, of $\hat{\textbf{X}}^{(l)}$. The reverse activation pattern
at layer l refers to the support of $\textbf{X}^{(l)}$. Our aim is to derive
conditions for which the reverse and forward activation patterns coincide
across all layers. Defining the activation pathway as the sequence of
activations across all layers (e.g. the reverse activation pathway is
$\\{supp(\textbf{X}^{(l)})\\}_{l=1}^{L}$), we can summarise our goal as
attempting to understand when the forward and reverse activation pathways for
a given data point are the same, or at least are highly likely to be the same.
Assuming that we are able to recover the reverse activation pattern, we will
also aim to bound the error between the estimated and true representation at a
given layer.

###  2.3 Uniform guarantees for the recovery of activation pathways

In [1] Papyan, Romano, and Elad consider the
$\\{\hat{\textbf{X}}^{(l)}\\}_{l=1}^{L}$ obtained by applying a feed forward
algorithm to solve the sequence of sparse coding problems defined in 2.2 and
prove that this model admits a solution under certain sparsity constraints.
Their analysis relies heavily on the notion of the coherence of a dictionary,

$\mu(\textbf{A})=\max_{i\neq j}|\textbf{a}_{i}^{*}\textbf{a}_{j}|,$ (2.3)

where $\textbf{a}_{i}$ is the $i^{th}$ column of A. The main technical
innovations in [1] include how bounds from traditional sparse approximation
propagate through multiple layers, and also the aforementioned sparsity
measures used to ameliorate the limited lower bound on (2.3). This is often
observed for matrices with a convolutional structure as in the case of
$\textbf{A}^{(l)}$. In particular, the main results in [1] most relevant to
our extensions lets $\\{\textbf{X}^{(l)}\\}_{l=1}^{L}$ be a set of sparse
matrices consistent with Model (2.1). The activations in the presence of
noise, as in (2.2) are estimated recursively from the data matrix
$\hat{\textbf{X}}^{(0)}$ according to

$\hat{\textbf{X}}^{(l)}=Proj_{|supp(\cdot)|=k}\left((\textbf{A}^{(l)}\textbf{D}^{(l)})^{T}\hat{\textbf{X}}^{(l-1)}\right).$
(2.4)

for $l=1,2,\cdots L$ and in Papyan et al’s analysis
$\textbf{D}^{(l)}=\textbf{I}$ for all $l$ (note that in all our results that
follow we shall assume that $\textbf{D}^{(l)}$ are samples drawn from
distributions of Rademacher random matrices, as described in model 2.2).
$Proj_{|supp(\cdot)|=k}(\cdot)$ denotes a family of sparsifying operators that
sets all but $k$ entries of the each column of the matrix argument to 0. By
substituting $Proj_{|supp(\cdot)|=k}(\cdot)$ with a ReLU operator we obtain
the standard forward pass algorithm across a ReLU layer of a neural network
with $(\textbf{A}^{(l)}\textbf{D}^{(l)})^{T}$ the weight matrix between layer
$l$ and $l-1$. In what follows we will assume that
$Proj_{|supp(\cdot)|=k}(\cdot)$ refers to basic thresholding with the hard
thresholding operator [16]. To be clear, this operator keeps the $k$ largest
entries (in terms of absolute value) of each column of the argument matrix
unchanged while setting all other elements to zero.

Papyan et al prove 111Papyan et al’s analysis is wide-ranging, including
conditions under which the solution to Model (2.2) is unique. They also
consider a variety of thresholding operators such as soft and hard
thresholding as well as more advanced algorithms to compute
$\hat{\textbf{X}}^{(l)}$ from $\textbf{A}^{(l)}$ and
$\hat{\textbf{X}}^{(l-1)}$. We speak here only of a few of their
contributions., under worst case assumptions, that if the noise free data
satisfies a sparsity bound $\|\textbf{X}^{(l)}\|_{0,\infty}^{Q^{(l)}}\leq
S_{l}$ and $\|\textbf{V}^{(l)}\|_{2,\infty}^{P^{(l)}}\leq\zeta_{l}$ for some
sets of scalars $\\{S_{l}\\}_{l=1}^{L}$ and $\\{\zeta_{l}\\}_{l=1}^{L}$, then
so long as

$S_{l}<\frac{\mu^{(l)})^{-1}}{|X^{(l)}_{max}|}\left(\frac{1}{2}|X^{(l)}_{min}|-\zeta_{l}\right)+\frac{1}{2}$
(2.5)

the activation (or support) of $\hat{\textbf{X}}^{(l)}$ computed using 2.4 is
exactly the same as the activation of $\textbf{X}^{(l)}$. In other words, the
reverse activation pattern at layer $l$ is recovered. Note that we require
knowledge of the cardinality of the support at each layer. Here
$|X^{(l)}_{min}|$ and $|X^{(l)}_{max}|$ are the smallest and largest non-zeros
in $\textbf{X}^{(l)}$ respectively and note also that we have adopted the
shortened notation $\mu_{l}=\mu(\textbf{A}^{(l)})$.

##  3 An average case analysis of the D-CSC model

###  3.1 Probabilistic bound for the recovery of activation pathways

Notable in the sparsity bound (2.5) is the presence of $\mu_{l}$, which is the
factor that allows for a nontrivial $S_{l}$. Bounds of the form (2.5) are
prevalent in the theory of sparse approximation, see for instance [16, Chapter
5], where it is known [17] that for a generic matrix
$\textbf{B}\in\mathbb{R}^{m\times\gamma m}$ that
$\mu(\textbf{B})>m^{-1/2}\sqrt{1-\gamma^{-1}}$. This is colloquially referred
to as the square-root bottleneck in that $\mu^{-1}\sim m^{1/2}$. In many
applications, e.g. imaging, $m_{i}$ is typically not more than $7^{2}$ and
$n_{i}$ is typically about $2m_{i}$. Solving the sequence of sparse coding
problems in (2.2) has the additional challenge due to $\textbf{A}^{(l)}$ being
convolutional in structure. This can result in a large mutual coherence if the
stride between shifted versions of the local dictionaries
$\textbf{A}_{Local}^{(l)}$ is insufficient. As a result the proportionality of
the bound on the signal complexity, measured in terms of the number of
nonzeros, on $\mu_{l}^{-1}$ in (2.5) limits its ability to provide guarantees
in many practical situations.

It is well known from the work of Schnass and Vandergheynst [2] that in the
single layer context, if one introduces a randomized sign pattern then the
Rademacher concentration inequality can be used to derive bounds demonstrating
that the recovery of the correct activations is typically possible with the
sparsity bounds relaxed to depend on $\mu_{l}^{-2}$. Our main result is to
extend the techniques used in [2] to the multi-layer setting of [1]. In order
to do so we adapt Model (2.2) to include randomized sign patterns on the masks
of the network, or equivalently activations at the next layer. That is the
inclusion of the matrix $\textbf{D}^{(l)}$, a diagonal matrix whose diagonal
entries are independent Rademacher random variables as we have already
discussed. This matrix applies a random sign pattern to the columns of
$\textbf{A}^{(l)}$. Although this matrix is primarily an artifact necessary
for our analysis, it is interesting to note its connection with dropout, a
technique commonly used when training DCNNs in which a random set of nodes (or
columns of the weight matrix) are ignored in every batch. Indeed one can
tentatively interpret $\textbf{D}^{(l)}$ as a special form of dropout which
selects either the positive or negative signed column from a wider dictionary
that contains both. Under this adaption we are able to provide Theorem 1.

######  Theorem 1.

Let $\hat{\textbf{X}}^{(0)}$ be a data matrix consistent with Model (2.2) with
$\|\textbf{X}^{(l)}\|_{0,\infty}^{Q^{(l)}}\leq S_{l}$,
$\|\textbf{V}^{(l)}\|_{2,\infty}^{P^{(l)}}\leq\zeta_{l}$ for $l=0,\ldots,L-1$.
Suppose that we know the cardinality of the support of each column of
$\textbf{X}^{(l)}$ for $l=1,\ldots,L$ and that we calculate each column of
$\hat{\textbf{X}}^{(l)}$ independently using (2.4). Denote the event that the
location of the non-zeros in $\textbf{X}^{(l)}$ and $\hat{\textbf{X}}^{(l)}$
exactly coincide for $l=0,1,\ldots,L$, as $Z_{L}$, i.e., the event that the
reverse and forward activation pathways are the same. The probability that
this event doesn’t hold, $\bar{Z}_{L}$, has an upper bound

$P(\bar{Z}_{L})\leq
2dM\sum_{l=1}^{L}n_{l}\exp\left(-\frac{|X_{min}^{(l)}|^{2}}{8\left(|X_{max}^{(l)}|^{2}\mu_{l}^{2}S_{l}+\zeta_{l-1}^{2}\right)}\right).$
(3.1)

Furthermore when $Z_{L}$ does occur then for all $j$,

$\|\hat{\textbf{x}}_{j}^{(l)}-\textbf{x}_{j}^{(l)}\|_{2,\infty}^{P^{(l)}}\leq\zeta_{l}$
(3.2)

where

$\zeta_{l}=\sqrt{\|\hat{\textbf{X}}^{(l)}\|_{0,\infty}^{P^{(l)}}}\left(\mu_{l}(S_{l}-1)|X_{max}^{(l)}|+\zeta_{l-1}\right).$
(3.3)

A key implication of Theorem 1 is that the derived probability bound scales
proportional to $\mu_{l}^{-2}$ across a given layer, rather than
$\mu_{l}^{-1}$. To be precise, for a given representation
$\hat{\textbf{x}}^{(l-1)}$ and an arbitrary $\delta\in[0,1]$, then
$P(\bar{W}_{l})\leq\delta$ if

$S_{l}\leq\left(\frac{|x_{min}^{(l)}|^{2}}{8|x_{max}^{(l)}|^{2}\ln\left(\frac{2Mn_{l}}{\delta}\right)}-\frac{\zeta_{l-1}^{2}}{|x_{max}^{(l)}|^{2}}\right)\mu_{l}^{-2}$
(3.4)

is satisfied. For this theorem to be meaningful (since we require
$S_{l}\in\mathbb{Z}^{\geq 0}$) it is necessary that the noise satisfies

$\zeta_{l-1}<\frac{|x_{min}^{(l)}|}{\left(8\ln\left(\frac{2Mn_{l}}{\delta}\right)\right)^{1/2}}.$

###  3.2 Proof of Theorem 1

We develop the proof of Theorem 1 by first considering the failure to recover
the sparse representation of a single vector across a single layer (Lemma 1)
and then a single vector across multiple layers (Lemma 2).With these results
in place it is a simple step to prove Theorem 1. In what follows we will make
use of the following Rademacher concentration inequality.

######  Theorem 2 (Rademacher concentration [18]).

Let $\alpha$ be an arbitrary real vector and $\varepsilon$ a random vector
whose elements are independent random variables pulled from a Rademacher
distribution $\\{-1,1\\}$. Then for all $t\in\mathbb{R_{+}}$

$P\left(|\sum_{i}\varepsilon_{i}\alpha_{i}|>t\right)\leq
2\exp\left(-\frac{t^{2}}{2\|\alpha\|_{2}^{2}}\right).$ (3.5)

####  3.2.1 Recovery of the activation of a single vector across a single
layer

Consider the recovery of the support, or reverse pass activation pattern, of a
single vector across a single layer of model 2.2; the signal model for this
layer we can write as

$\hat{\textbf{x}}^{(l-1)}=\textbf{A}\textbf{D}\textbf{x}^{(l)}+\textbf{v}^{(l-1)},$
(3.6)

where we have omitted the superscript layer notation on the matrices A and D
for typographical clarity. For signals consistent with model (3.6) we are able
to provide Lemma 1.

######  Lemma 1.

Suppose we have an estimate of the representation of a data point, generated
under model 2.1, at layer $l-1$, which we denote $\hat{\textbf{x}}^{(l-1)}$
and assume it is consistent with model (3.6). Let $\textbf{x}^{(l)}$, whose
support we denote as $\Lambda$, be a solution to (3.6) with
$\|\textbf{x}^{(l)}\|_{0,\infty}^{Q^{(l)}}\leq S_{l}$,
$\|\textbf{v}^{(l)}\|_{2,\infty}^{P^{(l)}}\leq\zeta_{l-1}$ and assume that we
know the cardinality of the support, $|\Lambda|$. Suppose that
$\hat{\textbf{x}}^{(l)}$ is computed according to 2.4. Denoting the event that
the locations of the nonzeros in $\textbf{x}^{(l)}$ and
$\hat{\textbf{x}}^{(l)}$ differ as $\bar{W}_{\Lambda}^{(l)}$, then

$P(\bar{W}_{\Lambda}^{(l)})\leq
2nM\exp\left(-\frac{|x^{(l)}_{min}|^{2}}{8\left(|x^{(l)}_{max}|^{2}\mu_{l}^{2}S_{l}+\zeta_{l-1}^{2}\right)}\right).$
(3.7)

Furthermore in the setting where the location of the nonzeros in
$\textbf{x}^{(l)}$ and $\hat{\textbf{x}}^{(l)}$ are the same, then

$\|\hat{\textbf{x}}^{(l)}-\textbf{x}^{(l)}\|_{2,\infty}^{P^{(l)}}\leq\zeta_{l}$

where

$\zeta_{l}=\sqrt{\|\hat{\textbf{x}}^{(l)}\|_{0,\infty}^{P^{(l)}}}\left(\mu_{l}(S_{l}-1)|x_{max}^{(l)}|+\zeta_{l-1}\right).$

###### Proof.

Lemma 1 extends bounds in [2] to include additive noise and the stripe
sparsity model $\|\cdot\|_{0,\infty}^{Q^{(l)}}\leq S_{l}$ present for the
convolutional matrices $\textbf{A}^{(l)}$ considered here.

Firstly denote the diagonal elements of D, $\textbf{D}_{jj}$, as
$\varepsilon_{j}$, which are mutually independent random variables with value
either $-1$ or $1$ with probability $0.5$. For $\bar{W}_{\Lambda}^{(l)}$ to
occur requires the condition that there exists some $i\in\Lambda$ and some
$k\in\bar{\Lambda}$ such that
$|\langle\varepsilon_{i}\textbf{a}_{i},\hat{\textbf{x}}^{(l-1)}\rangle|<|\langle\varepsilon_{k}\textbf{a}_{k},\hat{\textbf{x}}^{(l-1)}\rangle|$.
This condition is equivalent to requiring
$\min_{i\in\Lambda}|\langle\varepsilon_{i}\textbf{a}_{i},\hat{\textbf{x}}^{(l-1)}\rangle|$
$<\max_{k\in\bar{\Lambda}}|\langle\varepsilon_{k}\textbf{a}_{k},\hat{\textbf{x}}^{(l-1)}\rangle|$
and hence

$P(\bar{W}_{\Lambda}^{(l)})=P(\min_{i}|\langle\varepsilon_{i}\textbf{a}_{i},\hat{\textbf{x}}^{(l-1)}\rangle|<\max_{k}|\langle\varepsilon_{k}\textbf{a}_{k},\hat{\textbf{x}}^{(l-1)}\rangle|).$

Introducing an arbitrary real valued scalar threshold $p>0$, we form the
inequality

$\begin{split}P(\bar{W}_{\Lambda}^{(l)})\leq&P(\min_{i\in\Lambda}|\langle\varepsilon_{i}\textbf{a}_{i},\hat{\textbf{x}}^{(l-1)}\rangle|<p)+P(\max_{k\in\bar{\Lambda}}|\langle\varepsilon_{k}\textbf{a}_{k},\hat{\textbf{x}}^{(l-1)}\rangle|>p).\end{split}$

We now provide bounds on each of the terms on the right hand side of the above
inequality using the Rademacher concentration inequality provided in Theorem
2. Denoting $\bar{W}_{\Lambda}^{\prime}$ as the event
$\max_{k\notin\Lambda}\\{|\langle\varepsilon_{k}\textbf{a}_{k},\hat{\textbf{x}}^{(l-1)}\rangle|\\}>p$
then

$\displaystyle P(\bar{W}_{\Lambda}^{\prime})$ $\displaystyle=$ $\displaystyle
P\left(\max_{k}\\{|\langle\varepsilon_{k}\textbf{a}_{k},\hat{\textbf{x}}^{(l-1)}\rangle|\\}>p\right)$
$\displaystyle\leq$
$\displaystyle\sum_{k\in\bar{\Lambda}}P\left(|\langle\varepsilon_{k}\textbf{a}_{k},\hat{\textbf{x}}^{(l-1)}\rangle|>p\right)$
$\displaystyle=$
$\displaystyle\sum_{k\in\bar{\Lambda}}P\left(|\sum_{j\in\Lambda}\varepsilon_{j}^{\prime}x_{j}^{(l)}\langle\textbf{a}_{k},\textbf{a}_{j}\rangle+\varepsilon_{k}\langle\textbf{a}_{k},\textbf{v}\rangle|>p\right)$
$\displaystyle\leq$ $\displaystyle
2\sum_{k\in\bar{\Lambda}}\exp\left(\frac{-p^{2}}{2\left(\sum_{j\in\Lambda\cap\Gamma}|x^{(l)}_{j}|^{2}|\langle\textbf{a}_{k},\textbf{a}_{j}\rangle|^{2}+\zeta_{l-1}^{2}\right)}\right)$
$\displaystyle\leq$ $\displaystyle
2(mN-|\Lambda|)\exp\left(\frac{-p^{2}}{2\left(|x^{(l)}_{max}|^{2}S_{l}\mu_{l}^{2}+\zeta_{l-1}^{2}\right)}\right).$

The second line and inequality arises from
$\max_{k\in\bar{\Lambda}}\\{|\langle\varepsilon_{k}\textbf{a}_{k},\hat{\textbf{x}}^{(l-1)}\rangle|\\}>p$
implying
$\cup_{k\in\bar{\Lambda}}\\{|\langle\varepsilon_{k}\textbf{a}_{k},\hat{\textbf{x}}^{(l-1)}\rangle|\\}>p$.
The third line is a simple expansion of the inner product, where we define a
new Rademacher random variable
$\varepsilon_{j}^{\prime}=\varepsilon_{j}\varepsilon_{k}$. Note that the set
of random variables
$\\{\left(\bigcup_{j}\varepsilon_{j}^{\prime}\right)\cup\varepsilon_{k}\\}$ is
also mutually independent. Moving from the third to the fourth line we use
Theorem 2. The set $\Gamma$ refers to the indices of columns of
$\textbf{A}^{(l)}$ which have a nonzero inner product with the column
$\textbf{a}_{k}$. The final line is the result given that
$|\Lambda\cap\Gamma|\leq S_{l}$, which follows from our assumption that
$\|\textbf{x}^{(l)}\|_{0,\infty}^{Q^{(l)}}\leq S_{l}$.

Denoting $\bar{W}_{\Lambda}^{\prime\prime}$ as the event
$\min_{i}\\{|\langle\varepsilon_{i}\textbf{a}_{i},\hat{\textbf{x}}^{(l-1)}\rangle|\\}<p$,
we firstly expand the inner product and then use the triangle inequality to
derive

$|\langle\varepsilon_{i}\textbf{a}_{i},\hat{\textbf{x}}^{(l-1)}\rangle|\geq|x_{i}|-\left|\sum_{j\in\Lambda,j\neq
i}\varepsilon_{j}^{\prime}x_{j}^{(l)}\langle\textbf{a}_{i},\textbf{a}_{j}\rangle+\varepsilon_{i}\langle\textbf{a}_{i},\textbf{v}\rangle\right|.$

We are then able to bound $P(\bar{W}_{\Lambda}^{\prime\prime})$ using
essentially the same steps as before for $P(\bar{W}_{\Lambda}^{\prime})$.

$\begin{split}P(\bar{W}_{\Lambda}^{\prime\prime})&\leq
P\left(\max_{i\in\Lambda}\\{|\sum_{j\in\Lambda,j\neq
i}\varepsilon_{j}^{\prime}x_{j}^{(l)}\langle\textbf{a}_{i},\textbf{a}_{j}\rangle+\varepsilon_{i}\langle\textbf{a}_{i},\textbf{v}\rangle|\\}>|x^{(l)}_{min}|-p\right)\\\
&\leq\sum_{i\in\Lambda}P\left(|\sum_{j\in\Lambda,j\neq
i}\varepsilon_{j}^{\prime}x_{j}^{(l)}\langle\textbf{a}_{i},\textbf{a}_{j}\rangle+\varepsilon_{i}\langle\textbf{a}_{i},\textbf{v}\rangle|>|x^{(l)}_{min}|-p\right)\\\
&\leq
2\sum_{i\in\Lambda}\exp\left(-\frac{(|x_{min}^{(l)}|-p)^{2}}{2\left(\sum_{j\in\Lambda\cap\Gamma/i}|x_{j}|^{2}|\langle\textbf{a}_{k},\textbf{a}_{j}\rangle|^{2}+\zeta_{l-1}^{2}\right)}\right)\\\
&\leq
2|\Lambda|\exp\left(\frac{-(|x_{min}^{(l)}|-p)^{2}}{2\left(|x^{(l)}_{max}|^{2}S_{l}\mu_{l}^{2}+\zeta_{l-1}^{2}\right)}\right).\end{split}$

The first line is a result of rearranging and minimising the expanded inner
product with respect to being less than $p$. The subsequent lines follow in
the same manner as in (3.2.1). Since $p$ can be arbitrary, and since it is
equidistant between the expectations of the two distributions of
$|\langle\varepsilon_{i}\textbf{a}_{i},y\rangle|$ and
$|\langle\varepsilon_{k}\textbf{a}_{k},y\rangle|$, choose $p=|x_{min}|/2$. As
a result combining the bounds on $P(\bar{W}_{\Lambda}^{\prime})$ and
$P(\bar{W}_{\Lambda}^{\prime\prime})$ we obtain the desired probability bound
on $P(\bar{W}_{\Lambda})$.

To now bound the error under the assumption that the support $\Lambda$ is
recovered we provide a proof very similar to that provided in Theorem 8 of
[1]. Firstly

$\begin{split}\|\hat{\textbf{x}}^{(l)}-\textbf{x}^{(l)}\|_{2,\infty}^{P^{(l)}}&=\max_{i}\|P_{i}\textbf{x}^{(l)}-P_{i}^{(l)}\hat{\textbf{x}}^{(l)}\|_{2}\\\
&=\sqrt{\|\textbf{x}^{(l)}\|_{0,\infty}^{P^{(l)}}}\left(\max_{i}\|P_{i}\textbf{x}^{(l)}-P_{i}\hat{\textbf{x}}^{(l)}\|_{\infty}\right)\\\
&\leq\sqrt{\|\textbf{x}^{(l)}\|_{0,\infty}^{P^{(l)}}}\left(\|\textbf{x}^{(l)}-\hat{\textbf{x}}^{(l)}\|_{\infty}\right).\end{split}$

The first equality follows from the definition of the measure
$\|\cdot\|_{2,\infty}^{P^{(l)}}$. In the second inequality we use the vector
norm relationship that for $\textbf{z}\in\mathbb{R}^{m}$, with $k$ nonzeros,
then $\|\textbf{z}\|_{2}\leq\sqrt{k}\|\textbf{z}\|_{\infty}$. Note that
$\hat{\textbf{x}}^{(l)}$ and $\textbf{x}^{(l)}$ have the same support. The
inequality on the third line is due to fact that the largest element in a
vector is at least as large as the largest element of any subset of elements
of the vector. Since
$\|\textbf{x}^{(l)}-\hat{\textbf{x}}^{(l)}\|_{\infty}=\|\textbf{x}^{(l)}_{\Lambda}-\hat{\textbf{x}}^{(l)}_{\Lambda}\|_{\infty}$
, and recalling that the $\ell_{\infty}$ matrix norm is the maximum row sum of
the absolute elements in each row of the matrix, then

$\begin{split}\|\textbf{x}_{\Lambda}^{(l)}-\hat{\textbf{x}}^{(l)}_{\Lambda}\|_{\infty}&=\|(\textbf{A}_{\Lambda}\textbf{D}_{\Lambda})^{+}(\textbf{A}_{\Lambda}\textbf{D}_{\Lambda})\textbf{x}^{(l)}_{\Lambda}-(\textbf{A}_{\Lambda}\textbf{D}_{\Lambda})^{T}\textbf{x}^{(l-1)}\|_{\infty}\\\
&=\|(\textbf{I}-(\textbf{A}_{\Lambda}\textbf{D}_{\Lambda})^{T}(\textbf{A}_{\Lambda}\textbf{D}_{\Lambda}))\textbf{x}^{(l)}_{\Lambda}-(\textbf{A}_{\Lambda}\textbf{D}_{\Lambda})^{T}\textbf{v}^{(l-1)}\|_{\infty}\\\
&\leq\|(\textbf{I}-\textbf{A}_{\Lambda}^{T}\textbf{A}_{\Lambda})\|_{\infty}\|\textbf{x}^{(l)}_{\Lambda}\|_{\infty}+\|\textbf{A}_{\Lambda}^{T}\textbf{v}^{(l-1)}\|_{\infty}\\\
&\leq\mu(\|\textbf{x}^{(l)}\|^{Q^{(l)}}_{0,\infty}-1)|x_{max}|+\zeta_{l-1}.\end{split}$

The equality in line 1 uses
$\textbf{I}=(\textbf{A}_{\Lambda}\textbf{D}_{\Lambda})^{+}(\textbf{A}_{\Lambda}\textbf{D}_{\Lambda})$
and the definition of the estimate derived using (2.4). The equality in line 2
is obtained by introducing a positive and negative
$\textbf{A}_{\Lambda}\textbf{D}_{\Lambda}\textbf{x}^{(l)}_{\Lambda}$ (which
cancel one another hence preserving equality) and then rearranging. The
inequality on the third line is obtained by applying the triangle inequality
and then using the submultiplicative property of the induced matrix norm. The
fourth and final inequality is a result of the definition of the $l_{\infty}$
matrix norm;
$\|(\textbf{I}-\textbf{A}_{\Lambda}^{T}\textbf{A}_{\Lambda})\|_{\infty}=\max_{i}\sum_{j\in\Lambda}|1-\langle\textbf{a}_{i},\textbf{a}_{j}\rangle|$.
The diagonal elements are all zero since
$|\langle\textbf{a}_{i},\textbf{a}_{i}\rangle|=1$ and by the definition of the
mutual coherence the off-diagonal elements are bounded as
$|\langle\textbf{a}_{i},\textbf{a}_{j}\rangle|\leq\mu_{l}$. Defining $\Gamma$
as the set of indices of columns whose supports overlap with $\textbf{a}_{i}$
then

$\begin{split}\max_{i}\sum_{j\in\Lambda}|1-\langle\textbf{a}_{i},\textbf{a}_{j}\rangle|&=\max_{i}\sum_{j\in(\Lambda\cap\Gamma)/i}|1-\langle\textbf{a}_{i},\textbf{a}_{j}\rangle|\\\
&\leq\mu^{(l)}(\|\textbf{x}^{(l)}\|^{Q^{(l)}}_{0,\infty}-1).\end{split}$

Finally since
$\|\textbf{A}_{\Lambda}^{T}\textbf{v}^{(l-1)}\|_{\infty}=\max_{i}|\langle\textbf{a}_{i},\textbf{v}^{(l-1)}\rangle|$,
then, since $\textbf{a}_{i}$ is only supported over $m_{l-1}$ elements,
$|\langle\textbf{a}_{i},\textbf{v}^{(l-1)}\rangle|\leq\zeta_{l-1}$. Combining
these results we arrive at the stability bound presented in Lemma 1. ∎

####  3.2.2 Recovery of the activations of a single vector across multiple
layers

With the single layer, single vector case proven in Lemma 1, we now proceed to
investigate the single vector, multilayer case.

######  Lemma 2.

Suppose we have a data point
$\hat{\textbf{x}}^{(0)}=\textbf{x}^{(0)}+\textbf{v}^{(0)}$, where
$\textbf{x}^{(0)}$ is a column from a matrix generated under Model (2.1) and
$\textbf{v}^{(0)}$ is some noise. We estimate the latent representations of
$\textbf{x}^{(0)}$ at every layer by recursively applying (2.4). Assume that
there exists $\\{S_{l}\\}$ and $\\{\zeta_{l}\\}$ such that
$\|\textbf{x}^{(l)}\|_{0,\infty}^{Q^{(l)}}\leq S_{l}$ and
$\|\textbf{V}^{(l)}\|_{2,\infty}^{P^{(l)}}\leq\zeta_{l}$ are satisfied for all
$l$. If $\bar{Y_{L}}$ denotes the event that the thresholding operation of the
forward pass fails to exactly recover the set of supports
$\\{\Lambda\\}_{l=1}^{L}$ (or reverse activation paths), then

$P(\bar{Y}_{L})\leq
2M\sum_{l=1}^{L}n_{l}\exp\left(-\frac{|x^{(l)}_{min}|^{2}}{8\left(|x^{(l)}_{max}|^{2}\mu_{l}^{2}S_{l}+\zeta_{l-1}^{2}\right)}\right).$
(3.9)

Furthermore in the setting where the location of the nonzeros in
$\textbf{x}^{(l)}$ and $\hat{\textbf{x}}^{(l)}$ are the same, we are able to
characterise $\\{\zeta_{l}\\}_{l=0}^{L-1}$ in a recursive manner as

$\|\hat{\textbf{x}}^{(l)}-\textbf{x}^{(l)}\|_{2,\infty}^{P^{(l)}}\leq\zeta_{l},$

where

$\zeta_{l}=\sqrt{\|\hat{\textbf{x}}^{(l)}\|_{0,\infty}^{P^{(l)}}}\left(\mu_{l}(S_{l}-1)|x_{max}^{(l)}|+\zeta_{l-1}\right).$

###### Proof.

This result can be proved easily via induction. For the sake of convenience
let

$\gamma^{(l)}=2Mn_{l}\exp\left(-\frac{|x^{(l)}_{min}|^{2}}{8\left(|x^{(l)}_{max}|^{2}\mu_{l}^{2}S_{l}+\zeta_{l-1}^{2}\right)}\right).$

Note that the bound on the error at each layer is conditioned on the correct
recovery of the support at the previous layer. Letting
$\bar{W}_{\Lambda}^{(l)}$ be the event that the support at the $l$th layer is
not correctly recovered, then

$\begin{split}&P(\bar{W}_{\Lambda}^{(1)})\leq\gamma^{(1)}\\\
&P(\bar{W}_{\Lambda}^{(2)}|W_{\Lambda}^{(1)})\leq\gamma^{(2)}\\\ &...\\\
&P(\bar{W}_{\Lambda}^{(l)}|\cap_{i}^{(l-1)}W_{\Lambda}^{(i)})\leq\gamma^{(l)}.\end{split}$

The result for $L=1$ is trivial so we will proceed with the proof by induction
by considering the base case $L=2$. Applying De Morgan’s theorem to
$\bar{Y_{2}}$ we obtain

$\begin{split}P(\bar{Y_{2}})&=P(\bar{W}_{\Lambda}^{(1)}\cup\bar{W}_{\Lambda}^{(2)})\\\
&=P(\bar{W}_{\Lambda}^{(1)})+P(\bar{W}_{\Lambda}^{(2)}\cap
W_{\Lambda}^{(1)})\\\
&=P(\bar{W}_{\Lambda}^{(1)})+P(\bar{W}_{\Lambda}^{(2)}|W_{\Lambda}^{(1)})P(W_{\Lambda}^{(1)})\\\
&\leq\gamma^{(1)}+\gamma^{(2)}P(W_{\Lambda}^{(1)})\\\
&\leq\gamma^{(1)}+\gamma^{(2)}.\end{split}$

Hence our theorem is correct for $L=1$ and $L=2$. Now assume that the result
holds true for the kth layer, i.e.

$P(\bar{Y}_{k})\leq\sum_{l=1}^{k}\gamma^{(l)}.$

Considering $\bar{Y}_{k+1}$ then

$\begin{split}P(\bar{Y}_{k+1})&=P(\bar{W}_{\Lambda}^{(k+1)}\cup\bar{Y_{k}})\\\
&=P(\bar{Y_{k}})+P(\bar{W}_{\Lambda}^{(k+1)}\cap Y_{k})\\\
&=P(\bar{Y_{k}})+P(\bar{W}_{\Lambda}^{(k+1)}|Y_{k})P(Y_{k})\\\
&\leq\sum_{l=1}^{k}\gamma^{(l)}+\gamma^{(k+1)}P(Y_{k})\\\
&\leq\sum_{l=1}^{k}\gamma^{(l)}+\gamma^{(k+1)}\\\
&=\sum_{l=1}^{k+1}\gamma^{(l)}.\end{split}$

This proves the result holds for the $k+1$th case and given this and our base
case hold then all others must follow. The bound on the error at each layer
follows in exactly the same manner as that of Lemma 1. ∎

####  3.2.3 Recovery of the activations of multiple vectors across multiple
layers

With Lemma 1 and 2 in place it is a fairly simple step to derive Theorem 1.
Suppose that $Y^{(L)}_{j}$ is the event that supports
$\\{\Lambda_{j}^{(l)}\\}_{l=1}^{L}$ of the representations
$\\{\textbf{x}_{j}^{(l)}\\}_{l=1}^{L}$ of the $j$th data point are recovered
from $\\{\hat{\textbf{x}}_{j}^{(l)}\\}_{l=1}^{L}$. Let

$Z_{L}\triangleq\bigcap_{j=1}^{d}Y^{(L)}_{j}.$

Applying De Morgan’s Theorem then
$\bar{Z}^{(L)}=\bigcup_{j=1}^{d}\bar{Y}^{(L)}_{j}$. As a result we obtain

$\begin{split}P(\bar{Z}_{L})&\leq\sum_{j=1}^{d}P(\bar{Y}^{(L)}_{j})\\\ &\leq
2M\sum_{j=1}^{d}\sum_{l=1}^{L}\gamma_{j}^{(l)}\\\ &\leq
2Md\sum_{l=1}^{L}\gamma_{max},\end{split}$

which gives the probability bound claimed in Theorem 1.

##  4 Conclusion

Interpreting the forward pass algorithm as a sparse coding problem allows us
to make claims and conditions sufficient in theory for the successful
operation of the forward pass. Our contributions in this paper are a) an
approach to carrying out an average rather than worst case analysis for the
recovery of activation pathways in deep sparse coding networks (as stated in
2.2) and b) Theorem 1, which extends the prior uniform bounds in [1] to high
probability bounds. The key benefit of this result is the proportionality to
the dictionary coherence of the upper bound on the signal’s complexity
(measured in terms of the number of non-zeros per stripe) improving from
$\mu^{-1}$ to $\mu^{-2}$. Assuming the weight matrices are suitably
conditioned, this indicates that the forward pass algorithm is likely to
recover the latent representations in Model 2.2 for a more complex (again
measured in terms of the number of non-zeros per stripe) family of signals
than previously thought. In summary, this suggests that if optimal sparse
coding is indeed an important factor explaining the success of certain DCNN
architectures, then explicitly encouraging weight matrices with low coherence
during training could improve the DCNN’s performance.

## References

  * [1] V. Papyan, Y. Romano, and M. Elad.  Convolutional Neural Networks Analyzed via Convolutional Sparse Coding.  ArXiv e-prints, July 2016.
  * [2] K. Schnass and P. Vandergheynst.  Average performance analysis for thresholding.  IEEE Signal Processing Letters, 14(11):828–831, Nov 2007.
  * [3] Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton.  Imagenet classification with deep convolutional neural networks.  In F. Pereira, C. J. C. Burges, L. Bottou, and K. Q. Weinberger, editors, Advances in Neural Information Processing Systems 25, pages 1097–1105. Curran Associates, Inc., 2012.
  * [4] Yoon Kim.  Convolutional neural networks for sentence classification.  In EMNLP, 2014.
  * [5] Y. Zhang, M. Pezeshki, P. Brakel, S. Zhang, C. L. Yoshua Bengio, and A. Courville.  Towards End-to-End Speech Recognition with Deep Convolutional Neural Networks.  ArXiv e-prints, January 2017.
  * [6] H. N. Mhaskar and T. Poggio.  Deep vs. shallow networks: An approximation theory perspective.  Analysis and Applications, 14(06):829–848, 2016.
  * [7] Jeffrey Pennington and Yasaman Bahri.  Geometry of neural network loss surfaces via random matrix theory.  2017\.
  * [8] Tomaso A. Poggio and Qianli Liao.  Theory ii: Landscape of the empirical risk in deep learning.  CoRR, abs/1703.09833, 2017.
  * [9] C. D. Freeman and J. Bruna.  Topology and Geometry of Half-Rectified Network Optimization.  ArXiv e-prints, November 2016.
  * [10] Benjamin D. Haeffele and René Vidal.  Global optimality in tensor factorization, deep learning, and beyond.  CoRR, abs/1506.07540, 2015.
  * [11] Joan Bruna and Stephane Mallat.  Invariant scattering convolution networks.  IEEE Trans. Pattern Anal. Mach. Intell., 35(8):1872–1886, August 2013.
  * [12] T. Wiatowski, P. Grohs, and H. Bölcskei.  Energy Propagation in Deep Convolutional Neural Networks.  ArXiv e-prints, April 2017.
  * [13] C. Zhang, S. Bengio, M. Hardt, B. Recht, and O. Vinyals.  Understanding deep learning requires rethinking generalization.  ArXiv e-prints, November 2016.
  * [14] Xavier Glorot, Antoine Bordes, and Yoshua Bengio.  Deep sparse rectifier neural networks.  In Geoffrey Gordon, David Dunson, and Miroslav Dudík, editors, Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, volume 15 of Proceedings of Machine Learning Research, pages 315–323, Fort Lauderdale, FL, USA, 11–13 Apr 2011\. PMLR.
  * [15] V. Papyan, J. Sulam, and M. Elad.  Working Locally Thinking Globally: Theoretical Guarantees for Convolutional Sparse Coding.  IEEE Transactions on Signal Processing, 65:5687–5701, November 2017\.
  * [16] R. Foucart and H. Rauhut.  A Mathematical Introduction to Compressive Sensing.  Applied and Numerical Harmonic Analysis. Birkhäuser Basel, 2013.
  * [17] L R. Welch.  Lower bounds on the maximum cross correlation of signals (corresp.).  20:397 – 399, 06 1974.
  * [18] M. Ledoux and M. Talagrand.  Probability in Banach Spaces.  Classics in Mathematics. Springer-Verlag Berlin Heidelberg, 2011.