IEEE Signal Processing - July 2018 - 77

Sparseland difficulties: Atom decomposition

min c
c

s.t. x = Dc.

s.t.

y - Dc

# e.

0
1,
60
0
1,
80
0
2,
00
0

1,
40

1,
20

1,
00

Original Sparse Vector
Thresholding

OMP
BP

(1)

This problem seeks the sparsest explanation of x as a linear
combination of atoms from D. In a more practical version of the
atom-decomposition problem, we may assume that the signal we
get, y, is an e-contaminated version of x, and then the optimization task becomes
min
c
c

4
3
2
1
0
-1
-2
-3
-4
-5

The term atom-decomposition refers to the most fundamental
problem of identifying the atoms that construct a given signal.
Consider the following example: We are given a dictionary having 2,000 atoms, and a signal known to be composed of a mixture of 15 of these. Our goal now is to identify these 15 atoms.
How should this be done? The natural option to consider is an
exhaustive search over all the possibilities of choosing 15 atoms
out of the 2,000, and checking per each whether they fit the measurements. The number of such possibilities to check stands on
an order of 2.4e + 37, and even if each of this takes 1 ps, billions of years will be required to complete this task!
Put formally, atom decomposition can be described as the following constrained optimization problem:

(2)

Both (1) and (2) are known to be NP-hard, implying that their
complexity grows exponentially with the number of atoms in D.
So, are we stuck?
The answer to this difficulty came in the form of approximation algorithms, originally meant to provide exactly that-an
approximate solution to the previously given problems. In this
context, we mention greedy methods such as the orthogonal
matching pursuit (OMP) [31] and the thresholding algorithm, and
relaxation formulations such as the BP [27].
While it is beyond the scope of this article to provide a
detailed description of these algorithms, we will say a few
words on each, as we will return to use them later when we
get closer to the connection to neural networks. BP takes the
problem posed in (2) and relaxes it by replacing the , 0 by an , 1
-norm. With this change, the problem is convex and manageable
in reasonable time.
Greedy methods such as the OMP solve the problem posed
in (2) by adding one nonzero at a time to the solution, trying to
reduce the error y - Dc 2 as much as possible at each step,
and stopping when this error goes below e. The thresholding algorithm is the simplest and crudest of all pursuit
methods-it multiplies y by D T , and applies a simple shrinkage on the resulting vector, nulling small entries and leaving the
rest almost untouched.
Figure 2 presents an experiment in which these three
algorithms were applied on the scenario we described previously, in which D has 2,000 atoms, and an approximate atom
decomposition is performed on noisy signals that are known
to be created from few of these atoms. The results shown suggest that these three algorithms tend to succeed rather well in
their mission.

Figure 2. An illustration of OMP, BP, and thresholding in approximating
the solution of the atom decomposition problem, for a dictionary with
2,000 atoms.

Sparseland difficulties: Theoretical foundations
Can the success of the pursuit algorithms be explained and justified? One of the grand achievements of the field of Sparseland is
the theoretical analysis that accompanies many of these pursuit
algorithms, claiming their guaranteed success under some conditions on the cardinality of the unknown representation and the
dictionary properties. Hundreds of papers offering such results
were authored in the past two decades, providing Sparseland
with the necessary theoretical foundations. This activity essentially resolved the atom-decomposition difficulty to the point
where we can safely assume that this task is doable-reliably,
efficiently, and accurately.
Let us illustrate the theoretical side of Sparseland by providing a small sample from these results. We bring one such representative theorem that discusses the terms of success of the
BP. This is the first among a series of such theoretical results
that will be stated throughout this article. Common to them all
is our sincere effort to choose the simplest results, and these
will rely on a simple property of the dictionary D called the
mutual coherence.

Definition

Given the dictionary D ! R n # m, assume that the columns of this
matrix, " d i ,mi = 1 are , 2 -normalized. The mutual coherence
n (D) is defined as the maximal absolute inner product between
different atoms in D [32]:
T

n (D) = max d i d j .
1#i1j#m

(3)

Clearly, 0 # n (D) # 1 and, as we will see, the smaller this
value is, the better our theoretical guarantees become. We note
that other characterizations of D exist and have been used quite
extensively in developing the theory of Sparseland. These
include the restricted isometry property (RIP) [33], the exact
recovery condition (ERC) [34], the Babel function [35], the

IEEE Signal Processing Magazine

July 2018

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