IEEE Signal Processing - July 2018 - 80

Ω
RiX

n
(2n - 1)m

γi

Figure 3. The global CSC model.

matrix regardless of i. The notation c i = S i C stands for a
stripe of (2n - 1) m elements from C.
And now we get to the main point of all of this description:
As we move from location i to i + 1, the patch p i + 1 = R i + 1 X
equals Ωc i + 1 . The stripe vector c i + 1 is a shifted version of c i
by m elements. Other than that, we observe that the extracted
patches are all getting a sparse description of their content with
respect to a common dictionary Ω, just as assumed by the locally
operating algorithms. Thus, CSC furnishes a way to make our
local modeling assumption valid, while also posing a clear global
model for X. In other words, the CSC model offers a path toward
answering all of the questions that we have posed in the context of
the global-local gap.

the ability to guarantee that BP will recover a close-enough
sparse representation. Clearly, such a statement is meaningless,
and the unavoidable conclusion is that the classic theory of
Sparseland provides no solid foundations whatsoever to the
CSC model.
The recent work reported in [14] offers an elegant way to
resolve this difficulty, by moving to a new, local, measure of sparsity. Rather than counting the number of nonzeros in the entire
vector C, we run through all the stripe representations, c i = S i C
for i = 1, 2, 3, f, N, and define the relevant cardinality of C as
the maximal number of nonzeros in these stripes. Formally, this
measure can be defined as follows.

CSC: New theoretical foundations

Given the global vector C, we define its local cardinality as

Realizing that CSC may well be the missing link to all of the
locally operating image processing algorithms, and recalling that
it is a special case of Sparseland, we should wonder whether the
classic existing theory of Sparseland provides sufficient foundations for it as well. Using Theorem 1 to the case in which the signal we operate upon is Y = DC + E, where E 2 # e and D is
a convolutional dictionary, the condition for success of the BP is
C

1 1 c 1 + 1 m.
4
n (D)

(9)

Interestingly, the Welch bound offers a lower bound on the best
achievable mutual coherence of our dictionary [58], being
n (D) $

m-1
.
m (2n - 1) - 1

(10)

For example, for m = 2 filters of length n = 200, this value is
. 0.035, and this value necessarily grows as m is increased.
This implies that the bound for success of the BP stands on
C 0 1 7.3. In other words, we allow the entire vector C to
have only seven nonzeros (independently of N, the size of X) for
80

Definition
C

s
0, 3

= max
ci 0 .
1#i#N

(11)

In this terminology, it is an , 0, 3 measure since we count number
of nonzeros, but also maximize over the set of stripes. The superscript s stands for the fact that we sweep through all the stripes
in C, skipping m elements from c i to c i + 1 .
Intuitively, if C s0, 3 is small, this implies that all the stripes
are sparse, and thus each patch in X = DC, has a sparse representation w.r.t. the dictionary Ω. Recall that this is exactly the model
assumption we mentioned previously when operating locally.
Armed with this local-sparsity definition, we are now ready to
define CSC signals, in the same spirit of the Sparseland definition:

Definition
The set of CSC signals of cardinality k over the convolutional
dictionary D is defined as S " D, k , . A signal X belongs to
S " D, k , if it can be described as X = DC, where C s0, 3 # k.
Could we use these new notions of the local sparsity and the
CSC signals in order derive novel and stronger guarantees for the

IEEE Signal Processing Magazine

July 2018

Table of Contents for the Digital Edition of IEEE Signal Processing - July 2018