IEEE Signal Processing - July 2018 - 75

the earliest of this manifestation (though in a philosophical or
tested empirically to see whether they fit reality sufficiently well.
religious context), a more recent and relevant quote from
This is perhaps the place to disclose that models are almost always
Wrinch and Jeffrey (1921) [25] reads: "The existence of simple
wrong, as they tend to explain reality in a simple manner at the
laws is, then, apparently, to be regarded as a quality of nature;
cost of its oversimplification. Does this mean that models are necand accordingly we may infer that it is justifiable to prefer a
essarily useless? Not at all. While they do carry an error in them,
simple law to a more complex one that fits our observations
if this deviation is small enough, then such models are priceless
slightly better."
and extremely useful for our processing needs. How small is small
When it comes to the description of data, sparsity is an ultienough? This is a tough question that has not been addressed in
mate expression of simplicity, which explains the great attraction
the literature. Here we will simply be satisfied with the assumpit has. While it is hard to pinpoint the exact appearance of the
tion that this error should be substantially smaller compared to
concept of sparsity in characterizing data priors, it is quite clear
the estimation error the model leads to. Note that, often times,
that this idea became widely recognized with
the acceptable relative error is dictated by the
the arrival of the wavelet revolution that took
application or problem that one is trying to
Sparseland started with
place during the late 1980s and early 1990s.
solve by employing the model.
a massive theoretical
The key observation was that this particular
For a model to succeed in its mission of
effort, which slowly
transformation, when applied to many differtreating signals, it must be a good compromise
expanded and diffused to
ent signals or images, produced representabetween simplicity, reliability, and flexibility.
tions that were naturally sparse. This, in turn,
Simplicity is crucial since this implies that
practical algorithms and
was leveraged in various ways, both empirialgorithms harnessing this model are relativeapplications, leading in
cally and theoretically. Almost in parallel,
ly easy and pleasant to work with. However,
many cases to state-ofapproximation theorists started discussing
simplicity is not sufficient. We could suggest,
the-art results in a wide
the dichotomy between linear and nonlinear
for example, a model that simply assumes
variety of disciplines.
approximation, emphasizing further the role
that the signal of interest is zero. This is the
of sparsity in signal analysis. These are the
simplest model imaginable, and yet it is also
prime origins of the field of Sparseland, which borrowed the
useless. So, next to simplicity, comes the second force of reliabilcore idea that signal representations should be redundant and
ity-we must offer a model that does justice to the data served,
sparse, while putting aside many other features of wavelets, such
capturing its true essence. The third virtue is flexibility, implying
as (bi)orthogonality, multiscale analysis, frame theory interprethat the model can be tuned to better fit the data source, thus errtation, and more.
ing less. Every model is torn between these three forces, and we
Signs of Sparseland appeared already in the early and midare constantly seeking simple, reliable, and flexible models that
1990s, with the seminal papers on greedy- (Zhang and Mallat,
improve over their predecessors.
[26]) and relaxation-based (Chen, Donoho, and Saunders, [27])
pursuit algorithms, and even the introduction of the concept of
Models-Summary
dictionary learning by Olshausen and Field [28]. However, it is
Models are central for enabling the processing of structured
our opinion that this field was truly born only few years later, in
data sources. In image processing, models take a leading part
2000, with the publication of the paper by Donoho and Huo [29],
in addressing many tasks, such as denoising, deblurring, and
which was the first to show that the basis pursuit (BP) is provall the other inverse problems, compression, anomaly detecably exact under some conditions. This work dared and defined
tion, sampling, recognition, separation, and more. We hope
a new language, setting the stage for thousands of follow-up
that this perspective on data sources and their inner structure
papers. Sparseland started with a massive theoretical effort,
clarifies the picture, putting decades of research activity in the
which slowly expanded and diffused to practical algorithms and
fields of signal and image processing and machine learning in
applications, leading in many cases to state-of-the-art results in
a proper perspective.
a wide variety of disciplines. The knowledge in this field as it
In the endless quest for a model that explains reality, one
stands today relies heavily on numerical optimization and linear
that has been of central importance in the past two decades is
algebra, and parts of it have a definite machine-learning flavor.
Sparseland. This model slowly and consistently carved its path
to the lead, fueled by both great empirical success and impressive
accompanying theory that added a much needed color to it. We
Introduction to Sparseland
turn now to present this model. We remind the reader that this is
So, what is this model? How can it capture structure in a data
yet another station in our road toward providing a potential explasource? Let us demonstrate this for 8 × 8 image patches, in the
nation of deep learning using sparsity-inspired models.
spirit of the description of the JPEG algorithm mentioned previously. Assume that we are given a family of patches extracted
from natural images. The Sparseland model starts by preparing
Sparse modeling
a dictionary-a set of atom patches of the same size, 8 × 8 pixels. For example, consider a dictionary containing 256 such
On the origin of sparsity-based modeling
atoms. Then, the model assumption is that every incoming
Simplicity as a driving force for explaining natural phenomena
patch could be described as a linear combination of only few
has a central role in sciences. While Occam's razor is perhaps
IEEE Signal Processing Magazine

July 2018

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