IEEE Signal Processing - July 2018 - 79

number of possible supports that a reasonable-sized dictionary enables.

Sparseland difficulties: Summary
The bottom line to all of this discussion is the fact that, as
opposed to our first impression, Sparseland is a simple yet flexible model, and one that can be trusted. The difficulties mentioned have been fully resolved and answered constructively,
and today we are armed with a wide set of algorithms and supporting theory for deploying Sparseland successfully for processing signals.
The interest in this field has grown impressively over the
years, and this is clearly manifested by the exponential growth of
papers published in the arena. Another testimony to the interest
in Sparseland is seen by the wealth of books published in the past
decade in this field-see [19], [30], and [49]-[56]. This attention
brought us to offer a new massive open online course (MOOC),
covering the theory and practice of this field. This MOOC, given
under edX, started in October 2017, and already has more than
2,000 enrolled students. It is expected to be open continuously
for all those who are interested in getting to know more about
this field.

Local versus global in sparse modeling
We now discuss the practicalities of deploying Sparseland in
image processing. The common practice in many of such algorithms, and especially the better performing ones, is to operate
on small and fully overlapping patches. The prime reason for
this mode of work is the desire to harness dictionary-learning
methods, and these are possible only for low-dimensional signals
such as patches. The prior used in such algorithms is therefore
the assumption that every patch extracted from the image is
believed to have a sparse representation with respect to a commonly built dictionary.
After years of using this approach, questions started surfacing regarding this local model assumption, and the underlying
global model that may operate behind the scene. Consider the
following questions, all referring to a global signal X that is
believed to obey such a local behavior-having a sparse representation with respect to a local dictionary D for each of its
extracted patches:
■ How can such a signal be synthesized?
■ Do such signals exist for any D?
■ How should the pursuit be done to fully exploit the believed
structure in X?
■ How should D be trained for such signals?
These tough questions started being addressed in recent works
[14], [57], and this brings us to our next section, in which we dive
into a special case of Sparseland-the CSC model, and resolve
this global-local gap.

Convolutional sparse modeling
Introducing the CSC model
The CSC model offers a unique construction of signals based on
the following relationship:

/ di * Ci .

(7)

i=1

Note that all of our equations and derivations will be built under
the assumption that the treated signals are 1-D, but this model
and all our derivations apply to 2-D and even higher dimensions
just as well. In our notations, X ! R N is the constructed global
signal, the set " d i ,mi = 1 ! R n are m local filters of small support
^n % N h, and C i ! R N are sparse vectors convolved with their
corresponding filters. For simplicity and without loss of generality, we shall assume hereafter that the convolution operations
used are all cyclic. Adopting a more intuitive view of the CSC
model, we can say that X is assumed to be built of many
instances of the small m filters, spread all over the signal
domain. To be exact, the flipped version of the filters are the
ones shifted in all spatial locations, since this flip is part of the
convolution definition. This spread is obtained by the convolution of d i by the sparse feature map C i.
And here is another, more convenient, view of the CSC model.
We start by constructing m circulant matrices C i ! R N # N , representing the convolutions by the filters d i . Each of these matrices
is banded, with only n populated diagonals. Thus, the global signal X can be described as
RC1V
S W
m
SC2W
X = / C i C i = 6C 1 C 2 g C m@ S W = DC.
h
i=1
SS WW
C
T mX

(8)

The concatenated circulant matrices form a global dictionary
D ! R N # mN , and the gathered sparse vectors C i lead to the
global sparse vector C ! R mN . Thus, just as said previously,
CSC is a special case of Sparseland, built around a very structured dictionary being a union of banded and circulant matrices.
Figure 3 presents the obtained dictionary D, where we permute
its columns to obtain a sliding block diagonal form. Each of the
small blocks in this diagonal is the same, denoted by D L -this
is a local dictionary of size n # m, containing the m filters as
its columns.

Why should we consider the CSC?
Why are we interested in the CSC model? Because it
resolves the global-local gap we mentioned previously. Suppose that we extract an n-length patch from X taken in
location i. This is denoted by multiplying X by the patchextractor operator R i ! R n # N , p i = R i X. Using the relation
X = DC, we have that p i = R i X = R i DC. Note that the
multiplication R i D extracts n rows from the dictionary, and
most of their content is simply zero. To remove their empty
columns, we introduce the stripe extraction operator
S i ! R (2n - 1) m # mN that extracts the nonzero part in this set
of rows: R i D = R i DS Ti S i . Armed with this definition, we
observe that p i can be expressed as p i = R i DS Ti S i C = Ωc i .
The structure of Ω, referred to as the stripe dictionary,
appears in Figure 3, showing that Ω = R i DS Ti is a fixed

IEEE Signal Processing Magazine

July 2018

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