IEEE Signal Processing - July 2018 - 78

Spark [36], and others. As mentioned previously, we stick with
n (D) in this article due to its simplicity, and this may come at
the cost of getting weaker guarantees.
We are now ready to state our first theorem: The story starts
with an arbitrary sparse vector c that generates a Sparseland signal x = Dc. We get a noisy version of this signal, y = x + e, and
our goal is to obtain an evaluation of a sparse representation that
should be as close as possible to the original c. The following
result claims that BP is guaranteed to provide such performance.

Theorem 1

Given y = Dc + e, where e is an energy-bounded noise,
e 2 # e, and c is sufficiently sparse,
c

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

(4)

then the BP solution, given by
ct = arg min c
c

s.t.

Dc - y

# e,

(5)

(6)

leads to a stable result,
ct - c

■
■

■

4e 2
1 - n (D) (4 c

- 1)

A few comments are in order:
Observe that if we assume e = 0, then Theorem 1 essentially
guarantees a perfect recovery of the original c.
The result stated is a worst-case one, claiming a perfect recovery under the conditions posed and for an adversarial noise.
Far stronger claims exist, in which the noise model is more
realistic (for example, random Gaussian), and then the language is changed to a probabilistic statement (i.e., success
with probability close to 1) under much milder conditions
(see, for example, [37] and [38]).
The literature on Sparseland offers many similar such theorems, either improving Theorem 1, or referring to other pursuit algorithms.

Sparseland difficulties: The quest for the dictionary
Now that we are not so worried anymore about solving the problems posed in (1) and (2), we turn to discuss a far greater difficulty-how can we get the dictionary D? Clearly, everything that
we do with this model relies on a proper choice of this matrix.
Sweeping through the relevant data processing literature, we
may see attempts to
■ use the Sparseland model to fill-in missing parts in natural
images [39], [40]
■ deploy this model for audio processing (e.g., [41] and [42])
■ plan to exploit it for processing seismic data [43], [44]
■ process volumes of hyperspectral imaging [45], [46].
Each of these applications and many others out there call for a
separate and adapted dictionary, so how can D be chosen
or found?
The early steps in Sparseland were made using known transforms as dictionaries. The intuition behind this idea was that
carefully tailored transforms that match specific signals or have
78

particular properties could serve as the dictionaries we are after.
Note that the dictionary represents the inverse transform, as it
multiplies the representation to construct the signal. In this spirit,
wavelets of various kinds were used for one-dimensional (1-D)
signals [19], two-dimensional (2-D) DCT for image patches, and
curvelets [47], contourlets [48], and shearlets [20] were suggested
for images.
While seeming reasonable and elegant, this approach was
found to be quite limited in real applications. The obvious reasons
for this weakness were the partial match that exists between a chosen transform and true data sources, and the lack of flexibility in
these transforms that would enable them to cope with special and
narrow families of signals (e.g., face images, or financial data).
The breakthrough in this quest of getting appropriate dictionaries
came in the form of dictionary learning. The idea is quite simple:
if we are given a large set of signals believed to emerge from a
Sparseland generator, we can ask what is the best dictionary that
can describe these sparsely. In the past decade, we have seen a
wealth of dictionary-learning algorithms, varied in their computational steps, in their objectives, and in their basic assumptions
on the required D. These algorithms gave Sparseland the necessary boost to become a leading model, due to the added ability
to adapt to any data source, and match to its content faithfully.
In this article, we will not dwell too long on this branch of work,
despite its centrality, as our focus will be the model evolution we
are about to present.

Sparseland difficulties: Model validity
We are listing difficulties that the Sparseland model encountered, and, in this framework, we mentioned the atom-decomposition task and the pursuit algorithms that came to resolve it. We
also described the quest for the dictionary and the central role of
dictionary-learning approaches in this field. Beyond these, perhaps the prime difficulty that Sparseland poses is encapsulated
in the following questions: Why should this model be trusted to
perform well on a variety of signal sources? Clearly, images are
not made of atoms, and there is no dictionary behind the scene
that explains our data sources. So, what is the appeal in this specific model?
The answers to those questions are still being built, and they
take two possible paths. On the empirical front, Sparseland has
been deployed successfully in a wide variety of fields and for various tasks, leading time and again to satisfactory and even stateof-the-art results. So, one obvious answer is the simple statement
"We tried it, and it works!" Again, a model cannot be proven to be
correct, but it can be tested with real data, and this is the essence
of this answer.
The second branch of answers to the natural repulse from
Sparseland has been more theoretically oriented, tying this model
to other, well-known and better established, models, showing that
it generalizes and strengthens them. Connections have been established between Sparseland and Markov random field models,
GMMs, and other union-of-subspaces constructions [30]. Indeed,
the general picture obtained from the answers previously given
suggests that Sparseland has a universal ability to describe information content faithfully and effectively, due to the exponential

IEEE Signal Processing Magazine

July 2018

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