Working Locally Thinking Globally - Part I: Theoretical Guarantees for Convolutional Sparse Coding

I Introduction

Generally, solving a pursuit problem is a computationally challenging task. As a consequence, most such recent successful methods have been deployed on relatively small dimensional signals, commonly referred to as patches. Under this local paradigm, the signal is broken into overlapped blocks and the above defined sparse coding problem is reformulated as

The above discussion suggests that in order to find a consistent global representation for the signal, one should propose a global sparse model. However, employing a general global dictionary is infeasible due to the curse of dimensionality and the complexity involved. An alternative is a global model in which the signal is composed as a superposition of local atoms. The family of dictionaries giving rise to such signals is a concatenation of banded Circulant matrices. This global model benefits from having a local shift invariant structure – a popular assumption in signal and image processing – suggesting an interesting connection to the above-mentioned local modeling.

When the dictionary ${\mathbf{D}}$ has this structure of a concatenation of banded Circulant matrices, the pursuit problem in (1) is usually known as convolutional sparse coding . Recently, several works have addressed the problem of using and training such a model in the context of image inpainting, super-resolution, and general image representation . These methods exploit an ADMM formulation in the Fourier domain in order to search for the sparse codes and train the dictionary involved. Several variations have been proposed for solving the pursuit problem, yet there has been no theoretical analysis of their success.

In this two-part work, we consider the following set of questions: Assume a signal ${\mathbf{X}}$ is created by multiplying a sparse vector ${\bm{\Gamma}}$ by a global structured dictionary ${\mathbf{D}}$ that consists of a union of banded and Circulant matrices. Then,

Can we guarantee the uniqueness of such a global (convolutional) sparse vector?

Can global pursuit algorithms, such as the ones suggested in recent works, be guaranteed to find the true underlying sparse code, and if so, under which conditions?

Can we guarantee a stability of the sparse approximation problem, and a stability of corresponding pursuit methods in a noisy regime?; And

Can we solve the global pursuit by restricting the process to local pursuit operations?

In part I of our work, we focus on answering questions 1 and 2, while questions 3 and 4 are analyzed and answered in the sequel paper.

A naïve approach to address such theoretical questions is to apply the fairly extensive results for sparse representation and compressed sensing to the above defined model . However, as we will show throughout this paper, this strategy provides nearly useless results and bounds from a global perspective. Therefore, there exists a true need for a deeper and alternative analysis of the sparse coding problem in the convolutional case which would yield meaningful bounds.

This paper is organized as follows. We begin by reviewing the unconstrained global (traditional) sparse representation model in Section II, followed by a detailed description of the convolutional structure in Section III. Section IV briefly motivates the need of a thorough analysis of this model, which is then provided in Section V. We introduce additional mathematical tools in Section VI, which provide further insight into the convolutional model. Finally, we conclude and motivate the next part of this work in Section VII.

II The Global Sparse Model – Preliminaries

Several results have shed light on the theoretical aspects of this problem, claiming a unique solution under certain circumstances. These guarantees are given in terms of properties of the dictionary ${\mathbf{D}}$, such as the Spark, defined as the minimum number of linearly dependent columns (atoms) in ${\mathbf{D}}$ . Formally,

Based on this property, a solution obeying $\|{\bm{\Gamma}}\|_{0}<\sigma({\mathbf{D}})/2$ is necessarily the sparsest one . Unfortunately, this bound is of little practical use, as computing the Spark of a matrix is a combinatorial problem – and infeasible in practice.

Another guarantee is given in terms of the mutual coherence of the dictionary, $\mu({\mathbf{D}})$. This measure quantifies the similarity of atoms in the dictionary, defined in as:

Solving the $P_{0}$ problem is NP-hard in general. Nevertheless, its solution can be approximated by either greedy pursuit algorithms, such as the Orthogonal Matching Pursuit (OMP) , or convex relaxation approaches like Basis Pursuit (BP) . Despite the difficulty of this problem, these methods (and other similar ones) have been proven to recover the true solution if $\|{\bm{\Gamma}}\|_{0}<\frac{1}{2}\left(1+1/\mu({\mathbf{D}})\right)$ .

In real world applications, due to noisy measurements and model imperfections, the idealistic setting portrayed above is not directly applicable. Nevertheless, one can extend the model to include signal perturbations, obtaining the following problem:

We will deffer studying this case here, as it will be analyzed in detail in part two of this report.

III The Convolutional Sparse Model

When handling large dimensional signals, using an unstructured dictionary becomes unfeasible. In this section we will enforce a constraint on the global dictionary, resulting in both theoretical and practical benefits.

Consider the global dictionary to be a concatenation of $m$ banded Circulant matricesThe choice of Circulant matrices comes to alleviate boundary problems., where each such matrix has a band of width $n\ll N$. As such, by simple permutation of its columns, such a dictionary consists of all shifted versions of a local dictionary ${\mathbf{D}}_{L}$ of size $n\times m$. This model is commonly known as Convolutional Sparse Representation . Hereafter, whenever we refer to the global dictionary ${\mathbf{D}}$, we assume it has this structure. Assume a signal ${\mathbf{X}}$ to be generated as ${\mathbf{D}}{\bm{\Gamma}}$. In Figure 1 we describe such a global signal, its corresponding dictionary that is of size $N\times mN$ and its sparse representation, of length $mN$. We note that ${\bm{\Gamma}}$ is built of $N$ distinct and independent sparse parts, each of length $m$, which we will refer to as the local sparse vectors ${\bm{\alpha}}_{i}$. In this section we shall propose several different interpretations of signals emerging from this model, and as we shall see, these will serve us well in the later analysis.

Consider a global sparse vector ${\bm{\Gamma}}$. Define ${\bm{\gamma}}_{i}={\mathbf{S}}_{i}{\bm{\Gamma}}$ as its $i^{th}$ stripe representation.

Note that a stripe ${\bm{\gamma}}_{i}$ can be also seen as a group of $2n-1$ adjacent local sparse vectors ${\bm{\alpha}}_{j}$ of length $m$ from ${\bm{\Gamma}}$, centered at location ${\bm{\alpha}}_{i}$.

Consider a convolutional dictionary ${\mathbf{D}}$ defined by a local dictionary ${\mathbf{D}}_{L}$ of size $n\times m$. Define the stripe dictionary ${\bm{\Omega}}$ of size $n\times(2n-1)m$, as the one obtained by extracting $n$ consecutive rows from ${\mathbf{D}}$, followed by the removal of its zero columns, namely ${\bm{\Omega}}={\mathbf{R}}_{i}{\mathbf{D}}{\mathbf{S}}_{i}^{T}$.

Observe that ${\bm{\Omega}}$, depicted in Figure 2, is independent of $i$, being the same for all locations due to the union-of-Circulant-matrices structure of ${\mathbf{D}}$. In other words, the shift invariant property is satisfied for this model – all patches share the same stripe dictionary in their construction. Armed with the above two definitions, Equation (7) reads ${\mathbf{x}}_{i}={\bm{\Omega}}{\bm{\gamma}}_{i}$.

From a different perspective, one can synthesize the signal ${\mathbf{X}}$ by a different interpretation of the relation ${\mathbf{X}}={\mathbf{D}}{\bm{\Gamma}}$, shown in Figure 1. The matrix ${\mathbf{D}}$ is a concatenation of $N$ vertical stripes of size $N\times m$, where each can be represented as ${\mathbf{R}}_{i}^{T}{\mathbf{D}}_{L}$. In other words, the vertical stripe is constructed by taking the small and local dictionary ${\mathbf{D}}_{L}$ and positioning it in the $i^{th}$ row. As we have already said, the same partitioning applies to ${\bm{\Gamma}}$, leading to the ${\bm{\alpha}}_{i}$ ingredients. Thus,

Since ${\bm{\alpha}}_{i}$ play the role of local sparse vectors, ${\mathbf{D}}_{L}{\bm{\alpha}}_{i}$ are reconstructed patches (which are not the same as ${\mathbf{x}}_{i}={\bm{\Omega}}{\bm{\gamma}}_{i}$), and the sum above proposes a patch averaging approach as practiced in several papers . This formulation provides another local interpretation of the convolutional model.

Yet a third interpretation of the very same signal construction can be suggested, in which the signal is seen as resulting from a sum of local/small atoms which appear in a small number of locations throughout the signal. This can be formally expressed as

This model (adopting the last, convolutional, interpretation) has received growing attention in recent years in various applications. In a convolutional sparse coding framework was used for pattern detection in images and the analysis of instruments in music signals, while in it was used for the reconstruction of 3D trajectories. The problem of learning the local dictionary ${\mathbf{D}}_{L}$ was also studied in several works .

IV From Global to Local Analysis

Let us now introduce a measure that will provide a local notion of sparsity within a global sparse vector.

Armed with the above definition, we move now to define the ${P_{0,\infty}}$ problem:

When dealing with a global signal, instead of solving the $P_{0}$ problem (defined in Equation (3)) as is commonly done, we aim to solve the above defined objective instead. The key difference is that we are not limiting the overall number of zeros in ${\bm{\Gamma}}$, but rather putting a restriction on its local density.

IV-B Global versus Local Bounds

As mentioned previously, theoretical bounds are often given in terms of the mutual coherence of the dictionary. In this respect, a lower bound on this value is much desired. In the case of our convolution sparse model, this value quantifies not only the correlation between the atoms in ${\mathbf{D}}_{L}$, but also the correlation between their shifts. Though in a different context, a bound for this value was derived in , and it is given by

For example, if $m=1$ (one local atom with all its shifts), this suggests that ${\mathbf{D}}$ might be an orthogonal matrix, and thus $\mu({\mathbf{D}})=0$. Going to the other extreme, for a large value of $m$ one obtains that the best possible coherence is $\mu({\mathbf{D}})\approx\frac{1}{\sqrt{2n}}$ – this is a very high value (e.g., if $n=128$, this coherence bound is $1/16$), considering the fact that it characterizes the whole global dictionary. This implies that if we are to apply BP or OMP to recover the sparsest ${\bm{\Gamma}}$ that represents ${\mathbf{X}}$, the classical sparse approximation results would allow merely $O(\sqrt{n})$ non-zeros in all ${\bm{\Gamma}}$, for any $N$, no matter how long ${\mathbf{X}}$ is!

As we shall see next, the situation is not as grave as may seem, due to our migration from $P_{0}$ to ${P_{0,\infty}}$. Leveraging on the definitions from the previous subsection, we will provide recovery guarantees that will have a local flavor, and the bounds will be given in terms of the number of non-zeros in the densest stripe. This way, we will show that the guarantee conditions can be significantly enhanced to $O(\sqrt{n})$ non-zeros locally rather than globally.

V Theoretical Study

As motivated in the previous section, the concerns of uniqueness, recovery guarantees and stability of sparse solutions in the convolutional case require special attention. We now formally address these questions by closely following the path taken in , carefully generalizing each and every statement to the global-local model discussed here.

Before proceeding onto theoretical grounds, we briefly summarize, for the convenience of the reader, all notations used throughout this work in Table V. Note the unorthodox choice of capital letters for global vectors and lowercase for local ones.

As can be seen from these results, the theoretical bound is far from being tight. However, in the traditional sparse representation model the corresponding bounds have the same loose flavor . This kind of results is in fact expected when using such a worst-case analysis. Tighter bounds could likely be obtained by a probabilistic study, which we leave for future work.

When considering the mutual coherence $\mu({\mathbf{D}})$, one needs to look at the maximal correlation between every pair of atoms in the global dictionary. One should note, however, that atoms having a non-zero correlation must have overlapping supports. As we see, $\mu({\mathbf{D}})$ provides a bound for these values independently of the amount of overlap. One could go beyond this characterization of the convolutional dictionary by a single value and propose to bound all the inner products between atoms for a given shift. In this section we briefly explore this direction of analysis, introducing new tools for this model and addressing the theoretical consequences that they convey. We will only present the main points of these results here for the sake of brevity; the interested reader can find a more detailed discussion on this matter in Appendix C.

Recall that ${\bm{\Omega}}$ is defined as a stripe extracted from the global dictionary ${\mathbf{D}}$, as explained in Section III. Consider the sub-system given by ${\mathbf{x}}_{i}={\bm{\Omega}}{\bm{\gamma}}_{i}$, corresponding to the $i^{th}$ patch in ${\mathbf{X}}$. Note that ${\bm{\Omega}}$ can be split into a set of $2n-1$ blocks of size $n\times m$, where each block is denoted by ${\bm{\Omega}}_{s}$, i.e.,

as shown previously in Figure 2. Similarly, ${\bm{\gamma}}_{i}$ can be split into a set of $2n-1$ vectors of length $m$, each denoted by ${\bm{\gamma}}_{i,s}$ and corresponding to ${\bm{\Omega}}_{s}$. In other words, ${\bm{\gamma}}_{i}=[{\bm{\gamma}}_{i,-n+1}^{T},\dots,{\bm{\gamma}}_{i,-1}^{T},{\bm{\gamma}}_{i,0}^{T},{\bm{\gamma}}_{i,1}^{T},\dots,{\bm{\gamma}}_{i,n-1}^{T}]^{T}$. Note that previously we denoted local sparse vectors of length $m$ by ${\bm{\alpha}}_{j}$. Yet, we will also denote them by ${\bm{\gamma}}_{i,s}$ in order to emphasize the fact that they correspond to the $s^{th}$ shift inside ${\bm{\gamma}}_{i}$. Denote the number of non-zeros in ${\bm{\gamma}}_{i}$ as $n_{i}$. We can also write $n_{i}=\displaystyle\sum_{s=-n+1}^{n-1}n_{i,s}$, where $n_{i,s}$ is the number of non-zeros in each ${\bm{\gamma}}_{i,s}$.

Define the shifted mutual coherence $\mu_{s}$ by

where ${\mathbf{d}}^{0}_{i}$ is a column extracted from ${\bm{\Omega}}_{0}$, ${\mathbf{d}}^{s}_{j}$ is extracted from ${\bm{\Omega}}_{s}$, and we requireThe condition $i\neq j$ if $s=0$ is necessary so as to avoid the inner product of an atom by itself. that $i\neq j$ if $s=0$.

The above definition can be seen as a generalization of the mutual coherence for the shift-invariant local model presented in Section III. Indeed, $\mu_{s}$ characterizes ${\bm{\Omega}}$ just as $\mu({\mathbf{D}})$ characterizes the coherence of a general dictionary. Note that if $s=0$ the above definition boils down to the traditional mutual coherence of ${\mathbf{D}}_{L}$, i.e., $\mu_{0}=\mu({\mathbf{D}}_{L})$. It is important to stress that the atoms used in the above definition are normalized globally according to ${\mathbf{D}}$ and not ${\bm{\Omega}}$. In Appendix C we comment on several interesting properties of this measure.

Following the definition of the shifted mutual coherence, for a given stripe $i$ from the linear system of equations ${\mathbf{X}}={\mathbf{D}}{\bm{\Gamma}}$, we can formulate a new measure:

According to this definition, each stripe has a coherence given by the sum of its non-zeros weighted by the shifted mutual coherence. As a particular case, if all $k$ non-zeros correspond to atoms in the center sub-dictionary, ${\mathbf{D}}_{L}$, this becomes $\mu_{0}k$. Note that unlike the traditional mutual coherence, this new measure depends on the location of the non-zeros in ${\bm{\Gamma}}$ – it is a function of the support of the sparse vector, and not just of the dictionary. As such, it characterizes the correlation between the atoms participating in a given stripe. In what follows, we will use the notation $\zeta_{i}$ for $\zeta({\bm{\gamma}}_{i})$.

Next, we will present results based on these measures. Although these theorems are generally sharper, they are harder to grasp. We begin with a recovery guarantee for the OMP and BP algorithms, followed by a discussion on their implications.

(Global OMP recovery guarantee using the stripe coherence): Given the system of linear equations ${\mathbf{X}}={\mathbf{D}}{\bm{\Gamma}}$, if a solution ${\bm{\Gamma}}$ exists satisfying

(Global BP recovery guarantee using the stripe coherence): Given the system of linear equations ${\mathbf{X}}={\mathbf{D}}{\bm{\Gamma}}$, if a solution ${\bm{\Gamma}}$ exists satisfying

then Basis Pursuit is guaranteed to recover it.

The corresponding proofs are similar to their counterparts presented in the preceding section but require a more delicate analysis; one of them is thoroughly discussed in Appendix D.

In order to provide an intuitive interpretation for these results, the above bounds can be tied to a concrete number of non-zeros per stripe. First, notice that requiring the maximal stripe coherence to be less than a certain threshold is equal to requiring the same for every stripe:

Multiplying and dividing the left-hand side of the above inequality by $n_{i}$ and rearranging the resulting expression, we obtain

Define $\bar{\mu}_{i}=\sum_{s=-n+1}^{n-1}\frac{n_{i,s}}{n_{i}}\mu_{s}$. Recall that $\sum_{s=-n+1}^{n-1}\frac{n_{i,s}}{n_{i}}=1$ and as such $\bar{\mu}_{i}$ is simply the (weighted) average shifted mutual coherence in the $i^{th}$ stripe. Putting this definition into the above condition, the inequality becomes

Thus, the condition in (27) boils down to requiring the sparsity of all stripes to be less than a certain number. Naturally, this inequality resembles the one presented in the previous section for the OMP and BP guarantees. The reader might wonder about how they are related. In Appendix C we prove that under the assumption that $\mu({\mathbf{D}})=\mu_{0}$, the shifted mutual coherence condition is at least as strong as the original one.

As a final note, the shifted mutual coherence, $\mu_{s}$, is a considerably more informative measure than the standard mutual coherence. In some applications, the signals created by the convolutional dictionary are built of atoms which are known a priori to be separated by some minimal lag, or shift. In radio communications, for example, such a situation appears when there exists a minimal time between consecutive transmissions . In these cases, knowing how the correlation between the atoms depends on their shifts is fundamental for the design of the dictionary and its utilization.

One of the cardinal motivations for this work was a series of recent practical methods addressing the convolutional sparse coding problem; and in particular, the need for their theoretical foundation. However, our results are as of yet not directly applicable to these, as we have restricted our analysis to the ideal case of noiseless signals. The natural extension to this work is therefore the study of signals under noise contamination and model imperfections. This is indeed the path we undertake in part II of our work, exploring the question of whether the convolutional model remains stable in the presence of noise. Moreover, we show how to decompose and solve the global pursuit by performing merely local operations. This will tie the algorithmic solutions for the convolutional model to patch-based methods, which are the current practice in state-of-the-art signal and image restoration.

The research leading to these results has received funding from the European Research Council under European Union’s Seventh Framework Programme, ERC Grant agreement no. 320649. The authors would like to thank Dmitry Batenkov, Yaniv Romano and Raja Giryes for the prolific conversations and most useful advice which helped shape this work.

Let ${\bm{\Gamma}}^{1}$ and ${\bm{\Gamma}}^{2}$ be two global sparse vectors. Denote the $i^{th}$ stripe extracted from each as ${\bm{\gamma}}^{1}_{i}$ and ${\bm{\gamma}}^{2}_{i}$, respectively. Notice that

In this section we prove both theorems presented in Section V, which guarantee the success of OMP and BP in solving the ${P_{0,\infty}}$ problem. We begin by presenting the OMP proof.

Denoting by $\mathcal{T}$ the support of the solution ${\bm{\Gamma}}$, we can write

Suppose, without loss of generality, that the sparsest solution has its largest coefficient (in absolute value) in $\Gamma_{i}$. For the first step of the OMP to choose one of the atoms in the support, we require

Substituting Equation (B-1) in this requirement we obtain

Using the reverse triangle inequality, the assumption that the atoms are normalized, and that $|\Gamma_{i}|\geq|\Gamma_{t}|$, we construct a lower bound for the left hand side:

Consider the stripe which completely contains the $i^{th}$ atom as shown in Figure 4. Notice that ${\mathbf{d}}_{t}^{T}{\mathbf{d}}_{i}$ is zero for every atom too far from ${\mathbf{d}}_{i}$ because the atoms do not overlap. Denoting the stripe which fully contains the $i^{th}$ atom as $p(i)$ and its support as $\mathcal{T}_{p(i)}$, we can restrict the summation as:

We can bound the right side by using the number of non-zeros in the support $\mathcal{T}_{p(i)}$, denoted by $n_{p(i)}$, together with the definition of the mutual coherence, obtaining:

Now, we construct an upper bound for the right hand side of Equation (B-3), using the triangle inequality and the fact that $|\Gamma_{i}|$ is the maximal value in the sparse vector:

Relying on the same rational as above, we obtain:

From this we obtain the requirement stated in the theorem. Thus, this condition guarantees the success of the first OMP step, implying it will choose an atom inside the true support.

B-B BP Success Guarantee (Proof of Theorem 9)

By defining ${\bm{\Delta}}=\hat{{\bm{\Gamma}}}-{\bm{\Gamma}}$, we obtain a shifted version of the set,

In what follows, we will enlarge the set ${\mathbf{C}}_{s}$ and prove that it remains empty even after this expansion. Since ${\mathbf{D}}{\bm{\Delta}}=\mathbf{0}$, then ${\mathbf{D}}^{T}{\mathbf{D}}{\bm{\Delta}}=\mathbf{0}$. By subtracting ${\bm{\Delta}}$ from both sides, we obtain

Taking an entry-wise absolute value on both sides, we obtain

where we have applied the triangle inequality to the multiplication of the $i^{th}$ row of $({\mathbf{D}}^{T}{\mathbf{D}}-\mathbf{I})$ by the vector ${\bm{\Delta}}$. Note that in the convolutional case ${\mathbf{D}}^{T}{\mathbf{D}}$ is zero for inner products of atoms which do not overlap. Furthermore, the $i^{th}$ row of ${\mathbf{D}}^{T}{\mathbf{D}}$ is non-zero only in the indices which correspond to the stripe that fully contains the $i^{th}$ atom, and these non-zero entries can be bounded by $\mu({\mathbf{D}})$. Thus, extracting the $i^{th}$ row from the above equation gives

where $p(i)$ is the stripe centered around the $i^{th}$ atom and ${\bm{\delta}}_{p(i)}$ is the corresponding sparse vector of length $(2n-1)m$ extracted from ${\bm{\Delta}}$, as can be seen in Figure 5.

The above expression is a relaxation of the equality in Equation (B-16), since each entry $\Delta_{i}$ is no longer constrained to a specific value, but rather bounded from below and above. Therefore, by putting the above into ${\mathbf{C}}_{s}$, we obtain a larger set ${\mathbf{C}}_{s}^{1}$:

Next, let us examine the second requirement

where, as before, $\mathcal{T}({\bm{\Gamma}})$ denotes the support of ${\bm{\Gamma}}$. Using the reverse triangle inequality, $|a+b|-|b|\geq-|a|$, we obtain

where the vector $\mathds{1}_{\mathcal{T}({\bm{\Gamma}})}$ contains ones in the entries corresponding to the support of ${\bm{\Gamma}}$ and zeros elsewhere. Note that every vector satisfying Equation (B-21) will necessarily satisfy Equation (B-22). Therefore, by relaxing this constraint in ${\mathbf{C}}_{s}^{1}$, we obtain a larger set ${\mathbf{C}}_{s}^{2}$

Next, we will show the above defined set is empty for a small-enough support. We begin by summing the inequalities $|\Delta_{i}|\leq\frac{\mu({\mathbf{D}})}{\mu({\mathbf{D}})+1}\|{\bm{\delta}}_{p(i)}\|_{1}$ over the support of ${\bm{\gamma}}_{{p(i)},0}$. Recall that ${\bm{\gamma}}_{p(i)}$ is defined to be a stripe of length $(2n-1)m$ extracted from the global representation vector and ${\bm{\gamma}}_{p(i),0}$ corresponds to the central $m$ coefficients in the $p(i)$ stripe. Also, note that ${\bm{\delta}}_{p(i)}$ is equal for all the entries inside the support of ${\bm{\gamma}}_{p(i),0}$. Since all the atoms inside the support of ${\bm{\gamma}}_{p(i),0}$ are fully overlapping, ${\bm{\delta}}_{p(i)}$ does not change, as explained in Figure 5. Thus, we obtain

Summing over all different $p(i)$ we obtain

Define a banded matrix ${\mathbf{A}}$ (with a band of width $2n-1$) such that ${\mathbf{A}}_{k,j}=\|{\bm{\gamma}}_{k,0}\|_{0}\cdot\|{\bm{\delta}}_{j,0}\|_{1}$, where $k-n+1\leq j\leq k+n-1$. Notice that the summation in (B-28) is equal to the sum of all entries in this matrix, where the first sum considers all its rows $k$ while the second sum considers all its columns $j$ (the second sum is restricted to the non-zero band). Instead, this interpretation suggests that we could first sum over all the columns $j$, and only then sum over all the rows $k$ which are inside the band. As a result, we obtain that

Using the definition of $\|\cdot\|_{0,\infty}$

For the set ${\mathbf{C}}_{s}^{2}$ to be non-empty, there must exist a ${\bm{\Delta}}$ which satisfies

where the first and second inequalities are given in (B-22) and (B-35), respectively. Rearranging the above we obtain $\|{\bm{\Gamma}}\|_{0,\infty}\geq\frac{1}{2}\left(1+\frac{1}{\mu({\mathbf{D}})}\right)$. However, we have assumed that $\|{\bm{\Gamma}}\|_{0,\infty}<\frac{1}{2}\left(1+\frac{1}{\mu({\mathbf{D}})}\right)$ and thus the previous inequality is not satisfied. As a result, the set we have defined is empty, implying that BP leads to the desired solution. ∎

Appendix C Properties of the Shifted Mutual Coherence and Stripe Coherence

The shifted mutual coherence exhibits some interesting properties:

$\mu_{s}$ is symmetric with respect to the shift $s$, i.e. $\mu_{s}=\mu_{-s}$.

Its maximum over all shifts equals the global mutual coherence of the convolutional dictionary: $\mu({\mathbf{D}})=\underset{s}{\max}\ \mu_{s}$.

The mutual coherence of the local dictionary is bounded by that of the global one: $\mu({\mathbf{D}}_{L})=\mu_{0}\leq\underset{s}{\max}\ \mu_{s}=\mu({\mathbf{D}})$.

We now briefly remind the definition of the maximal stripe coherence, as we will make use of it throughout the rest of the appendix. Given a vector ${\bm{\Gamma}}$, recall that the stripe coherence is defined as $\zeta({\bm{\gamma}}_{i})=\sum_{s=-n+1}^{n-1}n_{i,s}\ \mu_{s}$, where $n_{i,s}$ is the number of non-zeros in the $s^{th}$ shift of ${\bm{\gamma}}_{i}$, taken from ${\bm{\Gamma}}$. The reader might ponder how the maximal stripe coherence might be computed. Let us now define the vector $\mathbf{v}$ which contains in its $i^{th}$ entry the number $n_{i,0}$. Using this definition, the coherence of every stripe can be calculated efficiently by convolving the vector $\mathbf{v}$ with the vector of the shifted mutual coherences $[\mu_{-n+1},\dots,\mu_{-1},\mu_{0},\mu_{1},\dots,\mu_{n-1}]$.

Next, we provide an experiment in order to illustrate the shifted mutual coherence. To this end, we generate a random local dictionary with $m=8$ atoms of length $n=64$ and afterwards normalize its columns. We then construct a convolutional dictionary which contains global atoms of length $N=640$. We exhibit the shifted mutual coherences for this dictionary in Figure 6(a).

We now present a theorem relating the stripe coherences of related sparse vectors.

Let ${\bm{\Gamma}}_{1}$ and ${\bm{\Gamma}}_{2}$ be two global sparse vectors such that the support of ${\bm{\Gamma}}_{1}$ is contained in the support of ${\bm{\Gamma}}_{2}$. Then the maximal stripe coherence of ${\bm{\Gamma}}_{1}$ is less or equal than the maximal stripe coherence of ${\bm{\Gamma}}_{2}$.

Denote by ${\bm{\gamma}}_{i}^{1}$ and ${\bm{\gamma}}_{i}^{2}$ the $i^{th}$ stripe extracted from ${\bm{\Gamma}}_{1}$ and ${\bm{\Gamma}}_{2}$, respectively. Also, denote by $n_{i,s}^{1}$ and $n_{i,s}^{2}$ the number of non-zeros in the $s^{th}$ shift of ${\bm{\gamma}}_{i}^{1}$ and ${\bm{\gamma}}_{i}^{2}$, respectively. Since the support of ${\bm{\Gamma}}_{1}$ is contained in the support of ${\bm{\Gamma}}_{2}$, we have that $\forall i,s\quad n_{i,s}^{1}\leq n_{i,s}^{2}$. As a result, we have that

The left-hand side of the above inequality is the maximal stripe coherence of ${\bm{\Gamma}}_{1}$, while the right-hand side is the corresponding one for ${\bm{\Gamma}}_{2}$. Thus, we conclude that the maximal stripe coherence of ${\bm{\Gamma}}_{1}$ is less or equal than the maximal stripe coherence of ${\bm{\Gamma}}_{2}$. ∎

Appendix D OMP Success Guarantee via Stripe Coherence (Proof of Theorem 12)

The first steps of this proof are exactly those derived in proving Theorem 8, and thus we omit them for the sake brevity. Recall that in order for the first step of OMP to succeed, we require

Lower bounding the left hand side of the above inequality, we can write

as stated previously in Equation (B-6). Instead of summing over the support $\mathcal{T}_{p(i)}$, we can sum over all the supports $\mathcal{T}_{{p(i)},s}$, which correspond to all possible shifts. We can then write

We can bound the right term by using the number of non-zeros in each sub-support $\mathcal{T}_{{p(i)},s}$, denoted by $n_{{p(i)},s}$, together with the corresponding shifted mutual coherence $\mu_{s}$. Also, we can disregard the constraint $t\neq i$ in the above summation by subtracting an extra $\mu_{0}$ term, obtaining:

Bounding the above by the maximal stripe coherence, we obtain

In order to upper bound the right hand side of Equation (D-1) we follow the steps leading to Equation (B-9), resulting in

Using a similar decomposition of the support and the definition of the shifted mutual coherence, we have

Once again bounding this expression by the maximal stripe coherence, we obtain

which is the requirement stated in the theorem. Thus, this condition guarantees the success of the first OMP step, implying it will choose an atom inside the true support $\mathcal{T}$.

The next step in the OMP algorithm is an update of the residual. This is done by decreasing a term proportional to the chosen atom (or atoms within the correct support in subsequent iterations) from the signal. Thus, the support of this residual is contained within the support of the true signal. As a result, according to Theorem 15, the maximal stripe coherence corresponding to the residual is less or equal to the one of the true sparse code ${\bm{\Gamma}}$. Using the same set of steps we obtain that the condition on the maximal stripe coherence (27) guarantees that the algorithm chooses again an atom from the true support of the solution. Furthermore, the orthogonality enforced by the least-squares step guarantees that the same atom is never chosen twice. As a result, after $\|{\bm{\Gamma}}\|_{0}$ iterations the OMP will find all the atoms in the correct support, reaching a residual equal to zero. ∎

As a final note, we mention that assuming $\mu({\mathbf{D}})=\underset{s}{\max}\ \mu_{s}=\mu_{0}$ is in fact a reasonable assumption. Recall that in order to compute $\mu_{s}$ we evaluate inner products between atoms which are $s$ indexes shifted from each other. As a result, the higher the shift $s$ is, the less overlap the atoms have, and the less $\mu_{s}$ is expected to be. Thus, we expect the value $\mu_{0}$ to be the largest or close to it in most cases.

References